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

algorithm data-structures java hash

2022-08-31 16:13:35

这可能听起来像是一个非常模糊的问题，但事实并非如此。我已经在wiki上浏览了哈希函数描述，但理解它不是很有帮助。

我正在为像哈希这样相当复杂的主题寻找简单的答案。以下是我的问题：

我们所说的散列是什么意思？它如何在内部工作？
它遵循什么算法？
和之间有什么区别？HashMapHashTableHashList
我们所说的“恒定时间复杂性”是什么意思，为什么哈希的不同实现给出恒定时间运算？
最后，为什么在大多数面试问题中被问到，从测试受访者的知识中是否有任何具体的逻辑？HashLinkedList

我知道我的问题列表很大，但如果我能得到这些问题的一些明确答案，我将不胜感激，因为我真的很想了解这个话题。

答案 1

这是关于散列的一个很好的解释。例如，您要存储字符串“Rachel”，您将哈希函数应用于该字符串以获取内存位置。.该函数可能会为输入“Rachel”返回10，因此假设您有一个大小为100的数组，则将“Rachel”存储在索引10处。如果要检索该元素，只需调用它，它将返回10。请注意，对于此示例，键为“Rachel”，值为“Rachel”，但您可以对该键使用另一个值，例如出生日期或对象。您的哈希函数可能会为两个不同的输入返回相同的内存位置，在这种情况下，如果您要实现自己的哈希表，则必须使用链表或其他技术来处理这个问题。myHashFunction(key: "Rachel" value: "Rachel") --> 10GetmyHashFunction("Rachel")
以下是一些常用的哈希函数。一个好的哈希函数满足这一点：每个密钥都同样可能散列到n个内存插槽中的任何一个，而与任何其他键散列到的位置无关。其中一种方法称为除法。我们将一个关键 k 映射到 n 个槽之一，方法是将 k 的余数除以 n。例如，如果数组大小为整数，则键为整数，则 .h(k) = k mod nn = 100k = 15h(k) = 10
Hashtable是同步的，而Hashmap不是。Hashmap允许空值作为键，但Hashtable不允许。
哈希表的目的是在添加和获取元素时具有 O（c）恒定的时间复杂度。在大小为N的链接列表中，如果要获取最后一个元素，则必须遍历所有列表，直到获得它，因此复杂度为O（N）。使用哈希表，如果要检索元素，只需传递密钥，哈希函数将返回所需的元素。如果哈希函数实现良好，它将处于常量时间O（c）这意味着您不必遍历哈希表中存储的所有元素。您将“立即”获得该元素。
程序员/开发人员计算机科学家需要了解数据结构和复杂性=）

答案 2

散列意味着生成一个（希望）表示值的唯一数字。
不同类型的值（，等）使用不同的算法来计算哈希码。IntegerString
HashMap和HashTable是地图;它们是 unqiue 键的集合，每个键都与一个值相关联。
Java 没有 HashList 类。哈希集是一组唯一值。
从哈希表获取项目是表大小的常量时间。
计算哈希值不一定是要哈希值的常数时间。
例如，计算字符串的哈希涉及迭代字符串，并且相对于字符串的大小不是常量时间。
这些是人们应该知道的事情。