这种处理哈希冲突的方法是new/unique吗?
Is this approach to dealing with hash collisions new/unique?
在处理哈希映射时,我看到了一些处理哈希冲突的策略,但我们提出了一些不同的策略。
我想知道这是不是新东西。
此版本的散列映射仅在散列和将散列的数据结构是可更改的情况下才有效。
(Haskell 中的 hashable
就是这种情况,我们建议实施这种方法。)
我们的想法是,您存储递归哈希映射,而不是在哈希映射的每个单元格中存储列表或数组。此递归哈希映射的唯一区别是您使用了不同的盐。
这样,哈希映射的一个级别上的哈希冲突很可能不会在下一层上发生哈希冲突。
因此,插入这样的哈希映射不再是 O(此哈希上的冲突数),而是 O(此冲突递归发生的级别数),这很可能更好。
更详细的解释和实现可以在这里找到:
您的想法似乎与 the Fredman, Komlós & Szemerédi paper from 1984. As Wikipedia summarizes it 中建议的想法实际上相同:
FKS Hashing makes use of a hash table with two levels in which the top level contains n buckets which each contain their own hash table.
与您的想法相反,本地散列映射不是递归的,而是每个散列映射都选择一个使其成为完美散列的盐。在实践中,这将(如您所说)通常已经由您尝试的第一个盐给出,因此它是渐近常数时间。
在处理哈希映射时,我看到了一些处理哈希冲突的策略,但我们提出了一些不同的策略。 我想知道这是不是新东西。
此版本的散列映射仅在散列和将散列的数据结构是可更改的情况下才有效。
(Haskell 中的 hashable
就是这种情况,我们建议实施这种方法。)
我们的想法是,您存储递归哈希映射,而不是在哈希映射的每个单元格中存储列表或数组。此递归哈希映射的唯一区别是您使用了不同的盐。 这样,哈希映射的一个级别上的哈希冲突很可能不会在下一层上发生哈希冲突。 因此,插入这样的哈希映射不再是 O(此哈希上的冲突数),而是 O(此冲突递归发生的级别数),这很可能更好。
更详细的解释和实现可以在这里找到:
您的想法似乎与 the Fredman, Komlós & Szemerédi paper from 1984. As Wikipedia summarizes it 中建议的想法实际上相同:
FKS Hashing makes use of a hash table with two levels in which the top level contains n buckets which each contain their own hash table.
与您的想法相反,本地散列映射不是递归的,而是每个散列映射都选择一个使其成为完美散列的盐。在实践中,这将(如您所说)通常已经由您尝试的第一个盐给出,因此它是渐近常数时间。