linux hash表的桶数量的确定

xiegang112

linux的hash函数hash_long等，用了golden ratio来计算。因为桶(bits)的数量需要由hash函数和对冲突的期望来决定，那么对于hash_long这样的hash函数，我们怎么确定桶的数量呢？有兄弟在项目中用过吗？能具体讲讲分析过程吗？
谢谢

platinum

一般情况下都是自己根据数据特性来考虑使用的 hash 算法，不是千篇一律咬死一个不放
比如存放 IP 地址的 hash table，用一个 65536 的桶就很好，把 IP 的后 16bit 作为 key
这种方法绝对比 hash_long、jhash 等函数的碰撞率低

xiegang112

有道理，我教条了。 不过，你说的这个情况是在n一定得时候。我的情况n的范围并不太固定。

Godbach

非常赞同白金兄的说法。

platinum

原帖由 xiegang112 于 2009-7-21 13:15 发表
有道理，我教条了。 不过，你说的这个情况是在n一定得时候。我的情况n的范围并不太固定。

也不是啊，加入有一个收集 IP 的 hash table，那么 IP 数有可能到多少我也不清楚
为什么说适用于 n 一定的时候呢？

Godbach

原帖由 platinum 于 2009-7-21 16:25 发表

也不是啊，加入有一个收集 IP 的 hash table，那么 IP 数有可能到多少我也不清楚
为什么说适用于 n 一定的时候呢？

我觉得LZ的意思是不是至少这个IP的集合是确定的，顶多2^32个IP地址。

platinum

原帖由 Godbach 于 2009-7-21 17:01 发表


我觉得LZ的意思是不是至少这个IP的集合是确定的，顶多2^32个IP地址。

如果这样的话，那尽量考虑得大一些吧
其实几乎没有不能确定总数量的情况，什么都有个 “界”，真的无限的话，存储空间也不够啊
比如 conntrack，人为是限制有 max 的

Godbach

原帖由 platinum 于 2009-7-21 17:23 发表

如果这样的话，那尽量考虑得大一些吧
其实几乎没有不能确定总数量的情况，什么都有个 “界”，真的无限的话，存储空间也不够啊
比如 conntrack，人为是限制有 max 的

是的。具体应用中，是肯定要根据经验或者相关的数据来设置一个最大值的。这个最大值应该适合你的设备的指标相关的。

epegasus

我以前写的关于表的查找又加入了cache的功能,计算机里学的到的最近作用原理,先在cache里找,找不到再在hash里面去找.

xiegang112

是的，其实就是这个界和性能的折中。我可以取我问题空间的最大值。这样肯定能保证键值分散。但是这样会浪费很多空间。然而取得太小，又影响查找效率。感觉还是要在试验中进行测试。而且个人觉得，hash比其他搜索的数据结构灵活的地方就是它的可定制性。可以根据具体情况调整，以达到最优的效果。搜索到一篇论文：Linux Kernel Hash Table Behavior: Analysis and Improvements。感觉分析的很好。