理解哈希码

Question

哈希函数在实现哈希表时很重要.我知道在java Object中有它的哈希码,它可能是从弱哈希函数生成的.

以下是一个"补充哈希函数"的片段

static int hash(Object x) {
    int h = x.hashCode();

    h += ~(h << 9);
    h ^=  (h >>> 14);
    h +=  (h << 4);
    h ^=  (h >>> 10);
    return h;
}

任何人都可以帮助解释哈希算法的基本思想是什么？生成非重复整数？如果是这样,这些按位操作如何实现呢？

Answer 1

散列函数是任何明确定义的过程或数学函数,它将大的,可能大小可变的数据量转换为小数据,通常是可以作为数组索引的单个整数.哈希函数返回的值称为哈希值,哈希码,哈希值,校验和或简单哈希值.(维基百科)

使用更多"人类"语言对象散列是基于对象属性的简短紧凑值.也就是说,如果您有两个以某种方式变化的对象 - 您可以预期它们的哈希值会有所不同.好的哈希算法为不同的对象产生不同的值.

Answer 2

您通常尝试使用哈希算法执行的操作是将较大的搜索键转换为较小的非负数，因此您可以在表中的某个位置查找关联记录，并且比 M log2 N 更快（其中 M 是“比较”的成本，N 是“表”中的项目数）典型的二分搜索（或树搜索）。

如果您足够幸运，拥有完美的哈希值，您就会知道（已知！）键集中的任何元素都将被哈希为唯一的、不同的值。完美哈希主要对需要查找语言关键字的编译器之类的东西感兴趣。

在现实世界中，您的哈希值不完美，其中多个键都哈希为相同的值。没关系：您现在只需将键与一小组候选匹配项（散列到该值的匹配项）进行比较，而不是与一大组（整个表）进行比较。小集传统上称为“桶”。您使用哈希算法来选择一个存储桶，然后为存储桶本身使用一些其他可搜索的数据结构。（如果桶中的元素数量已知或安全地预期非常小，则线性搜索并非不合理。二叉搜索树也是合理的。）

您的示例中的按位操作看起来很像签名分析移位寄存器，它尝试将长的唯一模式压缩为短的、仍然唯一的模式。