快速哈希函數爲IPv4/6地址

我正在寫C程序，這是設計爲快速。快速哈希函數爲IPv4/6地址

我想存儲數據流中IP地址的出現次數。例如，我將分析100MB二進制文件，其中包含大約2 000 000個IP地址（但也許程序也將用於x-GB文件）。

我的想法是使用哈希表，所以我需要這些散列函數：

20b_int indexToIPv4HashTable = hashIPv4(32b_int addr4); 
20b_int indexToIPv6HashTable = hashIPv6(128b_int addr6);

我想是不是當這功能將有碰撞有時問題（我會解決這個使用單獨的鏈接）。

我應該使用哪些散列函數？
這個問題使用散列表是個好主意嗎？

小數學：

20b的索引= 1層048 576的元件（是否足夠？）
32B元素= 4B元素= 4MB表大小（是這樣的尺寸確定，當程序將在當前計算機上運行）

注： IP地址可能指定了一個掩碼。例如：IPv4/24 - >現在只有2^24個不同的IPv4地址，而不是2^32。 當設置掩碼時，我應該使用不同的散列表大小嗎？

絕對優先級是速度。

來源

2014-02-27 Bambo

addr [i]和addr [i + n]之間是否有任何相關性，其中n很小？當確定散列函數必須對比特進行加擾時，這可能是一個至關重要的因素。在I7中，在速度上很難擊敗crc32指令（或多項式乘法的組合），但它的整體性能很重要。 –

順便說一句，我假設你的意思是4Gb，而不是4Mb的32位索引大小以上。此外，假定您只需要每個條目一個字節（最多255個點擊）

如果不知道地址分配情況，很難知道哪個散列會更好。如果它們或多或少地隨機分佈在地址空間中（並且，是的，我知道大多數IPv6地址未分配），只需選取幾位地址並使用它即可。

作爲一個例子，選擇5個4位區域均勻分佈在ipv4的地址中，最低16位+4位從中間某個地方分配給v6。

但是，如果您使用crc32指令的現代x86幾乎肯定會產生足夠好的散列，並且速度很快。

#define HASH_MASK ((1<<20)-1) 

static inline int hash32(unsigned int foo) 
{ 
    return __builtin_ia32_crc32si(0, foo) & HASH_MASK; 
} 

static inline int hash128(const char *data) 
{ 
    int res = 0, i; 
    for(i=0; i<4; i++, data+=4) 
    res = __builtin_ia32_crc32si(res, *(int32_t *)data); 
    return res & HASH_MASK; 
}

注意，這是不可移植的高度，它不僅只在x86工作，它僅適用於某些x86上（它也需要-msse4.2如果你正在使用gcc）。

一注：除非您每秒處理大量條目（我的意思是很多），散列函數的速度不太可能有關係。數據在散列桶中的傳播可能會影響事物，但即使鏈接列表存儲桶散列表的一個簡單的非調整大小的實現，也將能夠每秒處理至少數億次點擊，除非鏈接達到100 +長。實際上，讀取文件的硬盤驅動器的速度很可能是限制因素。

來源

2014-02-27 13:45:09 perh

快速哈希函數爲IPv4/6地址

回答

相關問題