0

我有大量的长整数标识符，需要尽可能均匀地分布到 (n) 个桶中。长整数标识符可能有一些丢失的标识符。以此为标准，按原样使用长整数和进行模（n）[长整数]之间是否有区别，或者为长整数的字符串版本生成hashCode更好（以改善分布）然后做一个模（n）[字符串的哈希码（长整数）]？通过哈希码获得统一传播是否需要额外的字符串转换？

由于我收到反馈说我的问题没有足够的背景信息。我正在添加更多信息。

标识符基本上是自动递增的数字行标识符，在表示项目 ID 的数据库中自动生成。缺少标识符的原因是由于删除。

标识符本身是长整数。标识符（项目）本身在某些情况下为 (10s-100)+ 百万，在某些情况下为数千。

只有在标识符数以百万计的情况下，我才想真正将它们分散到存储桶（标识符计数 >> 存储桶计数）中，以便存储在非 SQL 系统（分区）中。

我想知道是否因为项目被删除，我是否应该求助于 (Long).toString().hashCode() 来获得统一的传播而不是直接使用长数字。我有一种感觉，做一个 toString.hashCode 不会给我带来太多好处，而且我也不喜欢 java hashCode 不能保证在 ja​​va 修订中具有相同值的事实（尽管对于 String 他们的 hashCode 实现似乎有文档且稳定对于过去几年的版本）

4

2 回答 2

1

没有必要参与String。

new Integer(i).hashCode()

... 给你一个哈希 - 专为均匀分布到桶中而设计。

new Integer(i).hashCode() % n

...会给你一个你想要的范围内的数字。

然而 Integer.hashCode()只是：

 return value;

所以new Integer(i).hashCode() % n等价于i % n。

于 2017-10-10T16:07:47.570 回答
1

您的问题无法回答。@slim 的尝试是您将得到的最好的，因为您的问题中缺少关键信息。

  • 要分发一组项目，您必须了解它们的初始分布。

如果它们是均匀分布的，并且桶的数量明显高于输入的范围，那么 slim 的答案就是要走的路。如果这两个条件中的任何一个不成立，它就不会起作用。

  • 如果输入的范围没有明显高于桶的数量，则需要确保输入的范围是桶数的精确倍数，否则最后的桶不会得到那么多的项目。例如，对于范围 [0-999] 和 400 个存储桶，前 200 个存储桶获取项目 [0-199]、[400-599] 和 [800-999]，而其他 200 个存储桶获取 iems [200-399] 和 [ 600-799]。

    也就是说，一半的存储桶最终比另一半多出 50% 的项目。

  • 如果它们不是均匀分布的，因为模运算符不会改变分布，除非通过包装它，输出分布也不均匀。

    这是您需要哈希函数的时候。

    但是要构建散列函数，您必须知道如何表征输入分布。哈希函数的重点是打破输入的重复性、可预测的方面。

公平地说，有一些散列函数在大多数数据集上工作得相当好，例如 Knuth 的乘法方法（假设输入不是太大）。比如说，你可能会计算

hash(input) = input * 2654435761 % 2^32

它擅长打破价值集群。但是，它在可分性方面失败了。也就是说，如果您的大部分输入都可以被 2 整除，那么输出也可以。[归功于这个答案]

我发现这个 gist对各种散列函数及其特征进行了有趣的汇编，您可能会选择最符合您的数据集特征的一个。

于 2017-10-10T16:44:42.450 回答