Hash和HashCode深入理解
目录介绍 1.Hash的作用介绍 1.1 Hash的定义 1.2 Hash函数特性 1.3 Hash的使用场景 2.如何判断两个对象相等 2.1 判断两个字符串 2.2 判断两个int数值 2.3 其他基本类型 3.HashCode深入分析 3.0 HashCode是什么 3.1 为什么要重写HashCode 3.2 HashCode源代码分析 3.3 HashCode带来的疑问 3.4 HashCode的作用 3.5 HashMap中的HashCode 3.6 可直接用hashcode判断两个对象是否相等 4.Hash表是什么 4.1 Hash表定义 4.2 Hash表简单介绍 5.Hash中的算法应用 5.1 基础算法 5.2 经典算法[摘自网络] 5.3 Hash碰撞[摘自网络] 6.Hash在Java中的应用场景 6.1 equals与hashCode有两个注意点 6.2 以HashSet为例说明hashCode()的作用 6.3 以HashMap为例说明Hash的作用 6.4 7.版本更新情况 8.其他介绍 1.Hash的作用介绍 1.1 Hash的定义 散列（哈希）函数 把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值，是一种压缩映射。 或者说一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 1.2 Hash函数特性 h(k1)≠h(k2)则k1≠k2，即散列值不相同，则输入值即预映射不同 如果k1≠k2，h(k1)=h(k2) 则发生碰撞； 如果h(k1)=h(k2)，k1不一定等于k2； 1.3 Hash的使用场景 比如说我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件就是我们所需要的呢？我们不可能去一一检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息，这时候，就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。 散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。 这种标志有何意义呢？之前文件下载过程就是一个很好的例子，事实上，现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。 2.如何判断两个对象相等 2.1 判断两个字符串 使用equals方法判断两个字符串是否相等 String a = "yc1"; String b = "yc2"; boolean isEqual = a.equals(b); 当然Object的子类可以通过重写equals的方法，实现子类自身的对象是否相等的逻辑；String是Object的子类，查看下它的equals方法 //在Object类中 public boolean equals(Object obj) { //直接比较的是地址 return (this == obj); } //在String类中 public boolean equals(Object anObject) { //直接比较的是地址 if (this == anObject) { return true; } //盘旋是否是字符串String类型 if (anObject instanceof String) { String anotherString = (String) anObject; int n = count; if (n == anotherString.count) { int i = 0; //循环判断每个字符是否相等 while (n-- != 0) { if (charAt(i) != anotherString.charAt(i)) return false; i++; } return true; } } return false; } 2.2 判断两个int数值 Integer类的equals方法又是如何实现的呢？ Integer a = Integer.valueOf("1"); Integer b = Integer.valueOf("2"); boolean ab = a.equals(b); public boolean equals(Object obj) { //先判断是否是Integer类型 if (obj instanceof Integer) { //转为int值后进行比较 return value == ((Integer)obj).intValue(); } return false; } 2.3 其他基本类型 //short类型 @Override public int hashCode() { return Short.hashCode(value); } public static int hashCode(short value) { return (int)value; } //Byte类型 @Override public int hashCode() { return Byte.hashCode(value); } public static int hashCode(byte value) { return (int)value; } //Long类型 @Override public int hashCode() { return Long.hashCode(value); } public static int hashCode(long value) { return (int)(value ^ (value >>> 32)); } //long类型作为索引范围太大，需要转为int类型。这里简单的获取低32位容易导致散列不均，因为高位部分没有被利用。所以这里采用逻辑右移32位，让高32位和低32位进行XOR操作，导致高位低位都能被利用到 //Boolean类型 @Override public int hashCode() { return Boolean.hashCode(value); } public static int hashCode(boolean value) { return value ? 1231 : 1237; } //采用两个质数作为true或false的索引。这两个质数足够大，用来作为索引时，出现碰撞的可能性低。 3.HashCode深入分析 3.0 HashCode是什么 HashCode是Object的一个方法，hashCode方法返回一个hash code值，且这个方法是为了更好的支持hash表，比如String，Set，HashTable、HashMap等; 3.1 为什么要重写HashCode 如果用 equal 去比较的话，如果存在1000个元素，你 new 一个新的元素出来，需要去调用1000次equal去逐个和他们比较是否是同一个对象，这样会大大降低效率。hashcode实际上是返回对象的存储地址，如果这个位置上没有元素，就把元素直接存储在上面，如果这个位置上已经存在元素，这个时候才去调用equal方法与新元素进行比较，相同的话就不存了，散列到其他地址上 3.2 HashCode源代码分析 在Object中的HashCode源代码 public int hashCode() { int lockWord = shadow$_monitor_; final int lockWordStateMask = 0xC0000000; // Top 2 bits. final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash). final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits. if ((lockWord & lockWordStateMask) == lockWordStateHash) { return lockWord & lockWordHashMask; } //返回的是对象引用地址 return System.identityHashCode(this); } 在String中的HashCode源代码 public int hashCode() { int h = hash; if (h == 0 && count > 0) { for (int i = 0; i < count; i++) { h = 31 * h + charAt(i); } hash = h; } return h; } 在Integer中的HashCode源代码 public int hashCode() { //int值 return value; } 3.3 HashCode带来的疑问 为何重写equals建议同时重写hashCode？ hashCode是什么？ hashCode作用？ hash code（hash值）是什么？ hash table（hash表）是什么？ hashCode方法对hash表有益处？ hashCode方法对不是hash有益处吗? 3.4 HashCode的作用 减少查找次数，提高程序效率 例如查找是否存在重复值 h(k1)≠h(k2)则k1≠k2 首先查看h(k2)输出值（内存地址），查看该内存地址是否存在值； 如果无，则表示该值不存在重复值； 如果有，则进行值比较，相同则表示该值已经存在散列列表中，如果不相同则再进行一个一个值比较；而无需一开始就一个一个值的比较，减少了查找次数 3.5 HashMap中的HashCode 在Java中也一样，hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。 为什么这么说呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在） 也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。 此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。下面这段代码是java.util.HashMap的中put方法的具体实现： put方法是用来向HashMap中添加新的元素，从put方法的具体实现可知，会先调用hashCode方法得到该元素的hashCode值，然后查看table中是否存在该hashCode值，如果存在则调用equals方法重新确定是否存在该元素，如果存在，则更新value值，否则将新的元素添加到HashMap中。从这里可以看出，hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 3.6 可直接用hashcode判断两个对象是否相等 肯定是不可以的，因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等，但是可以直接根据hashcode值判断两个对象不等，如果两个对象的hashcode值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过equals方法。 也就是说对于两个对象，如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等； 如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同； 如果两个对象的hashcode值不等，则equals方法得到的结果必定为false； 如果两个对象的hashcode值相等，则equals方法得到的结果未知。 4.Hash表是什么 4.1 Hash表定义 根据关键码值（KEY-VALUE）而直接进行访问的数据结构；它通过把关键码值（KEY-VALUE）映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 4.2 Hash表简单介绍 将k作为输入值，h(k)输出值作为内存地址，该内存地址用来存放value，然后可以通过k获取到value存放的地址，从而获取value信息。 5.Hash中的算法应用 5.1 基础算法 比如，Java中的String.hashCode使用乘法和加法 public int hashCode() { int h = hash; if (h == 0 && count > 0) { for (int i = 0; i < count; i++) { //乘法与加法 h = 31 * h + charAt(i); } hash = h; } return h; } 5.2 经典算法[摘自网络] MD4，MD5，SHA-1或SHA-2等其他 5.3 Hash碰撞[摘自网络] hash是存在碰撞的，如果k1≠k2，h(k1)=h(k2) 则发生碰撞； 6.Hash在Java中的应用场景 6.1 equals与hashCode有两个注意点 equals相同，则hashCode相同；而hashCode相同，equals不一定相同 如果equals相同，hashCode不相同，有可能会造成上述重复值等情况，这种情况是不允许的； 而hasCode相同，但是equals不一定相同，有可能是因为发生了碰撞而碰撞是有可能性发生的 6.2 以HashSet为例说明hashCode()的作用 假设，HashSet中已经有1000个元素。当插入第1001个元素时，需要怎么处理？ 因为HashSet是Set集合，它允许有重复元素。“将第1001个元素逐个的和前面1000个元素进行比较”？ 显然，这个效率是相等低下的。散列表很好的解决了这个问题，它根据元素的散列码计算出元素在散列表中的位置，然后将元素插入该位置即可。对于相同的元素，自然是只保存了一个。 由此可知，若两个元素相等，它们的散列码一定相等；但反过来确不一定。在散列表中， 1、如果两个对象相等，那么它们的hashCode()值一定要相同； 2、如果两个对象hashCode()相等，它们并不一定相等。 注意：这是在散列表中的情况。在非散列表中一定如此！ 6.3 以HashMap为例说明Hash的作用 在HashMap中有许多地方用到了hash算法 //put方法 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //remove方法 public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } //get方法 public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } //上面这几个方法都用到了这个方法 static final int hash(Object key) { int h; //计算hashCode，并无符号移动到低位 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 举个例子: h = 363771819^(363771819 >>> 16) 0001 0101 1010 1110 1011 0111 1010 1011(363771819) 0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR --------------------------------------- = 0001 0101 1010 1110 1010 0010 0000 0101(363766277) 这样做可以实现了高地位更加均匀地混到一起 参考博客 Java Hash 存储机制：http://blog.chinaunix.net/uid-26981819-id-4462638.html 数据结构之哈希表：https://www.cnblogs.com/s-b-b/p/6208565.html Java hashCode() 和 equals()的若干问题解答：https://www.cnblogs.com/skywang12345/p/3324958.html Hash算法总结：https://blog.csdn.net/asdzheng/article/details/70226007 浅谈Java中的hashcode方法：http://www.cnblogs.com/dolphin0520/p/3681042.html 关于其他内容介绍 01.关于博客汇总链接 1.技术博客汇总 2.开源项目汇总 3.生活博客汇总 4.喜马拉雅音频汇总 5.其他汇总 02.关于我的博客 我的个人站点：www.yczbj.org，www.ycbjie.cn github：https://github.com/yangchong211 知乎：https://www.zhihu.com/people/yang-chong-69-24/pins/posts 简书：http://www.jianshu.com/u/b7b2c6ed9284 csdn：http://my.csdn.net/m0_37700275 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/ 开源中国：https://my.oschina.net/zbj1618/blog 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1 邮箱：yangchong211@163.com 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
