哈希函数
哈希这个词相信大家一定不陌生, 最早接触到这个词是在网站上下载文件, 网站会给出一个哈希码, 然后文件下载完也可以生成一个哈希码, 如果哈希码是一样的, 则表明文件传输正常, 没有被修改过.
也正是因为开始有过这样的接触, 导致我在相当长的时间里都对哈希有着很深的误解.
首先我们来了解一下哈希函数. 哈希函数, 就是把任意长度的输入, 通过散列算法, 变换成固定长度的输出. 该输出就是散列值. 这种转换是一种压缩映射, 也就是, 散列值的空间通常远小于输入的空间, 不同的输入可能会散列成相同的输出, 而不可能从散列值来唯一的确定输入值. 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数.
上面提到的校验文件只是哈希函数的一种应用, 是采用的加密的哈希算法, 常见的如MD5, SHA1 等. 而且根据哈希函数的定义可见, 即便文件的哈希码是一样的, 也不能说明两个文件是一样的, 只是因为算法比较复杂, 要构建哈希码相同的两个文件非常非常难.
在Java中, Object类中有一个方法: public native int hashCode();
因为这个方法的名字, 我一直试图将它与文件校验用的哈希算法联系在一起, 误认为这个方法也是一种加密算法, 只要2个对象这个方法的返回值相同它们就是同一个对象, 然而hashCode 方法和文件校验用的算法其实没什么关系.
根据这个方法的声明可知, 该方法返回一个int 类型的数值, 并且是本地方法, 因此在Object类中并没有给出具体的实现. 为何Object类需要这样一个方法? 它有什么作用呢? 今天我们就来具体探讨一下hashCode 方法.
哈希表
首先我们得先了解一下哈希表. 哈希表是计算机中的一种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。
对哈希表的使用者一一人来说，这是一瞬间的事。哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。
而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。
然而如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
hashCode 方法的作用
对于包含容器类型的程序设计语言来说，基本上都会涉及到hashCode。在Java中也一样，hashCode 方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。
为什么这么说呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：Set集合中不允许重复的元素存在）
也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode 方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode 方法，得到对应的hashcode 值，实际上在HashMap 的具体实现中会用一个table保存已经存进去的对象的hashcode 值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同的话就散列到其它的地址(具体处理可以参考资料中的哈希表算法)，这样一来实际调用equals方法的次数就大大降低了，提升了程序的效率。说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。
有些朋友误以为默认情况下，hashCode 返回的就是对象的存储地址，事实上这种看法是不全面的，确实有些JVM在实现时是直接返回对象的存储地址，但是大多时候并不是这样，只能说可能存储地址有一定关联。
因此有人会说，可以直接根据hashcode值判断两个对象是否相等吗？肯定是不可以的，因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等，但是可以直接根据hashcode值判断两个对象不等，如果两个对象的hashcode值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过equals方法。
也就是说对于两个对象，如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等；
如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同；如果两个对象的hashcode值不等，则equals方法得到的结果必定为false；如果两个对象的hashcode值相等，则equals方法得到的结果未知。
在有些情况下，程序设计者在设计一个类的时候为需要重写equals方法，比如String类，但是千万要注意，在重写equals方法的同时，必须重写hashCode方法。
参考资料:
