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

问题描述

这听起来是一个非常模糊的问题，前期但它不是。我已经通过维基 Hash函数说明走了，但它是不是非常有帮助理解。

我要寻找简单的答案相当复杂的主题，如散列，这里是我的问题：

1. 什么是我们通过散列，它是如何工作的内部？
的意思
2. 什么算法它遵循 ？
3. 有什么区别？的HashMap，Hashtable和HashList
4. 什么是我们所说的恒时间复杂度？为什么不同的实施散列给人恒定的时间操作？
5. 最后，为什么在大多数的面试问题哈希和LinkedList 被询问，是否有任何具体的逻辑从测试受访者的知识？

我知道我的问题清单是很大，但真的很AP preciate如果我能得到一些明确的回答这个问题，因为我真的想了解散列主题。

感谢。

解决方案

1. 这里约为散列一个很好的解释。比如你想你的哈希函数应用于该字符串得到一个存储单元中存储字符串瑞秋。 myHashFunction（重点：瑞秋的价值：瑞秋） - ＆GT; 10 。该函数可以返回10输入瑞秋，所以假设你有大小100你存储瑞秋在索引10的阵列。如果你想找回你只需要调用 GetmyHashFunction（瑞秋这个元素），它将返回10。注意，在这个例子中，关键是瑞秋，值为瑞秋，但你可以用另一种价值的关键，例如出生日期或对象。您的哈希函数可以返回相同的存储位置，两个不同的输入，在这种情况下，你将有一个碰撞，你如果要实现自己的哈希表你有可能使用链表或其他技术来照顾这一点。

2. 这里是常用的一些哈希函数。一个好的散列函数满足的是：每个键等可能地散列到任何独立的，其中的任何其他键散列以n个存储器槽。其中一种方法就是所谓的划分方法。我们通过取k的其余除以n映射一个密钥k到n个时隙中的一个。 H（K）= K模N 。例如，如果您的数组大小 N = 100 和您的键是整数 K = 15 然后 H（K）= 10 。

3. Hashtable是同步而HashMap不是。 HashMap中允许空值作为重点，但哈希表没有。

4. 的哈希表的目的是使O（三）恒定时间复杂度增加和获取的元素。在大小为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 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屋！