哈希表+二进制搜索

我正在使用哈希表来存储一些值。这里是详细信息：哈希表+二进制搜索

将有大约1M项存储（以前不知道，所以没有完美的哈希可能）。
表是10M大。
散列函数是MurMurHash3。

我做了一些测试并存储1M值我在碰撞最大的散列表的插槽中得到了350,000个冲突和30个元素。

这些结果是好的吗？

对于在碰撞散列表插槽处创建的列表实现二进制搜索是否合理？

您对改善表演有何建议？

编辑：这里是我的代码

var 
    HashList: array [0..10000000 - 1] of Integer; 

for I := 0 to High(HashList) do 
    HashList[I] := 0; 

for I := 1 to 1000000 do 
begin 
    Y := MurmurHash3(UIntToStr(I)); 
    Y := Y mod Length(HashList); 
    Inc(HashList[Y]); 
    if HashList[Y] > 1 then 
    Inc(TotalCollisionsCount); 
    if HashList[Y] > MostCollidingSlotItemCount then 
    MostCollidingSlotItemCount := HashList[Y]; 
end; 

Writeln('Total: ' + IntToStr(TotalCollisionsCount) + ' Max: ' + IntToStr(MostCollidingSlotItemCount));

下面是结果我得到：

Total: 48169 Max: 5

我缺少的东西？

来源

2015-11-14 Alex

1）您是否在10M盒子上分配了1M项目？ 2）你对碰撞的定义是什么？ – wildplasser

1）是 2）映射到表中相同插槽的两个不同键 – Alex

随机填充时每个单元的预期元素数：0：9048K 1：905K 2：45K 3：1K5 4:50结论：您的散列函数是可怕的（或您的数据包含重复项） – wildplasser

这是当你把100万件随机到10M细胞

calendar_size=10000000 nperson = 1000000 
E/cell| Ncell | frac | Nelem | frac |h/cell| hops | Cumhops 
----+---------+--------+----------+--------+------+--------+-------- 
    0: 9048262 (0.904826)  0 (0.000000)  0  0  0 
    1: 905064 (0.090506) 905064 (0.905064)  1 905064 905064 
    2: 45136 (0.004514) 90272 (0.090272)  3 135408 1040472 
    3:  1488 (0.000149)  4464 (0.004464)  6  8928 1049400 
    4:  50 (0.000005)  200 (0.000200) 10  500 1049900 
----+---------+--------+----------+--------+------+--------+-------- 
    5: 10000000    1000000    1.049900 1049900

左栏你得到的是在电池的项目数。第二个：拥有此itemcount的单元格数量。

WRT二进制搜索：很明显，对于像这样的小的表（最大链长= 4，但大多数链长度= 1），线性搜索优于二进制搜索。接管点可能介于10到100之间。

来源

2015-11-14 20:40:06 wildplasser

哈希表+二进制搜索

回答

相关问题