哈希表的基础知识是什么？

Question

我对哈希表的基本概念感到很困惑。如果我要编写一个哈希，我该如何开始？哈希表和普通数组有什么区别？

如果有人回答这个问题，我认为我所有的问题都会得到解答： 如果我有100个随机生成的数字(作为键)，我该如何实现一个哈希表？为什么哈希表比数组更优？

伪代码或Java将作为学习工具受到赞赏...

- kylex

---

仍然是一个集合。您正在将100个数字存储在一个集合中。您在集合中查找它们。它们就在那里。哈希映射需要一个键和一个值作为两个独立的元素；否则它只是一个键的集合。 - S.Lott

我更关心哈希表查找键的方式以及如何生成键。 - kylex

使用没有值的哈希表完全可以实现集合。你在哪里需要值？只需要判断键是否存在或不存在即可。 - Zan Lynx

正如 Zan 所说，HashSet 在内部实际上是由 hashtable/hashMap 来支持的。 - matt b

关于集合，我不认为它们是退化的，但它们确实感觉有点奇怪。从概念上讲，你只是将一个键映射到非常简单的布尔值：True（在集合中）或False（不在）。删除一个项目就像将其值设置为False。除了它实际上是Null而不是False。 - Jon Coombs

Answer 1

到目前为止，答案已经帮助定义了哈希表并解释了一些理论，但我认为一个示例可能会帮助您更好地理解它们。

哈希表和普通数组之间有什么区别？

哈希表和数组都是允许您存储和检索数据的结构。两者都允许您指定一个索引并检索与之关联的值。如Daniel Spiewak所指出的那样，区别在于数组的索引是连续的，而哈希表的索引基于与其关联的数据的值。

我为什么要使用哈希表？

哈希表可以提供一种非常有效的方法来搜索大量数据中的项目，特别是其他情况下难以进行搜索的数据。（在这里，“大”意味着巨大的，也就是说，对于执行顺序搜索需要很长时间的数据）。

如果我要编写哈希，我该如何开始？

没问题。最简单的方法是发明一个可以对数据执行的任意数学操作，返回一个数字N（通常是整数）。然后使用该数字作为索引进入一个“桶”数组中，并将数据存储在桶#N中。关键是选择一种操作，使值以一种易于稍后找到它们的方式放置在不同的桶中。

例子：一个大商场保存其顾客的汽车和停车位置的数据库，以帮助购物者记住他们停车的地方。数据库存储make，color，license plate和parking location。离开商店时，购物者通过输入其汽车的品牌和颜色找到了车辆。数据库返回一个（相对较短的）许可证号码和停车位列表。快速扫描即可定位购物者的汽车。

您可以使用一个SQL查询来实现这个：

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

如果数据存储在数组中，它本质上就是一个列表，您可以想像通过扫描所有匹配条目的数组来实现查询。

另一方面，想象一下哈希规则：

添加制造商和颜色中所有字母的ASCII字符代码，除以100，并使用余数作为哈希值。

此规则将每个项目转换为0到99之间的数字，从而将数据排序到100个桶中。 每次客户需要查找汽车时，您可以将制造商和颜色哈希化，以找到包含信息的100个桶之一。 您已经将搜索减少了100倍！

现在将这个例子扩展到大量数据，例如基于十多个条件搜索的数百万条目的数据库。 一个“好”的哈希函数将以最小化任何额外搜索的方式将数据分发到桶中，从而节省大量时间。

- Adam Liss

---

巨大的。那么对于小数据集，比如几千个，我应该期望性能提升吗？ - akshayb

不完全是@akshayb。Java在处理小数据集方面非常高效。 - Lukas Lukac

Answer 2

首先，你需要了解哈希函数是什么。 哈希函数是一种接受键（例如，任意长度的字符串）并返回尽可能唯一的数字的函数。相同的键必须始终返回相同的哈希值。在Java中，一个非常简单的字符串哈希函数可能如下所示：

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

