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

问题描述

这可能听起来像是一个非常模糊的问题，但不是。我已经通过wiki上的哈希函数描述，但这不是很有帮助。

我看起来很简单的答案，如 Hashing ，这是我的问题：

1. 我们的意思是什么 Hashing ，它在内部如何工作 code>？


2. 什么算法是否遵循
   ？


3. 有什么区别： HashMap，HashTable和HashList ？


4. 我们的意思是复杂性，为什么 Hash 的不同实现给出常数时间操作？


5. 最后，为什么在大多数采访问题中要求Hash和LinkedList ，是否有任何具体的逻辑来测试访问者的知识？

我知道我的问题列表很大，但真的很感激，如果我可以得到一些明确的答案，这个问题，因为我真的想要了解哈希主题。

谢谢。

解决方案

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




2. 这里是使用的一些常见的哈希函数。一个好的散列函数满足：每个密钥同样可能散列到n个存储器插槽中的任一个，而与任何其他密钥散列的位置无关。其中一种方法称为除法。我们通过将k的余数除以n来将密钥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. 应用程序员/开发人员计算机科学家需要了解数据结构和复杂性=）

   / li>
   

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 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 would really appreciate if I can get some clear answers to this questions as I really want to understand Hash Topic.

Thanks.

解决方案

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屋！