linux hash表的桶數(shù)量的確定

xiegang112

linux的hash函數(shù)hash_long等，用了golden ratio來計(jì)算。因?yàn)橥?bits)的數(shù)量需要由hash函數(shù)和對(duì)沖突的期望來決定，那么對(duì)于hash_long這樣的hash函數(shù)，我們?cè)趺创_定桶的數(shù)量呢？有兄弟在項(xiàng)目中用過嗎？能具體講講分析過程嗎？
謝謝

platinum

一般情況下都是自己根據(jù)數(shù)據(jù)特性來考慮使用的 hash 算法，不是千篇一律咬死一個(gè)不放
比如存放 IP 地址的 hash table，用一個(gè) 65536 的桶就很好，把 IP 的后 16bit 作為 key
這種方法絕對(duì)比 hash_long、jhash 等函數(shù)的碰撞率低

xiegang112

有道理，我教條了。 不過，你說的這個(gè)情況是在n一定得時(shí)候。我的情況n的范圍并不太固定。

Godbach

非常贊同白金兄的說法。

platinum

原帖由 xiegang112 于 2009-7-21 13:15 發(fā)表
有道理，我教條了。 不過，你說的這個(gè)情況是在n一定得時(shí)候。我的情況n的范圍并不太固定。

也不是啊，加入有一個(gè)收集 IP 的 hash table，那么 IP 數(shù)有可能到多少我也不清楚
為什么說適用于 n 一定的時(shí)候呢？

Godbach

原帖由 platinum 于 2009-7-21 16:25 發(fā)表

也不是啊，加入有一個(gè)收集 IP 的 hash table，那么 IP 數(shù)有可能到多少我也不清楚
為什么說適用于 n 一定的時(shí)候呢？

我覺得LZ的意思是不是至少這個(gè)IP的集合是確定的，頂多2^32個(gè)IP地址。

platinum

原帖由 Godbach 于 2009-7-21 17:01 發(fā)表


我覺得LZ的意思是不是至少這個(gè)IP的集合是確定的，頂多2^32個(gè)IP地址。

如果這樣的話，那盡量考慮得大一些吧
其實(shí)幾乎沒有不能確定總數(shù)量的情況，什么都有個(gè) “界”，真的無限的話，存儲(chǔ)空間也不夠啊
比如 conntrack，人為是限制有 max 的

Godbach

原帖由 platinum 于 2009-7-21 17:23 發(fā)表

如果這樣的話，那盡量考慮得大一些吧
其實(shí)幾乎沒有不能確定總數(shù)量的情況，什么都有個(gè) “界”，真的無限的話，存儲(chǔ)空間也不夠啊
比如 conntrack，人為是限制有 max 的

是的。具體應(yīng)用中，是肯定要根據(jù)經(jīng)驗(yàn)或者相關(guān)的數(shù)據(jù)來設(shè)置一個(gè)最大值的。這個(gè)最大值應(yīng)該適合你的設(shè)備的指標(biāo)相關(guān)的。

epegasus

我以前寫的關(guān)于表的查找又加入了cache的功能,計(jì)算機(jī)里學(xué)的到的最近作用原理,先在cache里找,找不到再在hash里面去找.

xiegang112

是的，其實(shí)就是這個(gè)界和性能的折中。我可以取我問題空間的最大值。這樣肯定能保證鍵值分散。但是這樣會(huì)浪費(fèi)很多空間。然而取得太小，又影響查找效率。感覺還是要在試驗(yàn)中進(jìn)行測試。而且個(gè)人覺得，hash比其他搜索的數(shù)據(jù)結(jié)構(gòu)靈活的地方就是它的可定制性。可以根據(jù)具體情況調(diào)整，以達(dá)到最優(yōu)的效果。搜索到一篇論文：Linux Kernel Hash Table Behavior: Analysis and Improvements。感覺分析的很好。