哈希：它在内部是如何工作的？

Question

这似乎是一个非常模糊的问题，但实际上不是。我已经浏览了维基百科上关于哈希函数的描述，但它并没有很有用。

我正在寻找像哈希等复杂主题的简单答案。下面是我的问题：

1. 哈希是什么？它是如何在内部工作的？
2. 它遵循什么算法？
3. HashMap、HashTable 和 HashList 有什么区别？
4. 什么是“常数时间复杂度”，为什么哈希的不同实现能够给出常数时间操作？
5. 最后，为什么在大多数面试问题中都会问到 Hash 和 LinkedList，这有没有一些特定的逻辑来测试面试者的知识？

我知道我的问题列表很长，但如果我能得到这些问题的清晰答案，我将不胜感激，因为我真的想理解这个主题。

- Rachel

---

请尝试在维基百科上查看哈希表。哈希函数是该过程的一部分，但不解释哈希表的工作原理。 - user166390

在我所知道的Java或任何其他语言中，都没有“HashList”这样的东西。不要对非代码文本使用代码格式。 - user207421

Answer 1

1. 这里有一个关于哈希的好解释。例如，你想要存储字符串"Rachel"，你需要对这个字符串应用一个哈希函数来获取一个内存位置。myHashFunction(key: "Rachel" value: "Rachel") --> 10。函数可能会返回输入"Rachel"的10，所以假设你有一个大小为100的数组，你可以将"Rachel"存储在索引10处。如果你想要检索该元素，只需调用GetmyHashFunction("Rachel")，它会返回10。注意，对于这个例子，键是"Rachel"，值也是"Rachel"，但你也可以使用另外一个值作为键，比如生日或对象。如果你的哈希函数返回相同的内存位置用于两个不同的输入，则会发生冲突。如果你正在实现自己的哈希表，你必须处理冲突，可能使用链表或其他技术。

2. 这里有一些常用的哈希函数。好的哈希函数满足：每个键被等概率地散列到任意一个内存单元中，与其他键的散列结果无关。其中一个方法称为除法法。我们通过计算k除以n的余数，将键k映射到n个槽中的一个。h(k) = k mod n。例如，如果你的数组大小是n = 100，键是整数k = 15，那么h(k) = 10。

3. Hashtable是同步的，而HashMap不是。HashMap允许null值作为键，但Hashtable不允许。

哈希表的目的是为了在添加和获取元素时拥有O(c)常数时间复杂度。在大小为N的链表中，如果要获取最后一个元素，必须遍历整个链表，因此时间复杂度为O(N)。而使用哈希表，如果你想检索一个元素，只需要传递关键字，哈希函数将返回所需的元素。如果哈希函数实现良好，它将以常数时间O(c)运行，这意味着你不需要遍历存储在哈希表中的所有元素，你将“立即”获得该元素。

当然，程序员/开发人员和计算机科学家需要了解数据结构和时间复杂度 =)

- Enrique

---

你提供的两个链接都带我到了维基页面，而我已经访问过并在问题中提到了它们，所以你能否更新你的前两点？ - Rachel

感谢您更新答案，现在我能够更好地理解它。 - Rachel

不存在“O(c)时间复杂度”这样的概念：你应该是指O(1)。 - user207421

Answer 2

1. 哈希是生成一个（有望）唯一表示某个值的数字。
2. 不同类型的值（如整数、字符串等）使用不同的算法来计算哈希码。
3. HashMap和HashTable是映射表；它们是由一组唯一键和与之关联的值组成的集合。
   Java 没有HashList类，而 HashSet则是由一组唯一值组成的集合。
4. 从哈希表中获取项是与表的大小成常量时间的操作。
   计算哈希码不一定随值的大小具有常量时间性能。
   例如，计算字符串的哈希码涉及到遍历字符串，其计算时间与字符串长度相关，因此不具有常量时间性能。
5. 这些都是人们应该知道的事情。

- SLaks

---

不，不可能。为每个可能的字符串生成唯一的32位数字是不可能的。这就是为什么会存在冲突。 - SLaks

@Rachel：哈希不会尝试生成唯一的数字。它试图创建一个均匀分布的输出，以便每个输出值大致具有“1 /可能哈希值数量”的概率。 - ruslik

