Syd*_*ove 5 hash haskell hashmap hashable unordered-containers
在处理哈希映射时,我已经看到了一些处理哈希冲突的策略,但我们提出了一些不同的东西.我想知道这是否是新事物.
只有散列和将要散列的数据结构可以使用时,此版本的散列映射才有效.(hashable在Haskell中就是这种情况,我们建议实现这种方法.)
我们的想法是,不是在哈希映射的每个单元格中存储列表或数组,而是存储递归哈希映射.这个递归哈希映射的唯一区别是你使用不同的盐.这样,哈希映射的一个级别上的哈希冲突很可能不是下一级别的哈希冲突.因此,插入这样的哈希映射不再是O(此哈希上的冲突数),而是O(这种冲突在递归时发生的级别数),这很可能更好.
可以在此处找到更详细的说明和实现:
您的想法似乎与1984 年 Fredman、Koml\xc3\xb3s & Szemer\xc3\xa9di 论文中提出的想法实际上相同。正如维基百科总结的那样：
\n\n\n\n\nFKS 哈希使用具有两级的哈希表，其中顶层包含 n 个桶，每个桶都包含自己的哈希表。
\n
与您的想法相反，本地哈希映射不是递归的，而是每个哈希映射都选择一个使其成为完美哈希的盐。在实践中，这（正如你所说）通常已经由你尝试的第一个盐给出，因此它是渐近恒定时间的。
\n