统一散列函数 [英] Uniform hashing functions

问题描述

哈希表基本知识： - 重大考验来了。所有帮助将AP preCIATED。

我基本上上的按键均匀散列有点糊涂了。

  ----------------------
| X X X＆所述; ===链; X重新$ P $中有psents项目
----------------------
| XXX＆LT; === x倍数再presents碰撞
----------------------
|
----------------------
| X X X
----------------------
| X
----------------------
 

1. 考虑以上哈希表的情况下，M = 5（行NUM），总长度为10，我怎么会知道这是哈希表均匀散或不？

2. 如果人让一组按键的均匀散列，这是否意味着在哈希表又名链接列表中的链内的名单，由于碰撞具有相同的长度？还是意味着平均？

3. 如果人让按键的均匀散列，是否意味着找到并删除此哈希表的功能是O（1）（摊销）和纯的O（N / M）的复杂性，其中M是多少在总共链？

4. 请问负荷率或（N /​​＃ofChains）确定散列的一致性？

我希望你能帮我看看这些题。我的教授已经投入了大量的概念在课堂上，我基本上只是弯曲在一起在这里，我被弄糊涂，当我把这些概念放在一起。

我正在寻找在网络上进行更多的研究关于这个概念，我看到了一组幻灯片，如下图所示。如果您什么公式是指在第二张幻灯片相对于按键的均匀散列

我将不得不能向我解释

同时，当他们说这是什么意思键映射到每个插槽的数量是相等的。有没有去说，我的哈希表上面显示是不是uniformily哈希？

感谢您

解决方案

幻灯片在谈论密钥的所有可能的值。重要的是要认识到，在你的HashMap的，你只有钥匙的一个子集，在任何给定的时间。不管如何好你的散列函数，你可能会幸运地在如何将这些键映射到水桶，或者你可能不。

  

1）考虑上述的哈希表的情况下，其中M行= 5（NUM）和总长度为10，如何将知道这是哈希表被均匀散列或不？

均匀散列是散列函数的性质，而不是的哈希表。因此，只要看看哈希表中的内容，你不能。你要看看哈希函​​数本身在建立它是否是均匀的。

  

2）如果一个人做了一组按键的均匀散列，这是否意味着在哈希表又名链接列表中的链内的名单，由于碰撞具有相同的长度？还是意味着平均水平。

这意味着平均。

  

3）如果一个人做按键的均匀散列，是否意味着找到并删除在O（1）（摊销此哈希表的功能）和一个纯粹的O（N / M）的复杂性，其中M是多少连锁店总数。

在除了散列函数的特性，复杂性也取决于负载因子。如果桶的数量中的元素数量线性增长，你会得到 O（1）找到并删除平均（只要您摊销重新瓢泼大雨适当）。

Hash table basics: - MAJOR TEST COMING UP. ALL HELP WOULD BE APPRECIATED.

I am basically a bit confused on uniform hashing of keys.

----------------------
| X X X                    <=== Chains; X represents an item in there
----------------------
| X X X                    <=== Multiple X represents collisions
---------------------- 
| 
----------------------
| X X X
----------------------
| X
----------------------

1. Consider the case of the above hash table where M = 5 (num of rows) and the total length to be 10. How would I know if this is hash table is uniformly hashed or not?

2. If one makes a uniform hashing of a set of keys, does that mean the lists inside the chains in a hashtable aka the linked-lists due to collisions have the same length? Or does it mean the average?

3. If one makes a uniform hashing of keys, does that mean the find and remove functions of this hashtable are O(1) (amortized) and a pure complexity of O(n/M) where M is the number of chains in total?

4. Does the load factor or (N/#ofChains) identify the uniformity of the hashing?

I hope you can help me with these questions. My professor had put a lot of concepts out in class and I am just basically bending them together here and I am getting confused when I put these concepts together.

I was searching on the web for more to study about this concept and I saw a set of slides as shown below. I would be obliged if you can explain to me what the equation means in the second slide in relation to uniform hashing of keys.

Also, what does it mean when they say "the number of keys that map to each slot are equal." Does go to say that my hashtable that is shown above is NOT uniformily hashed?

Thank you

解决方案

The slide is talking about all possible values of keys. It's important to realize that in your hashmap, you only have a subset of keys at any given time. Regardless of how good your hash function is, you might be lucky in how those keys map to buckets, or you might be not.

1) Consider the case of the above hash table where M = 5 (num of rows) and the total length to be 10. How would I know if this is hash table is uniformly hashed or not?

Uniform hashing is a property of the hash function, not of the hash table. Therefore, just by looking at the contents of the hash table, you can't. You have to look at the hash function itself to establish whether or not it's uniform.

2) If one makes a uniform hashing of a set of keys, does that mean the lists inside the chains in a hashtable aka the linked-lists due to collisions have the same length? Or does it mean the average.

It means on average.

3) If one makes a uniform hashing of keys, does that mean the find and remove functions of this hashtable are O(1) (amortized) and a pure complexity of O(n/M) where M is the number of chains in total.

In addition to the properties of the hash function, complexity also depends on the load factor. If the number of buckets grows linearly in the number of elements, you get O(1) find and remove on average (as long as you amortize re-bucketing appropriately).

这篇关于统一散列函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！