你可以在http://www.azillionmonkeys.com/qed/hash.html学习一个好的哈希函数。现在，哈希表使用该哈希值将值放置到一个数组中。以下是简单的Java方法：

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

（该映射强制唯一键。并非所有映射都是如此。）

两个不同的键可能哈希到相同的值，或者两个不同的哈希映射到相同的数组索引。存在许多处理这种情况的技术。最简单的方法是为每个数组索引使用链表（或二叉树）。如果哈希函数足够好，您将永远不需要进行线性搜索。

现在来查找一个键：

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

- gnud

---

太棒了！我希望我能多次为你投票。这正是我一直计划要写的（作为对我的第一个答案的回应），但没有机会。 - Daniel Spiewak

谢谢你的回答。这个运算符 ^ = 做什么用的？我以前从没见过它。 - BenKoshy

什么是最佳数组大小或者我应该考虑哪些因素来设置这个大小？ - Mateus Pires

Answer 3

哈希表是一种关联数组。这与数组的线性数据结构有很大的区别。使用数组，您可能会执行以下操作：

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

注意通过指定确切的内存偏移量 (i) 从数组中获取元素。这与哈希表不同，哈希表允许您存储键 / 值对，并根据键检索值:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

通过上述表格，我们可以进行如下调用：

int n = table.get("Chris");

请放心，n 的值将被设为 18。

我认为这可能会回答你大部分的问题。哈希表的实现是一个相当有趣的主题，其中维基百科在此方面处理得还算不错。（链接）

- Daniel Spiewak

---

好的，但在实际实现中，table.get("Chris") 不还是要遍历整个表才能找到 Chris 吗？它怎么知道 Chris 在“键”值上？当它进行哈希时，“Chris”实际上发生了什么？ - kylex

好问题。将在另一个答案中回答...如果你不耐烦，可以尝试查看维基百科文章。 - Daniel Spiewak

@me.yahoo.com：请查看我在下面的评论（由于大小限制，无法在此处编写）。 - ashokgelal

不，哈希表永远不会遍历。它会计算“Chris”的哈希值，并将其作为键存储在哈希表的物理插槽中。哈希是对字节值进行的计算（有关详细信息，请参见MD5算法）。 - S.Lott

谢谢你的回答 - 但哈希表和字典有什么不同呢？它们都有键/值对。所以我对它们的区别感到困惑。 - BenKoshy

Answer 4

"我更关心哈希表如何查找键和生成键的方式."

1. 哈希将一个键对象转换为数字。这被称为“哈希”——它使对象成为哈希。请参见哈希函数。例如，对于字符串，求和字节是一种标准的哈希技术。计算模2 ³²的余数以保持哈希到可管理的大小。哈希总是给出相同的答案。这是O（1）。

2. 数字为您提供哈希表中的“插槽”。给定任意键对象，哈希值计算出哈希值。然后，哈希值为您提供了表中的插槽。通常是mod（hash，table size）。这也是O（1）。

这是一般的解决方案。两个数字计算，您就可以从任意对象作为键转换为任意对象作为值。很少有什么东西能像这样快。

从对象到哈希值的转换以以下其中一种常见方式进行。

1. 如果这是一个四字节的“原始”对象，那么该对象的本机值就是一个数字。

2. 对象的地址是4个字节，因此对象的地址可以用作哈希值。

3. 一个简单的哈希函数（例如MD5、SHA1等）会累加对象的字节以创建一个4字节的数字。高级哈希不是字节的简单总和，简单总和不能充分反映所有原始输入位。

哈希表中的插槽是mod（数值，表大小）。

如果插槽有所需的值，您已经完成了任务。如果不是所需值，您需要查找其他位置。有几种流行的探测算法可用于查找表中的空闲位置。线性搜索是查找下一个空闲位置的简单方法。二次探查是一种非线性跳跃，寻找空闲插槽。可以使用固定种子的随机数生成器来生成一系列探测，以平均但任意地传播数据。

