Java集合源码—HashMap

Myth丶恋晨 2021-11-06 01:04 339阅读 0赞

## HashMap源码分析 ##

### 1.概述 ###

HashMap是一种基于哈希算法的散列查找集合.其实现方式主要是数组+链表. 其存储键值对, 并根据键的哈希值作运算进行键值对的存储和查询. 当一个键的hash值与另一个键的hash值做运算后得到的在数组中位置相同, 这就说明出现了"哈希冲突", 所以采用链表, 将他们链成一条链表. 当这个链表长度过长时, 就会将该链表转化为红黑树提高性能

而HashMap的内部数组长度初始为16, 如果需要扩展数组, 那么规定是2的次方. 例如16会扩展到32->64->128->256…

这样扩充是因为 :

*  1.选择足够大的数组, 让键值对更均匀的分布在各个索引位, 尽量减少链表长度
 *  2.当使用除留余数法时, 能使用位运算代替模运算, 很大程度上提高效率. N % M等价于N & (M-1), M为2的次方

### 2.继承关系 ###

public class HashMap<K,V> extends AbstractMap<K,V>
        	implements Map<K,V>, Cloneable, Serializable {
        
        }

### 3.主要成员 ###

//数组默认的初始长度, java规定hashMap的数组长度必须是2的次方
    	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    	//数组的最大长度
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
    	//默认负载因子, 当元素在数组中的个数超过这个比例就会执行数组扩容操作
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    	//树形化临界值, 当链表节点个数大于等于TREEIFY_THRESHOLD-1时, 会将该链表转换为红黑树
        static final int TREEIFY_THRESHOLD = 8;
    
    	//结束树形化临界值, 当链表节点长度小于等于这个值时, 会将该红黑树转化为普通的链表
        static final int UNTREEIFY_THRESHOLD = 6;
    
    	//最小树形化的容量, 即:当内部数组长度小于等于这个值时, 会将红黑树转化为普通的链表
        static final int MIN_TREEIFY_CAPACITY = 64;
        
        //HashMap内部的数组, Node是链表节点对象
        transient Node<K,V>[] table;
    
        //存放映射对象的set
        transient Set<Map.Entry<K,V>> entrySet;
    
        //元素个数
        transient int size;
    
        //容器结构的修改次数, fail-fast机制
        transient int modCount;
    
        //临界值, 超过这个值时扩充数组
        int threshold;
    
        //负载因子
        final float loadFactor;

### 3.Node ###

static class Node<K,V> implements Map.Entry<K,V> {
        
