fin*_*nnw
15
algorithm
hashtable
我有一个哈希表,其中运行时的绝大多数访问遵循以下模式之一:
- 迭代所有键/值对.(此操作的速度至关重要.)
- 修改键(即删除一个键/值对并添加另一个具有相同值但另一个键不同的键.检测重复键并在必要时组合值.)这是在一个循环中完成的,影响了数千个键,但没有其他操作介入.
我也希望它尽可能少地消耗内存.
必须提供其他标准操作,尽管使用频率较低,例如
- 插入新的键/值对
- 给定一个键,查找相应的值
- 更改与现有密钥关联的值
当然,所有"标准"哈希表实现(包括大多数高级语言的标准库)都具有所有这些功能.我正在寻找的是针对第一个列表中的操作进行优化的实现.
常见实现的问题:
- 大多数哈希表实现都使用单独的链接(即每个存储桶的链接列表.)这有效但我希望能够占用更少内存并具有更好的引用局部性的东西.注意:我的密钥很小(每个13个字节,填充到16个字节.)
- 大多数开放式寻址方案对我的应用程序都有一个主要的缺点:键被删除并以大组替换.这留下了删除标记,增加了负载因子,需要经常重建表.
有效的方案,但不太理想:
- 每个桶与一个数组(而不是链表)分开链接:
引用的局部性差,因为内存碎片导致小数组重新分配多次
- 线性探测/二次散列/双重散列(有或没有Brent的变化):
表格快速填满删除标记
- Cuckoo散列
只适用于<50%的负载系数,我想要一个高LF来节省内存并加快迭代速度.
是否有专门的散列方案可以适用于这种情况？
注意:我有一个很好的哈希函数,适用于2的幂和素数表大小,并且可以用于双重哈希,所以这不应该是一个问题.