java - 哈希 : How does it work internally?

Question

这听起来像是一个非常模糊的问题，但事实并非如此。我经历过Hash Function wiki上的描述，但理解起来不是很有帮助。

我正在为诸如散列等相当复杂的主题寻找简单的答案。以下是我的问题:

1. 散列是什么意思？它在内部是如何运作的？
2. 它遵循什么算法？
3. HashMap、HashTable和HashList有什么区别？
4. “恒定时间复杂度”是什么意思？为什么哈希的不同实现会给出恒定时间操作？
5. 最后，为什么在大多数面试问题中都会问Hash和LinkedList，从测试面试者的知识来看，有什么具体的逻辑吗？

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

Answer 1

1. Here是关于散列的一个很好的解释。例如，您想存储字符串“Rachel”，您对该字符串应用哈希函数以获取内存位置。 myHashFunction(key: "Rachel"value: "Rachel") --> 10.该函数可能会为输入“Rachel”返回 10，因此假设您有一个大小为 100 的数组，您将“Rachel”存储在索引 10 处。如果您想检索该元素，您只需调用 GetmyHashFunction("Rachel") 它将返回 10。请注意，对于此示例，键是“Rachel”，值是“Rachel”，但您可以为该键使用另一个值，例如出生日期或对象。您的哈希函数可能会为两个不同的输入返回相同的内存位置，在这种情况下，如果您正在实现自己的哈希表，您可能会遇到冲突，您可能需要使用链表或其他技术来处理这个问题。

2. Here是一些常用的散列函数。一个好的散列函数满足:每个键都有可能散列到 n 个内存槽中的任何一个，而与任何其他键散列到的位置无关。其中一种方法称为除法。我们通过将 k 的余数除以 n 将 key k 映射到 n 个插槽之一。 h(k) = k mod n。例如，如果您的数组大小是 n = 100 并且您的键是整数 k = 15 那么 h(k) = 10。

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

4. 哈希表的目的是在添加和获取元素时具有 O(c) 恒定的时间复杂度。在大小为 N 的链表中，如果要获取最后一个元素，则必须遍历所有列表直到得到它，因此复杂度为 O(N)。使用哈希表，如果您想检索一个元素，您只需传递键，哈希函数将返回您所需的元素。如果哈希函数实现得很好，它将在恒定时间内 O(c) 这意味着您不必遍历存储在哈希表中的所有元素。您将“立即”获得元素。

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