哈希:它在内部是如何工作的? [英] Hash : How does it work internally?

问题描述

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

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

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

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

解决方案

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

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

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

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

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

This might sound as an very vague question upfront but it is not. I have gone through Hash Function description on wiki but it is not very helpful to understand.

I am looking simple answers for rather complex topics like Hashing. Here are my questions:

1. What do we mean by hashing? How does it work internally?
2. What algorithm does it follow ?
3. What is the difference between HashMap, HashTable and HashList ?
4. What do we mean by 'Constant Time Complexity' and why does different implementation of the hash gives constant time operation ?
5. Lastly, why in most interview questions Hash and LinkedList are asked, is there any specific logic for it from testing interviewee's knowledge?

I know my question list is big but I would really appreciate if I can get some clear answers to these questions as I really want to understand the topic.

解决方案

1. Here is a good explanation about hashing. For example you want to store the string "Rachel" you apply a hash function to that string to get a memory location. myHashFunction(key: "Rachel" value: "Rachel") --> 10. The function may return 10 for the input "Rachel" so assuming you have an array of size 100 you store "Rachel" at index 10. If you want to retrieve that element you just call GetmyHashFunction("Rachel") and it will return 10. Note that for this example the key is "Rachel" and the value is "Rachel" but you could use another value for that key for example birth date or an object. Your hash function may return the same memory location for two different inputs, in this case you will have a collision you if you are implementing your own hash table you have to take care of this maybe using a linked list or other techniques.

2. Here are some common hash functions used. A good hash function satisfies that: each key is equally likely to hash to any of the n memory slots independently of where any other key has hashed to. One of the methods is called the division method. We map a key k into one of n slots by taking the remainder of k divided by n. h(k) = k mod n. For example if your array size is n = 100 and your key is an integer k = 15 then h(k) = 10.

3. Hashtable is synchronised and Hashmap is not. Hashmap allows null values as key but Hashtable does not.

4. The purpose of a hash table is to have O(c) constant time complexity in adding and getting the elements. In a linked list of size N if you want to get the last element you have to traverse all the list until you get it so the complexity is O(N). With a hash table if you want to retrieve an element you just pass the key and the hash function will return you the desired element. If the hash function is well implemented it will be in constant time O(c) This means you dont have to traverse all the elements stored in the hash table. You will get the element "instantly".

5. Of couse a programer/developer computer scientist needs to know about data structures and complexity =)

这篇关于哈希:它在内部是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！