            final int hash;//该节点的哈希值
            final K key;//该节点的键值
            V value;//该节点的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;
            }
    
            public final K getKey()        {
         return key; }
            public final V getValue()      {
         return value; }
            public final String toString() {
         return key + "=" + value; }
    
            public final int hashCode() {
        
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
        
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
        
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
        
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

### 4.构造函数 ###

//带两个参数的构造函数, 第一个是初始数组长度, 第二个是负载因子
    	public HashMap(int initialCapacity, float loadFactor) {
        
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            //这个方法可以将任意一个整数转化为第一个比它大的2的次方的数
            this.threshold = tableSizeFor(initialCapacity);
        }
    
        //使用默认的负载因子0.75
        public HashMap(int initialCapacity) {
        
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        //使用默认的初始长度16
        public HashMap() {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

### 5.核心方法 ###

#### 1>tableSizeFor方法 ####

这个方法的作用就是将一个整数转化成一个2的次方的整数, 因为前面说过HashMap中的数组大小必须是2的次方

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;
        }

#### 2>hash方法 ####

hash方法负责将hashCode转化为要放在数组中的具体下标

static final int hash(Object key) {
        
            int h;
            //若key为null, 则放在下标为0的位置, 所以HashMap中key可以为null
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

那是通过哪个公式获得**数组下标**呢

i = (n - 1) & hash

其中的hash就是通过hash()方法或得到的hash值.

#### 3>put方法 ####

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
        //oblyIfAbsent : 当存入键值对时, 如果该key已经存在, 是否覆盖他的value. false为覆盖, true为不覆盖
    	//evict : 用于子类LinkedHashMap
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            //tab : 内部数组
            //p : hash对应索引位的首节点
            //n : 内部数组的长度
            //i : hash对应的索引位
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //首次put时, 内部数组为空, 进行扩充
            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;
                如果首节点的key和要存入的key相同, 那么直接覆盖value的值
                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 {
        
                    //从链表的首节点后面开始,如果存在该键值对, 直接覆盖旧的value
                    //如果不存在, 则插入在链表末端, 然后判断链表长度书否大于7, 尝试转成红黑树
                    //treeifyBin会判断数组容量是否达到64, 如果没有则会先扩充数组
                    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;
                    }
                }
                //覆盖value
                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;
        }

总结一下put方法, 流程是这样的 :

*  1.检查是否数组为空, 执行resize()扩充
 *  2.通过hash值计算数组索引, 获取该索引位的首节点
 *  3.如果首节点为nul, 直接添加该节点到该索引位
 *  4.如果首节点不为null, 那么有三种情况
    
     *  a.key和首节点的key相同, 覆盖value
     *  b.如果首节点是红黑树节点, 添加该节点到红黑树
     *  c.如果首节点是链表, 将键值对添加到链表末尾, 之后会判断长度是否达到了树形化的临界值, 尝试将链表转为红黑树
 *  5.最后判断当前元素个数是否大于threshold, 扩充数组

#### 4>resize方法 ####

扩充数组不只是将数组长度翻倍, 然后将数组中的元素放进新数组那么简单

因为数组元素的索引是通过 hash & (n-1) 得到的, 那么数组的长度由n变为2n, 重新计算的索引可能和原来的不一样了

在jdk1.7中, 是通过遍历每一个元素, 每一个节点, 重新计算他们的索引值, 存入新的数组中, 称为rehash操作

而在jdk1.8中,对此进行了优化 : 由于n变成了2n, 所以, 那么n-1会在高位多出一位, 因此只需要看hash值新增的那一位是0还是1就可以了. 如果是0 ,那么索引不变; 如果是1, 那么索引变成"原索引+oldCap"

这个优化既省去了计算hash的时间, 并且会把之前冲突的节点分散到新的索引位上

final Node<K,V>[] resize() {
        
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
        
                //如果数组已经是最大长度, 则不进行扩容
                if (oldCap >= MAXIMUM_CAPACITY) {
        
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //否则数组容量扩充为原来的两倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                //如果数组还未初始化, 但是已经指定了临界值, 则将其赋给容量
                //在构造函数的那块出现过
                newCap = oldThr;
            else {
                       // zero initial threshold signifies using defaults
                //无参构造: 容量为默认的16
                //扩容临界值为 容量*负载因子
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
        
                //扩容之后可能会丢失最高位, 变为0
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            //创建一个新的数组
            @SuppressWarnings({
        "rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) {
        
                //遍历原数组
                for (int j = 0; j < oldCap; ++j) {
        
                    //取出首节点
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
        
                        //方便GC
                        oldTab[j] = null;
                        //如果链表只有一个节点, 计算出索引并放进去
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        //如果是红黑树节点,执行split方法
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else {
         // preserve order
                            //此时节点是链表
                            //loHead,loTail是原链表的节点
                            Node<K,V> loHead = null, loTail = null;
                            //hiHead,hiTail是新链表的节点
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            //遍历链表
                            do {
        
                                next = e.next;
                                //新增bit位为0的节点, 存入原链表                         
                                if ((e.hash & oldCap) == 0) {
        
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                //新增bit位为1的节点, 存入新链表
                                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;
        }

**总结 :**

*  jdk1.7中, 扩容时是依次计算数组每个索引上链表各节点的hash, 并以倒置的方式放进新的数组.
 *  jdk1.8中, 使用位运算巧妙的避开了计算哈希值, 并且能够按本来头到尾的顺序放进新的数组中

#### 5>get方法 ####

//从这里我们也可以看到, 每个键值对的value是可以为null的
    	public V get(Object key) {
        
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
    	final Node<K,V> getNode(int hash, Object key) {
        
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
        
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
        
                    //如果是红黑树节点,调用相应的方法
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
        
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

### 6.modCount值 ###

我们注意到HashMap和其他很多集合都有一个modCount值, 这个值是用来做什么的呢?

该字段表示list**结构上被修改**的次数。结构上的修改指的是那些改变了list的长度大小或者使得遍历过程中产生不正确的结果的其它方式。。作用是在使用迭代器Iterator对集合进行遍历时，用modCount来判断集合内数据没有发生变化，如果该值被意外更改，Iterator或者ListIterator 将抛出ConcurrentModificationException异常.

这是jdk在面对迭代遍历的时候为了避免不确定性而采取的快速失败原则(fail-fast)。

### 7.jdk1.7和jdk1.8的区别 ###

*  首先, HashMap中的key和value都是可以为空的, 如果key为空, 则hash函数返回值为0.
 *  jdk1.7时, 在某一位置上出现冲突, 使用头插法, 但是jdk1.8中使用尾插, 因为需要遍历链表检测是否需要树形化
 *  jdk1.7时的哈希算法较为复杂, 而jdk1.8比较简单, 即key的hash值的高16位和低16位取与.