理解散列码

散列函数在实现散列表中很重要。我知道在java 对象有它的哈希码，它可能是从弱哈希函数生成的。理解散列码

下面是一个片段，是“补充哈希函数”

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

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

任何人可以帮助解释什么是哈希算法的基本理念？生成非重复的整数？如果是这样，这些按位运算如何执行？

来源

2010-06-25 SecureFish

你通常试图用散列算法做什么是将一个大的搜索关键字转换成一个小的非负数，这样你就可以在某个表的某个地方查找关联的记录，并且比M log2 N（其中M是“比较”的成本，N是“表”中项目的数量））是典型的二进制搜索（或树搜索）。

如果你足够幸运有一个完美的散列，你知道你的（已知！）按键的任何元素将被散列到一个独特的，不同的值。对于需要查找语言关键字的编译器而言，完美的哈希值得关注。

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

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

来源

2010-06-25 21:33:49

散列函数是任何明确定义的过程或数学函数，它将大量可能可变大小的数据量转换为小数据，通常是一个可用作数组索引的整数。由散列函数返回的值称为散列值，散列码，散列总和，校验和或简单散列。（wikipedia）

使用更多“人类”语言对象散列是基于对象属性的简短紧凑值。这就是说，如果你有两个对象以某种方式变化 - 你可以期望他们的散列值是不同的。好的散列算法为不同的对象产生不同的值。

来源

2010-06-25 21:36:17

一个好的散列函数也应该为类似的值创建_very_不同的散列值。即使元素A和元素B在一个位上不同，他们的哈希应该是非常不同的。 – Piotr 2010-06-25 21:56:10

我一直很喜欢这个写法：http：//www.eternallyconfuzzled。COM/TUTS /算法/ jsw_tut_hashing.aspx – Joe 2010-06-25 22:51:30

该代码试图通过混合位来提高散列值的质量。

总体效果是，对于给定的x.hashCode（），希望可以在整个整数范围内更好地分配散列值。如果您开始使用糟糕的哈希码实现，但是通过这种方式改善哈希码，某些算法的性能会提高。

例如，Java中一个不起眼的Integer的hashCode（）只返回整数值。虽然这对许多目的都很好，但在某些情况下，您需要更好的哈希代码，因此通过这种函数添加哈希代码将显着改善它。

来源

2010-06-25 23:19:00 mikera

基本上，你试图用哈希函数实现的事情是给哈希代码中的所有位大概有50％的机会被关闭或给定一个特定的项目被哈希。这样，无论你的散列表有多少个“桶”（或换句话说，你为了确定桶号而采取了多少底部位） - 如果每位与随机的可能的，那么一个物品将总是被分配给一个基本上随机的桶。

现在，在现实生活中，很多人使用散列函数并不好。他们有一些一些随机性，但不是全部。例如，想象一下如果你有一个散列函数，它的位6-7有偏见 - 比方说在一个对象的典型散列码中，他们有75％的机会被设置。在这个编制的例子中，如果我们的哈希表有256个桶（即桶编号来自哈希码的0-7位），那么我们丢掉8-31位确实存在的随机性，部分桶会倾向于被填满（即那些数量为6和7的桶）。

补充散列函数基本上试图散布散列代码中的任意随机性在大量的位上。因此，在我们的假设例子中，这个想法将会是，来自比特8-31的一些随机性将与较低比特混合在一起，并稀释比特6-7的偏差。它仍然不会完美，但比以前更好。

来源

2010-06-26 02:17:36

如果你正在生成一个哈希表，那么当你编写你的哈希函数时，你希望得到的主要事情是确保一致性，而不一定要创建完全独特的值。

例如，如果您有一个大小为10的散列表，则不需要反复散列3的散列函数。否则，该特定存储桶将强制搜索时间O（n）。你需要一个散列函数来返回它，例如：1，9，4，6，8 ......并确保你的桶不会比其他桶重得多。

对于您的项目，我建议您使用众所周知的散列算法，如MD5或更好的SHA，并使用您需要的前k位，然后丢弃其余部分。这些都是经过时间考验的功能，作为程序员，您可以很聪明地使用它们。

来源

2010-06-26 02:23:43 SHC

这可能是你想要的，只要你坚持在doc，这在我自己的话描述的general contract什么：

如果调用100（N）次的hashCode的对象上，所有的时间必须返回相同的值，至少在程序执行过程（随后的程序执行可以返回不同的一个）
如果o1.equals(o2)为真，则o1.hashCode() == o2.hashCode()必须为真也
如果o1.equals(o2)为假，则o1.hashCode() == o2.hashCode()可以是真的，但我t帮助它不是。

就是这样。

根据你的类的性质，hashCode（）e可能非常复杂或非常简单。例如String类可能有数百万个实例需要非常实用，并使用素数来降低冲突的可用性。

如果你的班级确实有一个连续的数字，那也没关系，你没有理由每次都把它复杂化。

来源

2010-06-26 02:39:09 OscarRyz

回答

相关问题