探测算法不是O(1)。如果表足够大，碰撞的几率很低，探测就不重要了。如果表太小，就会发生碰撞和探测。此时，需要进行“调整和微调”，以平衡探测和表大小，以优化性能。通常我们只需扩大表格。
请参见哈希表。

- S.Lott

---

谢谢，你们所有的回答都对我有很大帮助。但每个答案都引发了更多的问题。探测是如何工作的？线性探测似乎足够简单。只需沿着表向下走，直到有一个空槽，对吗？但是二次探测呢？它是如何工作的，为什么要这样做或者说它更好吗？ - kylex

二次探测法：“探测间隔与哈希值成正比增加”。为什么它更好？实证数据证明它比线性探测法更好。没有比这更多的“为什么”了。 - S.Lott

"MD5"和"SHA1"是什么意思？ - Hengameh

Answer 5

有一点我还没有看到特别指出的：

使用哈希表而不是数组的重点是性能。

遍历数组通常需要从O(1)到O(x)的时间，其中x是数组中的项目数。但是查找项目的时间将非常变量，特别是如果我们谈论的是数组中数十万个项目。

一个正确加权的哈希表通常具有几乎恒定的访问时间，略高于O(1)，无论哈希表中有多少项目。

- rally25rs

---

哈希表始终有一个键，你可以轻松地计算出插槽，查找不涉及实际搜索。差异在于哈希表可以使用任何东西作为键，而数组只能使用整数作为键。 - S.Lott

是的，一个字符串，例如“green”将始终哈希到相同的值。此外，Java会缓存该值，因此它只运行一次哈希算法来生成它。该哈希值用于获取“bucket”，它基本上是一个数组。然后它迭代地扫描它。理想情况下，每个bucket只有1个项目。 - CodingWithSpike

@rally25rs 【需要引用】 :-) 查看大多数类中hashCode()的源代码。它通常是即时计算而不是记忆化（以避免线程问题）。Object＃hashCode()实现也没有被缓存，但由于内存模型的工作方式，它是一个常量。 - Daniel Spiewak

Java可以缓存字符串值以简化一些事情。这与哈希无关。这只是在Java中恰好成立的事实。 - S.Lott

这就是我所指的。猜测它是字符串特定的（来自Java文档）：“自JDK版本1.3以来，类java.lang.String缓存其哈希码，即仅计算一次哈希码并将其存储在实例变量中，并在每次调用hashCode方法时返回此值。” - CodingWithSpike

Answer 6

您不应该使用哈希表来处理100个随机生成的数字。

一个好的思路是将哈希表看作值对。让我们以学生为例，假设每个学生都有一个学生ID号码。在您的程序中，您存储了关于学生的信息（姓名、电话号码、账单等）。您想仅使用基本信息（例如姓名或学生ID）查找有关学生的所有信息。

假设您有10,000名学生。如果您将它们全部存储在数组中，那么您必须循环遍历整个数组，比较每个条目的学生ID与您要查找的学生ID。

相反，如果您将他们的学生ID号“哈希”（见下文）到数组中的位置，则只需要搜索具有相同哈希的学生。寻找所需内容的工作量大大减少。

在这个例子中，假设学生ID只是6位数字。我们的哈希函数可以使用数字的底部3位作为“哈希键”。因此，232145被哈希到数组位置145。因此，您只需要一个包含999个元素的数组（每个元素都是一个学生列表）。

这应该是一个良好的起点。当然，您应该阅读教科书或维基百科来获取这种信息。但我假设您已经这样做了，已经厌倦了阅读。

- SoapBox

---

为什么不对整个学生ID进行哈希处理呢？ - Frederic Morin

因为那样它就不是一个哈希了，而只是学生ID。此时你可以将其用作数组索引。我认为“哈希”这个词更适合作为示例。 - SoapBox

