haskell - 这种处理哈希冲突的方法是新的/独特的吗?
问题描述
在处理哈希映射时,我看到了一些处理哈希冲突的策略,但我们想出了一些不同的方法。我想知道这是否是新事物。
此版本的哈希映射仅在哈希和将被哈希的数据结构是可盐化的情况下才有效。hashable
(在 Haskell 中就是这种情况,我们建议实施这种方法。)
这个想法是,不是在哈希映射的每个单元格中存储一个列表或数组,而是存储一个递归哈希映射。此递归哈希映射的唯一区别是您使用不同的盐。这样,哈希映射的一个级别上的哈希冲突很可能不是下一级的哈希冲突。结果,插入这样的哈希映射不再是 O(此哈希上的冲突数),而是 O(此上的冲突以递归方式发生的级别数),这很可能更好。
更详细的解释和实现可以在这里找到:
解决方案
您的想法似乎与1984 年 Fredman、Komlós 和 Szemerédi 论文中建议的想法相同。正如维基百科总结的那样:
FKS Hashing 使用具有两个级别的哈希表,其中顶层包含 n 个存储桶,每个存储桶都包含自己的哈希表。
与您的想法相反,本地哈希映射不是递归的,而是它们每个都选择一个盐,使其成为完美的哈希。在实践中,这将(如您所说)通常已经由您尝试的第一种盐给出,因此它是渐近常数时间。
推荐阅读
- jquery - jQuery .on(click) 函数包含 IF 语句检查 .hasClass() 在不包含类时总是返回 true?
- c++ - 如何计算 unordered_set c++ 中的冲突
- sql - 如何删除重复和不需要的行
- c - 如何使用gets(tmp)添加一些indata参数?
- python - 将 UTF-16 字符串编码为可读文本时的 python 问题
- python - len(string) 显示的索引号比实际字符串多
- android - 在 Spinner 中显示新数据和旧数据
- datadog - Datadog 检查未出现在 Datadog 控制台中
- vue.js - 从父级初始化子级的变量
- doctrine-odm - 如何调试 Doctrine ODM 查询