hash详解

Hash

一般翻译做”散列“，也有直接音译为”哈希“的，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。其中，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出。简单来说就是一种将任意输入的消息压缩到某一固定长度的消息摘要的函数。

哈希表

该函数的实现就是通过一系列的算法（如直接取余法、乘法取整法等）来得到一个哈希值，得到的哈希值就在hash表中。

Hashcode

对象的hashcode怎么得来的？

我没都知道，每个对象都有属于自己的物理地址，就是对象实际存放在内存中的地址。这个物理地址与hashcode是不一样的，hashcode是对象的物理地址通过hash函数算法计算得到的，得到的hashcode，就是对象在hash表中的位置。

举例：

hash表中有6个位置，有一个对象A，它有自己的物理地址，首先将这个物理地址转换成整数，假设是17，然后通过hash函数，直接取余法，即17%8=1。因此,对象A的hashcode值就是1，也就是其在hash表中的位置。

对象有了物理地址，为什么还有使用hashcode呢？

提升查找的效率。

题目：往内存中存1000个不同的数字。

不适用hashcode的情况下：

使用最笨的方法，每存一个数就去与之前存的所有数字比较，不一样则存入。当你存数字900的时候，你就需要对比900次，效率低。

使用hashcode的情况下：

hash表中有1，2，3，4，5，6，7，8个位置，你将每一个数字存入时，每个数字都有hashcode，当你存放数字900时，hash表中的八个位置内都有100个左右的数字。此时，你只需要去比较与900hash值相同位置的数字，也就是比较100次左右，相比上面的方法，效率大大提高。

equals方法和hashcode的区别

很多面试题中都有这个问题。

通过上面的例子我们知道，对象的hashcode不是唯一的，因此，我们不能通过比较对象的hashcode，来比较对象是否相等，比较对象是否相等才是使用equals。

接着上面，假如当我们计算出900的hash值为5时，你就需要与hash表中位置五里面的100个数字进行比较，而比较的方法就是equals。

结论：

• 如果两个对象equals相等，那么他们的hashcode也相等。

• 如果两个对象hashcode相等，只能说这两个对象在hash表中的位置相等，但是不代表两个对象相等，对象是否相等，需要通过equals来比较。

最后：

如果对象的equals方法被重写时，最好把对象的hashcode方法也一起重写，这样才能保证，对象equals相等时，对象的hashcode也相等。