Chinaunix

标题: linux hash表的桶数量的确定 [打印本页]

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

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

作者: xiegang112 时间: 2009-07-21 13:15
标题: 回复 #2 platinum 的帖子
有道理，我教条了。不过，你说的这个情况是在n一定得时候。我的情况n的范围并不太固定。

作者: Godbach 时间: 2009-07-21 13:59
标题: 回复 #2 platinum 的帖子
非常赞同白金兄的说法。

作者: platinum 时间: 2009-07-21 16:25

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

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

作者: Godbach 时间: 2009-07-21 17:01

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

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

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

作者: platinum 时间: 2009-07-21 17:23

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

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

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

作者: Godbach 时间: 2009-07-21 17:44

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

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

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

作者: epegasus 时间: 2009-07-21 17:51
我以前写的关于表的查找又加入了cache的功能,计算机里学的到的最近作用原理,先在cache里找,找不到再在hash里面去找.

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

作者: Godbach 时间: 2009-07-21 19:07
网上搜了一下这篇文章，还有一些对比数据，这里把原文上传了。

Linux Kernel Hash Table Behavior-Analysis and Improvements.pdf

92.88 KB, 下载次数: 142

作者: platinum 时间: 2009-07-21 19:14

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

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

作者: emmoblin 时间: 2009-07-21 23:53
能把那片论文分享一下吗？
我google了一下没g到

作者: xiegang112 时间: 2009-07-22 09:51
标题: 回复 #13 emmoblin 的帖子
11楼已经贴上了：）

作者: Godbach 时间: 2009-07-22 09:54
标题: 回复 #14 xiegang112 的帖子

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

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)