1.8版本HashMap底层原理分析_jdk1.8hashmap底层实现原理

一、什么是Hash

# 1、核心理论：

        Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

# 2、Hash的特点：

• 从hash值不可以反向推导出原始的数据
• 输入的数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值
• 哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
• hash算法的冲突概率要小

由于hash的原理是将输入的空间的值映射成hash空间内，而hash值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

抽屉原理：桌上有是个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。

二、HashMap中常量、成员变量以及构造方法分析

    // 缺省table容量16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
    // table最大容量2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
 
    // 默认的负载因子0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
    // 链表树化阈值
    static final int TREEIFY_THRESHOLD = 8;
 
    // 树降成链表阈值
    static final int UNTREEIFY_THRESHOLD = 6;
 
    // 树化阈值的另一个参数，当桶元素数量超过64个，并且链表达到阈值8，才会进行树化
    static final int MIN_TREEIFY_CAPACITY = 64;
 
    // HashMap类中的静态内部类Node链表
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
 
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
    }
 
    // table数组
    transient Node<K,V>[] table;
 
    // 存放元素的个数
    transient int size;
 
    // 扩容阈值 当实际大小超过扩容阈值时，会进行扩容（threshold = loadFactor * capacity）
    int threshold;   
 
    // 加载因子
    final float loadFactor;  
 
    // 当前hash表修改结构次数
    transient int modCount;  
 
    // 就说一个两个参数的构造器吧
    public HashMap(int initialCapacity, float loadFactor) {
        
        //做校验的容量必须大于0且不能超过最大容量
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        
        // 加载因子必须大于0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
 
        // tableSizeFor这个方法就是为了计算出大于等于给定容量的最小的2的次幂
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 这个方法就是保证容量为2的n次方
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

 三、HashMap中put方法和putVale方法源码分析

 
        /** 
            调用put方法时先调用hash()方法（扰动）将key传进去经过
            (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)得到一个值然后传putVal方法 
            中，            
            其目的就是混合高位和低位来加大随机性 
        */    
        public V put(K key, V value) {
              return putVal(hash(key), key, value, false, true);
        }
 
        // 调用putVal方法
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
 
        /**
           tab：引用当前hashMap的散列表
           p: 表示当前散列表的元素
           n: 表示散列表数组的长度
           i: 表示路由寻址结果
        */
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        // 延迟初始化逻辑，第一次调用putVal会初始化hashMap对象中的最耗费内存的散列表
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        /**
             第一种情况：对hash值进行计算得出索引值，如果该索引值的位置上没有其他元素则直接存放 
        */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
 
            /**
                 e: 不为null的话，找到了一个与当前要插入的key-value一致的key的元素
                 k: 临时key
            */
            Node<K,V> e; K k;
 
            /**
                 第二种情况：如果该索引位置上的元素和你要插入的元素的key完全一致时，那么就将这个 
                 元素赋给e后续进行替换操作
            */
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
 
            //  第三种情况：如果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;
                    }
 
                    // 如果当前索引处元素的key与插入元素的key相同的话，进行替换操作
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果存入的key相同，那么就将新插入key对应的value值替换掉原先key所对应的value值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        
        // 记录修改结构的次数
        ++modCount;
 
        // 判断如果数组大小大于扩容阈值那么就会进行resize（）
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}

  四、HashMap中reSize()方法源码分析

    // 为了解决哈希冲突导致的链化影响查询效率问题，扩容会缓解该问题。
    final Node<K,V>[] resize() {
 
        // 引用扩容前的哈希表
        Node<K,V>[] oldTab = table;
 
        // oldCap表示扩容前table的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        
        // oldthr表示扩容前的扩容阈值，也就是触发本次扩容的阈值
        int oldThr = threshold;
        
        // newCap：扩容之后的table大小
        // newThr：扩容之后的扩容阈值
        int newCap, newThr = 0;
        
        // 如果oldCap > 0 说明hashMap中的散列表已经初始化过了，这是正常的扩容
        if (oldCap > 0) {
                   
            // 如果oldCap达到最大容量，那么不扩容，直接返回oldTab，并且扩容阈值设置位最大
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
        
            // 如果oldCap * 2 < 最大容量，并且oldCap 大于等于默认初始容量16，则newThr为oldThr 
            // 的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; 
        }
 
        /** 
            如果oldCap = 0且oldThr > 0 时，当第一次put添加的时候容量就为扩容之前的扩容阈值，这    
            个数是一定是2的n次方
        */
        else if (oldThr > 0) 
            newCap = oldThr;
        
        /** 
            如果oldCap = 0且oldThr = 0，newCap等于默认的初始容量16，newThr等于初始容量乘以加 
            载因子 
        */
        else {   
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
 
        // 如果newThr为0时，通过newCap和loadFactor计算出一个newThr
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
 
        @SuppressWarnings({"rawtypes","unchecked"})
 
        // 创建一个更大容量的table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
 
        // 说明本次扩容之前，table不为null
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
            
                // 说明当前桶位中有数据
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
            
                    // 如果当前桶位只有一个元素，从未发生过碰撞，直接算出当前元素在新数组中存放 
                    // 的位置，然后放进去。
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
 
                    // 如果已经树化了，进行树操作
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
 
                    // 如果是链表，那么就将之前的链表进行拆分到新的数组中
                    else { // preserve order
            
                        // 低位链表：存放在扩容之后的数组的下标位置，与当前数组的下标位置一致
                        Node<K,V> loHead = null, loTail = null;
 
                        // 高位链表：存放在扩容之后的数组的下标位置为当前数组下标位置 + 扩容之 
                        // 前数组的长度
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

五、关于HashMap的一些问题

1、当key为null时，这次put操作，数据将被放入那个桶位？为什么？

        可以看出当key为null时，hash返回的是0，通过p = tab[i = (n - 1) & hash]得出i为0，所以放在0号桶位。

 static final int hash(Object key) {
        int h;
        // 混合高位和低位加大随机性
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、为什么HashMap内部的散列表数组的长度一定是2的次方数?

       长度16或其他2的幂次方，Length - 1的值的二进制所有的位均为1，这种情况下，Index的结果等于hashCode的最后几位。只要输入的hashCode本身符合均匀分布，Hash算法的结果就是均匀的。

          一句话，HashMap的长度为2的幂次方的原因是为了减少Hash碰撞，尽量使Hash算法的结果均匀分布。

3、JDK1.8的HashMap为什么要引入红黑树，以及树化的条件

        当HashMap中的数据量足够多的时候，HashMap的链化会很严重，他的查找效率会非常低，而引入红黑树，就是为了提高查找效率的。

        当桶内元素超过64个并且某个链表的长度大于等于8的时候会进行树化。

4、谈一下hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？

        当table中的元素达到阈值的时候（cap * loadFactor）就会进行扩容。

        1、如果oldCap大于等于最大容量，那么返回oldCap，不扩容

        2、如果oldCap * 2 < 最大容量，并且oldCap 大于等于默认初始容量16，则扩容为oladCap的2倍

        3、如果还未初始化，就将oldThr赋给newCap这个oldThr一定是2的n次方，然后计算出一个新的newThr赋给loadFactor，newThr = newCap * loadFactor

        4、遍历oldTab

        5、如果当前桶位只有一个元素，从未发生过碰撞，直接算出当前元素在新数组中存放 
的位置，然后放进去。如果是链表，那么就将之前的链表进行拆分到新的数组中。如果已经树化，就进行树的操作（目前不太了解红黑树的底层）。

5、为什么默认的加载因子loadFactor为0.75

     加载因子过高，例如为1，虽然减少了空间开销（扩容次数减少），提高了空间利用率，但同时也增加了查询时间成本（导致链表变长）；加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低。

六、为什么重写equals还要重写hashcode方法

 1、关于hashcode的规定（为了使诸如HashMap这样的哈希表正常使用）

• equals相等，hashcode一定相等。

• equals不等，hashcode不一定不等。

• hashcode相等，equals不一定相等。

• hashcode不相等，equals一定不相等。

2、

User a = new User("张三",28);
User b = new User("张三",28);
 
/**
    1、对于User类来说如果你只重写equals方法，那么a.equals(b)返回的是true，根据规定equals相等那么            
       hashcode一定相等，然而事实却是不相等的，这就造成了矛盾，所以要重写hashcode。
    2、个人认为这样的目的就是为了诸如HashMap这样的哈希表使用，通过上面hashmap源码的分析也可以看    
       到，如果你将这个User类当作key使用的话，那么你就必须重写hashcode，因为他底层是先把key也就是 
       插入的User对象的hashcode值经过扰动函数算出来该元素在hash表中的位置。如果不重写hashcode，那 
       么a和b算出来的索引值都一样就都会添加到hash表中，然而这样的事实并不是我们想要的，我们想要的结 
       果是第二个key为User的元素的值可以替换掉第一个key为User的元素的值，所以必须重写hashcode和 
       equals。
*/