数组大小可扩展散列 [英] array size for extendible hashing
问题描述
如果我想使用可扩展散列存储最多100条记录，那么我需要的最小数组大小是多少？
If I want to use extendible hashing to store a maximum of 100 records, then what is the minimum array size that I need?
我猜数组的100就足够了，但我可能错了。我还怀疑我可以使用更小的数组。
I am guessing that an array of 100 would be sufficient, but I could be wrong. I also suspect that I can use a smaller array.
推荐答案
你知道你的哈希函数是什么？
What do you know about your hash function?
您提到了可扩展散列。
使用可扩展散列法，您可以将散列看作位串，通常通过特里结构实现桶查找。
You mentioned extendible hashing.
With extendible hashing you look at your hash as a bit string and typically implement the bucket lookup via a trie. Instead of a trie based lookup though I assume you are converting this to an index into your array.
你提到你最多只能有100个元素，而不是基于trie的查找。如果你想要所有不同的哈希值，你将有128种可能性，因为这是与7位的位的最接近的组合。
You mentioned you will have at most 100 elements. If you wanted all distinct hashes you'd have 128 possibilities since that's the closest combination of bits with 7 bits.
如果你的哈希函数可以哈希每个元素有7 7（或更多）不同的位，那么你有一个桶大小为1的最优解。留下128个叶节点或一个大小为128的数组。
If your hashing function can hash each element to have 7 of 7 (or more) different bits, then you have the most optimal solution with a bucket size of 1. Leaving 128 leaf nodes, or an array of size 128.
你的哈希函数可以哈希每个元素有6的7（或更多）不同的位，那么你有一个桶大小2.你有64叶节点/组合/数组大小。
If your hashing function can hash each element to have 6 of 7 (or more) different bits, then you have a bucket size of 2. You would have 64 leaf nodes/combinations/array size.
如果你的哈希函数可以哈希每个元素有5的7（或更多）不同的位，那么你有一个桶大小为4.你有32叶节点/组合/数组大小。
If your hashing function can hash each element to have 5 of 7 (or more) different bits, then you have a bucket size of 4. You would have 32 leaf nodes/combinations/array size.
因为你说你想要桶大小为4我认为你的答案将是32，你有一个严格的要求，你有一个良好的散列函数，可以给你至少5第一位是不同的。
Since you said you want a bucket size of 4 I think your answer would be 32 and you have a hard requirement that you have a good hashing function that can give you at least 5 of the first bits as distinct.
这篇关于数组大小可扩展散列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
