哈希值 & 哈希表

哈希值

是一个十进制的整数，由系统随机给出，就是是对象的地址值（十六进制）也称逻辑地址，但非对象的物理地址。

获取方法

在Object类有一个方法,可以获取对象的哈希值

• public native int hashCode()

  ：返回该对象的哈希码值。

  native

  :代表该方法调用的是本地操作系统的方法

hashCode方法梳理

对象的哈希值

public class Demo01HashCode {
    public static void main(String[] args) {
        // Person继承了Object类，所以可以使用Object类的hashCode方法
        Person p1 = new Person();
        Person p2 = new Person();
        Person p3 = new Person("小明",18);
        int h1 = p1.hashCode();     
        int h2 = p2.hashCode();
        int h3 = p3.hashCode();
        
        System.out.println(h1); 
        System.out.println(h2); 
        System.out.println(h3);
        System.out.println(h1 == h2);
        System.out.println(h1 == h3); 

        /*
            toString方法的源码:
                return getClass().getName() + "@" + Integer.toHexString(hashCode());
         */
        // 物理地址不相同
        System.out.println(p1);  
        System.out.println(p2);
        System.out.println(p3); 
        System.out.println(p1 == p2);
        System.out.println(p1 == p3); 
    }
}
           

重写hashCode方法

public class Person {
       // ...省略
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
   }
           

结果：

未重写

hashCode

方法：

======逻辑地址、判断=======
1355531311
1967205423
42121758
false
false
======地址值、判断=======
com.luis.demo02.hashCode.Person@50cbc42f
com.luis.demo02.hashCode.Person@75412c2f
com.luis.demo02.hashCode.Person@282ba1e
// 物理地址不相同   
false
false
==================
           

重写后：

======逻辑地址、判断=======
961
961
23458772
true
false
======物理地址、判断=======
com.luis.demo02.hashCode.Person@3c1
com.luis.demo02.hashCode.Person@3c1
com.luis.demo02.hashCode.Person@165f3d4
false
false
==================
           

字符串类的哈希值

字符串类重写了

hashCode

方法，所以

s1、s2

的哈希值均为：96354

有两个元素不同，但是哈希值相同（特例）：哈希冲突

• 重地：1179395
• 通话：1179395

代码：

public class Demo01HashCode {
    public static void main(String[] args) {

        String s1 = new String("abc");
        String s2 = new String("abc");
        String s3 = new String("aBc");
        String s4 = "abc";
        String s5 = "abc";
        String s6 = "aBc";
        System.out.println(s1.hashCode()); // 96354
        System.out.println(s2.hashCode()); // 96354
        System.out.println(s2.hashCode()); // 95362
        System.out.println(s4.hashCode()); // 96354
        System.out.println(s5.hashCode()); // 96354
        System.out.println(s6.hashCode()); // 95362

        System.out.println(s1 == s2);
        System.out.println(s1 == s3);
        System.out.println(s1 == s4);
        System.out.println(s1 == s5);
        System.out.println(s1 == s6);
        System.out.println(s4 == s5); // true，其余为false
        System.out.println(s4 == s6);

        // 两个元素不同，但是哈希值相同（特例）：哈希冲突
        System.out.println("重地".hashCode()); // 1179395
        System.out.println("通话".hashCode()); // 1179395
    }
}
           

图表理解

哈希表 【JDK1.8】

在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。

而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示。

看到这张图就有人要问了，这个是怎么存储的呢？为了方便理解我们结合一个存储流程图来说明一下：

总而言之，JDK1.8引入红黑树大程度优化了HashMap的性能，那么对于我们来讲保证HashSet集合元素的唯一，其实就是根据对象的hashCode和equals方法来决定的。