linux hash表的桶数量的确定

xiegang112

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

Godbach

， google的第一个结果就是这篇PDF文档

xiegang112

11楼已经贴上了：）

emmoblin

能把那片论文分享一下吗？
我google了一下没g到

platinum

原帖由 xiegang112 于 2009-7-21 18:54 发表
而且个人觉得，hash比其他搜索的数据结构灵活的地方就是它的可定制性。可以根据具体情况调整，以达到最优的效果。

说得没错，其实可以根据实际情况动态调整 bucket 大小，实现空间/效率的最好结合点

Godbach

网上搜了一下这篇文章，还有一些对比数据，这里把原文上传了。

xiegang112

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

epegasus

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

Godbach

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

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

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

platinum

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


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

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