@ColinD：哦，你说得对。我的评论并不是针对Java，而是哈希总体而言的。我必须承认我从来没有在Java中使用过哈希码。 - Juri Robl

@Rachel - ruslik的意思是：哈希函数输出一个数字，而该数字处于特定数字范围内。例如，该数字可能在0至2^32-1之间。当您哈希一些数据时，会返回该范围内的一个数字，并且理想情况下每个可能的数字都有同等概率被返回。哈希表/映射需要这样做的原因是，可以将表视为数组。当您哈希一个值时，您使用该数字作为数组中的索引。您希望避免重复使用相同的索引。如果数字均匀分布，则碰撞的可能性较小。 - Niki Yoshiuchi

哈希是指从一个范围较大的输入中生成一个相对较小范围内的数字，希望哈希值分布均匀。唯一性不是显式的目标。 - user207421

Answer 3

我将尝试对哈希及其目的进行简单的解释。

首先，考虑一个简单的列表。在这样的列表上进行每个操作（插入、查找、删除）的时间复杂度为O(n)，这意味着您必须遍历整个列表（或平均遍历一半）才能执行此类操作。

哈希是一种非常简单而有效的加速方法：我们将整个列表分成一组小列表。一个小列表中的项将具有某些共同点，可以从密钥中推断出这些共同点。例如，通过使用名称列表，我们可以使用第一个字母作为选择要查找哪个小列表的质量。通过按密钥的第一个字母对数据进行分区，我们获得了一个简单的哈希，可以将整个列表划分为大约30个较小的列表，以便每个操作需要O(n)/30的时间。

然而，我们可以注意到结果并不完美。首先，只有30个结果，我们无法更改它。其次，某些字母比其他字母更常用，因此具有“Y”或“Z”的集合将比具有“A”的集合小得多。为了获得更好的结果，最好找到一种在大致相同大小的集合中分割项目的方法。我们如何解决这个问题？这就是使用哈希函数的地方。这是一种能够创建大约具有相同数量项的任意分区的函数。在我们的名称示例中，我们可以使用类似以下的内容：

int hash(const char* str){
    int rez = 0;
    for (int i = 0; i < strlen(str); i++)
        rez = rez * 37 + str[i];
    return rez % NUMBER_OF_PARTITIONS;
};

这将确保相当均匀的分布和可配置的集合数量（也称为桶）。

- ruslik

Answer 4

1. 哈希是将给定实体（在Java术语中-一个对象）转换为一些数字（或序列）。哈希函数是不可逆的，即您无法从哈希中获取原始对象。在内部，它通过JVM获取某些内存地址来实现（对于java.lang.Object）。

2. JVM地址是不重要的细节。每个类都可以使用自己的算法覆盖hashCode()方法。现代Java IDE允许生成良好的hashCode方法。

3. Hashtable和HashMap是相同的东西。它们是键值对，其中键被散列。Hash列表和哈希集不存储值-只存储键。

4. 恒定时间意味着无论hashtable（或任何其他集合）中有多少条目，找到给定对象的关键字所需的操作数都是恒定的。也就是说-1，或接近1。

5. 这是基本的计算机科学材料，假定每个人都熟悉它。我认为谷歌已经指定了hashtable是计算机科学中最重要的数据结构。

- Bozho

---

你能否举例说明从长整型生成哈希码函数的算法实现？同时，我在面试中被问到生成哈希码的算法是什么，但我不确定当前内部工作原理，因此想要了解它是如何在内部完成的。 - Rachel

你可以查看 java.lang.Long 的文档 - 代码只有一行：return (int)(value ^ (value >>> 32)); - Bozho

Answer 5

什么是哈希，它在内部如何工作？

哈希是将字符串转换为表示原始字符串的短固定长度值或键。它不是索引。哈希的核心是哈希表。它包含项目数组。哈希表包含数据项键的索引，并使用此索引将数据放入数组中。

它遵循什么算法？

简单来说，大多数哈希算法都遵循“index = f(key, arrayLength)”的逻辑。

最后，为什么在大多数面试问题中会问到哈希和链表，有没有特定的逻辑来测试面试者的知识？

这涉及您在逻辑推理方面的能力。这是每个程序员都必须掌握的最重要的数据结构。

- user517400