[关闭]
@PheonixHkbxoic 2017-11-27T19:14:11.000000Z 字数 4454 阅读 837

hashCode

Java

一、java中类的hashCode

1.1. Object

  1. public native int hashCode();

是一个本地方法，返回的对象的地址值。也有可能不是地址，跟jvm的实现有关

1.2 Integer

  1. public int hashCode() {
  2.     return value;
  3. }

1.3 Long

  1. public int hashCode() {
  2.     return (int)(value ^ (value >>> 32));
  3. }

^处理使Long的值如果是位数小于32位时（其实就是Float），hashCode会与Float处理的结果相同；
我理解为兼容

1.4 Float

  1. public static int floatToIntBits(float value) {
  2.     int result = floatToRawIntBits(value);
  3.     // Check for NaN based on values of bit fields, maximum
  4.     // exponent and nonzero significand.
  5.     if ( ((result & FloatConsts.EXP_BIT_MASK) ==
  6.           FloatConsts.EXP_BIT_MASK) &&
  7.          (result & FloatConsts.SIGNIF_BIT_MASK) != 0)
  8.         result = 0x7fc00000;
  9.     return result;
  10. }

floatToRawIntBits是本地方法

1.5 Double

  1.  public int hashCode() {
  2.     long bits = doubleToLongBits(value);
  3.     return (int)(bits ^ (bits >>> 32));
  4. }
  6. public static long doubleToLongBits(double value) {
  7.     long result = doubleToRawLongBits(value);
  8.     // Check for NaN based on values of bit fields, maximum
  9.     // exponent and nonzero significand.
  10.     if ( ((result & DoubleConsts.EXP_BIT_MASK) ==
  11.           DoubleConsts.EXP_BIT_MASK) &&
  12.          (result & DoubleConsts.SIGNIF_BIT_MASK) != 0L)
  13.         result = 0x7ff8000000000000L;
  14.     return result;
  15. }

Double跟Float类似，并且doubleToRawLongBits也是本地方法
同样，hashCode兼容Float

1.6 String

  1. public int hashCode() {
  2.     int h = hash;
  3.     if (h == 0 && value.length > 0) {
  4.         char val[] = value;
  6.         for (int i = 0; i < value.length; i++) {
  7.             h = 31 * h + val[i];
  8.         }
  9.         hash = h;
  10.     }
  11.     return h;
  12. }
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

二、常用的构造散列函数的方法

  1. 　　散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位：
  3. 　　1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数）
  5. 　　2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
  7. 　　3. 平方取中法：取关键字平方后的中间几位作为散列地址。
  9. 　　4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
  11. 　　5. 随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
  13. 　　6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

三、解决hash散列冲突的方法

1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
2.再哈希法
3.链地址法(Java hashmap就是这么做的)
4.建立一个公共溢出区

四、如何生成一个合适的hashCode

  1. Hashcode在基于key-value的集合如：HashMap、LinkedHashMap中扮演很重要的角色。此外在HashSet集合中也会运用到，使用合适的hashcode方法在检索操作时的时间复杂度最好的是 O(1).
  3. 一个差劲的hashcode算法不仅会降低基于哈希集合的性能，而且会导致异常结果。Java应用中有多种不同的方式来生成hashcode。
  5. Effective Java
  6. Josh Bloch在他的书籍《Effective Java》告诉我们重写hashcode方法的最佳实践方式。
  8. 一个好的hashcode方法通常最好是不相等的对象产生不相等的hash值，理想情况下，hashcode方法应该把集合中不相等的实例均匀分布到所有可能的hash值上面。
  10. 把某个非0的常数值，比如17，保存在一个名为result的int类型的变量中。int result = 17;
  11. 对于对象中的每个域，做如下操作：
  12. 为该域计算int类型的哈希值c：
  13.     如果该域是boolean类型，则计算(f?1:0)
  14.     如果该域是byte、char、short或者int类型，则计算(int)f
  15.     如果该域是long类型，则计算(int)(f^(f>>>32))
  16.     如果该域是float类型，则计算Float.floatToIntBits(f)
  17.     如果该域是double类型，则计算Double.doubleToLongBits(f)，然后重复第三个步骤。
  18.     如果该域是一个对象引用，并且该类的equals方法通过递归调用equals方法来比较这个域，同样为这个域递归的调用hashCode，如果这个域为null，则返回0。
  19.     如果该域是数组，则要把每一个元素当作单独的域来处理，递归的运用上述规则，如果数组域中的每个元素都很重要，那么可以使用Arrays.hashCode方法。
  21. 把上面计算得到的hash值c合并到result中
  22. result = 31*result + c