我是一个初学者程序员，正在阅读你的答案。在我脑海中浮现出一个问题：当你处于学生的房间里，有100个学生，你想跟其中一个学生交流，那你就会说他或她的名字。如果你说克里斯（Chris），并不是每个学生都会站起来。克里斯（Kris）、克里斯（Chris）和克里斯汀（Christine）（有时会被称为克里斯）会站起来。这是因为键值|Kris|、|Chris|和|Christine|都散列到声音/Chris/！但如果你说，“kay ar eye ess”，只有克里斯（Kris）会站起来。这意味着什么？我不理解我的类比对哈希和数组有什么实际意义... - Ziggy

Answer 7

这里简单介绍哈希表的工作原理。

假设你有一家图书馆，里面摆满了书。如果你把每本书都存储在一个数组中，你需要把每本书放在书架上的一个位置，当有人要找一本书时，你需要查看所有书架-这样很慢。但是如果有人说“书号12345”，你可以很容易地找到它。

现在，假设你规定：只要书名以“A”开头，就放在第1排。如果第二个字母是“B”，则放在第2层，第1排。如果第三个字母是“C”，则放在第3架，第2层，第1排......以此类推，直到确定书籍位置。然后，根据书名，你可以准确地知道它应该在哪里。

虽然我描述的“散列”算法存在一些问题——某些货架将会过度负荷，而其他货架则空置，有些书将被分配到同一位置...所以真正的哈希函数要经过精心构造以尽量避免这些问题。

但这就是基本思想。

- Dmitriy

Answer 8

我相信这个问题已经被清晰地回答了很多次。

我只想添加另一个角度（可能会让新读者感到困惑）

在最低抽象级别上，数组只是一块连续的内存块。给定起始地址（startAddress）、大小（sizeOfElement）和单个元素的索引（index），元素的地址计算如下：

elementAddress = startAddress + sizeOfElement * index

值得注意的是，数组可以被抽象成具有“索引”作为键和上述函数作为哈希函数计算值在O（1）时间内位置的哈希表。

- Omer Akhter

Answer 9

我来回答一下哈希表和数组之间的区别，但由于我以前从未实现过任何重要的哈希算法，所以我会把这个问题留给更有经验的人 :)

数组只是一个对象的有序列表。对象本身并不重要...重要的是，如果您想按插入顺序列出对象，则始终相同（这意味着第一个元素始终具有索引0）。

至于哈希表，它是由键索引的，而不是按顺序排列的...我认为对哈希算法进行基本搜索将为您提供比我更多的见解...维基百科有一个非常不错的算法...它确定了“桶”，使得用作键的任意对象可以快速检索。

至于优点：如果插入顺序很重要，则需要数组或某种有序列表。如果快速查找任意键（由各种哈希函数键入）很重要，则哈希表是有意义的。

- Jason Coco

---

你的回答很好，但是有一些事实上的漏洞。数组实际上是随机访问的（你可以在插入arr[0]之前插入arr[10]）。它们在内存中是有序的（正如你所说），但插入顺序是无关紧要的。（我想你可能在想链表） - Daniel Spiewak

继续之前，不是所有的关联表都使用哈希。二叉搜索树是一种非常简单的关联结构（键/值查找），它实际上以完美排序的方式维护事物。 - Daniel Spiewak

有趣的是，哈希表总是在表面下使用数组实现，进一步强调了数组不强制执行插入/访问顺序的事实。 - Daniel Spiewak

@daniel 实际上，我并不是那个意思...只是表达得不好 :) 我说的不是插入顺序，而是在哈希表中，检索顺序不像任意键检索那样重要...感谢你为其他人澄清了这一点!! - Jason Coco

Answer 10

[这是对我在me.yahoo.com/a上发表评论的回复]

这取决于您的哈希函数。假设您的哈希函数按照单词的长度哈希一个单词，那么chris的键将为5。同样，yahoo的键也将为5。现在，这两个值（chris和yahoo）都将进入5（即由5键控的“桶”中）。这样，您就不需要创建与您的数据大小相等的数组。

- askgelal