编程中的哈希表是如何工作的？

Question

在编程中哈希如何工作？我认为哈希是一种允许我使用某个唯一值来检索数据的东西。比如，如果我们有一个数组，并且我开始将东西放入数组中，如果我有另一个变量来跟踪哪个项目在0、1、2号槽中，那么我就可以立即找到该项。这是哈希吗？

哈希的目的是什么？

何时应该实现哈希？从数据结构的角度看，哈希类似于什么？

我所知道的关于哈希的是它允许我们以O(1)的时间复杂度检索项。这正确吗？

- RoR

---

注意：有哈希算法和哈希表两个概念，哈希表是使用哈希算法的数据结构，用于实现映射/关联数组。你指的是后者，但说的是“哈希”，这通常指的是哈希算法或哈希算法的输出。 - user395760

Answer 1

哈希就像一个人的名字一样--它是记住一个人的简短方式，尽管它不必是唯一的。如果你需要查找某个人的信息，只需通过他们的名字查找，如果两个或更多的人有相同的名字，你只需要执行其他检查。

这就是哈希的优势，就像用名字记住人比社会安全号码容易得多一样，通过其哈希码查找对象比实际比较已在集合中的对象要容易得多。

现在，在这个例子中，如果你按姓名在电话簿中查找某个人，你可能会在O（log n）的时间内找到他们，因为姓名按字母顺序排序，并且因为你需要进行二分搜索。然而，如果你按出生于1900年代的100个人的出生年份进行“哈希”，那么你只需要在哈希表/电话簿中进行最多4次比较（每个数字一次）即可通过哈希查找任何一个年份，这是常数时间。然后，如果两个人出生在同一年，你可以使用其他信息来找到你需要的人，平均而言，如果你的表没有太满（例如，如果你对于100个不同的出生年份最多有50个人），你的查找将是常数时间。

（如果你的表超过了50％的容量，你可以将其大小加倍，以保持碰撞次数低，从而保持查找速度快。）

---

更多信息：

如果你曾经听说过用于文件的MD5或SHA-1哈希，那么它们就像文件的“指纹”一样。虽然可能存在具有相同哈希值的两个文件，但这种情况非常罕见，以至于在实际情况下几乎不可能发生；因此，如果你拥有两个文件的哈希值，你可以通过它们的指纹比较这些文件，而不是通过它们的数据，这大大提高了速度。

- user541686

Answer 2

哈希表/字典是一种基于哈希函数值将对象存储在桶中的键/值数据结构。这些键必须是唯一的，但哈希函数值（有时称为哈希码）不一定是唯一的。

“就像我们有一个数组，并开始将物品放入数组中，如果我有另一个变量来跟踪哪个项目位于槽0、1、2…中，那么我就能立即找到一个项目。这是哈希吗？”

不是。哈希函数是一种确定性函数，总是为对象提供相同的值。哈希码不会因对象存储的位置而改变。

“我认为我对哈希有所了解，它使我们能够在O(1)内检索项目。这正确吗？”

几乎可以这样说。如果哈希码冲突不太多，则查找具有O(1)复杂度。但是，如果哈希函数很差，每个对象都具有相同的哈希值，则字典的性能可能是O(n)。

- Mark Byers

---

还要注意的是，键不一定是字符串或字符。大多数情况下是这样，但它们也可以是指针（除了字符串是指针的事实），结构体或其他数据类型。 - user142019

Answer 3

一个哈希可以快速查找，而不需要遍历数组或树。它使得在很少使用内存的情况下，能够以O(1)时间搜索。

- fastcodejava