五、关于 hashCode() 你需要了解的 3 件事

  1. 无论你何时实现 equals 方法，你必须同时实现 hashCode 方法
  2. 永远不要把哈希码误用作一个key
  3. 在分布式应用中不要使用哈希码,一种替代方法：SHA1
  1. 在一般的应用中你不需要了解hashcode的用法，但当你用到hashmap，hashset等集合类时要注意下hashcode。
  3. 你想通过一个object的key来拿hashmap的value，hashmap的工作方法是，通过你传入的object的hashcode在内存中找地址，当找到这个地址后再通过equals方法来比较这个地址中的内容是否和你原来放进去的一样，一样就取出value。
  5. 所以这里要匹配2部分，hashcode和equals
  6. 但假如说你new一个object作为key去拿value是永远得不到结果的，因为每次new一个object，这个object的hashcode是永远不同的，所以我们要重写hashcode，你可以令你的hashcode是object中的一个恒量，这样永远可以通过你的object的hashcode来找到key的地址，然后你要重写你的equals方法，使内存中的内容也相等。。。
  8. 首先，从语法角度，也就是从强制性的角度来说，hashCode和equals是两个独立的，互不隶属，互不依赖的方法，equals成立与hashCode相等这两个命题之间，谁也不是谁的充分条件或者必要条件。  
  10.   但是，从为了让我们的程序正常运行的角度，我们应当向Effective   Java中所言  
  11.   重载equals的时候，一定要（正确）重载hashCode  
  12.   使得equals成立的时候，hashCode相等，也就是a.equals(b)->a.hashCode()   ==   b.hashCode()，或者说此时，equals是hashCode相等的充分条件，hashCode相等是equals的必要条件（从数学课上我们知道它的逆否命题：hashCode不相等也不会equals），但是它的逆命题，hashCode相等一定equals以及否命题不equals时hashCode不等都不成立。  
  13.   所以，如果面试的时候，最好把hashCode与equals之间没有强制关系，以及根据（没有语法约束力的）规范的角度，应当做到...这两层意思都说出来:P  
  15.   总结一下，equals（）是对象相等性比较，hashCode（）是计算对象的散列值，当然他们的依据是对象的属性。
  16.  对于equals，一般我们认为两个对象同类型并且所有属性相等的时候才是相等的，在类中必须改写equals，因为Object类中的equals只是判断两个引用变量是否引用同一对象，如果不是引用同一对象，即使两个对象的内容完全相同，也会返回false。当然，在类中改写这个equals时，你也可以只对部分属性进行比较，只要这些属性相同就认为对象是相等的。

六、参考及文章

  1. 常见hash算法的原理
  2. 哈希分布与一致性哈希算法简介
    百度快照

七、另外

  1. 1.hashMap去掉了HashTable 的contains方法，但是加上了containsValue（）和containsKey（）方法。
  2. 2.hashTable同步的，线程安全，而HashMap是非同步的，线程不安全，效率上逼hashTable要高。
  3. 3.hashMap允许空键值，而hashTable不允许。
  4. 4.HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
  5. 5.Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；
  7. HashMap实现同步的方法：调用Collections的静态方法Collections.synchronizedMap(Map map);，返回一个同步的Map，这个Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。
  9. 同时说一下，ArrayList和HashSet，他们也都不是同步的，都是线程不安全的，对其实现同步的方式和HashMap的方式相同，都允许使用null元素，ArrayList分配的初始空间为10，HashSet分配的初始空间为16
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注