HashMap 基础源代码分析

HashMap源码解析

数据结构

jdk1.8开始HashMap底层是数组+链表/红黑树的结构，而jdk1.7时只有数组+链表，相对简单，故本文针对的是jdk1.8版本的做源码解析。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 16    
static final float DEFAULT_LOAD_FACTOR = 0.75f;//加载因子
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量，2的30次方
static final int TREEIFY_THRESHOLD = 8;//链表树化时的链表长度临界值
static final int MIN_TREEIFY_CAPACITY = 64;//链表树化时的数组容量临界值

static class Node<K,V> implements Map.Entry<K,V> {//数组及链表的Node结点
    final int hash;//hash值
    final K key;
    V value;
    Node<K,V> next;
}
transient Node<K,V>[] table;//table表，类型是Node数组
transient int size;//HashSet的实际元素个数，注意和tab.length区分（tab.length是容量）
int threshold;//临界值=加载因子（0.75）*当前容量

构造函数

    //无参构造
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
	//有参构造，指定初始容量和扩容因子
    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;
        this.threshold = tableSizeFor(initialCapacity);//将初始容量转为2的n次幂形式，暂时保存在threshold中，后续在resize中读取
    }
	//有参构造，指定初始容量，扩容因子默认不变
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

add插入元素机制

插入时调用的是HashMap的putVal（插值）方法，插入元素前需要计算对象的hash值

	//HashMap的put方法，最终调用putVal方法
	public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);//先计算hash值，再插入元素
    }

插入元素详细过程：

• 先通过hash算法来计算其hash值（hashCode处理而来）
• 根据hash值获得对应table表中的存储位置（hash值和n-1进行与运算计算而来）
• 确定位置后，判断该位置是否有元素存在。若没有，则直接插入到该位置
• 若有，则依次比较，若该位置上的链表中有元素和新元素相同，则放弃添加，若没有和新元素相同的，则插入新元素到当前位置链表的末尾。（拉链法）

putVal插入方法详解

	//插入元素方法putVal
	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //第一次插入，也就是table数组为空时
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;//扩容，并返回扩容后的size
        //如果hash值对应的位置的结点P为空，插入为首元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //若新元素和table表对应位置的元素P相同，则不插入
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //若新元素和table表对应位置的元素P不同，且此时已经树化，则遍历红黑树再判断是否插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //若新元素和table表对应位置的元素P不同，且还没有树化，则继续遍历链表判断是否要插入
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//若找到结尾还没找到相同的元素，插入到链表尾
                        p.next = newNode(hash, key, value, null);//插入
                        if (binCount >= TREEIFY_THRESHOLD - 1) //判断链表长度是否>8，进行树化(也可能扩容)
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&//如果找到某元素和新元素相同
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;//指针后移
                }
            }
            if (e != null) { //e不为空说明找到了相同key的元素，则不再插入新的，但是会更新对应的value值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)//覆盖value
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//如果总结点数大于临界值（0.75*），则扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }
        /**
         * 注：hash值通过(n - 1) & hash操作返回一个0到n-1的数，就是把【hash值】映射到【数组下标】
         */

总结：能插入进去的条件是：和其它hash值相同的结点相比，新结点的equals（）返回结果不一样

如何更具key计算存储位置？

先计算hash值：将key的hashCode值进行右移16位

	//hash值计算方法
	static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//hashCode无符号右移16位
    }

再将hash值和n-1进行与运算

(n - 1) & hash // n=tab.length

如何判断元素相同？

在之前的putVal方法中截取的以下代码可知：

	if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) 

代码解析：首先在hash值的前提下，然后对象（引用）相同或者对象的equals（）方法返回结果为真，就算是相等。而由于对象引用相等→对象equals（）必然相等，所以可以得到结论为：满足1.hash值相同 2.值相等（equals（）返回为真）时 判定为重复元素。（核心：值相同）

扩容机制

table表初始容量是16，每次插入元素后立即判断是否要扩容，有如下两种情况会扩容：

①、HashSet中元素个数达到【当前最大容量*负载因子（默认是0.75）】（临界值）的时候，说明table表快满了，再不扩容就很有可能频繁产生冲突（减低查找效率），这时对table表进行扩容，每次扩容后容量变成原来的2倍。（元素过多）

如：初始为16，达到16 * 0.75=12时，扩容为2 * 16=32，再达到32 * 0.75=24时，扩容为32 * 2=64，依次扩容…

②、若某链表过长，超过了8（且此时数组table表容量不到64时），冲突过多，这时说明可能是table表的容量不够引起了大量冲突，这时也进行对数组的扩容。（链表过长（冲突过多），且容量不大）

如：先往一个链表上连续添加8个元素，添加第9个时，table扩容为32，添加第10个时，扩容为64，添加第11个时，树化

注意：

• size和tab.length是不同的，size是所有链表中元素加起来的个数，值实际存储的元素个数；length后者是数组长度，指未发生冲突的最大容量；如果实际size>length，则必然产生冲突，降低查找效率。
• 因为jdk1.7时hashmap是用数组+链表构成的，没有树化机制，故jdk1.7时只有一种扩容情况：那就是当前元素个数超过了【当前最大容量*负载因子】的情况

扩容代码：

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) {
            //超过2的30次方时
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //正常扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)//注意这里newCap这里已经等于2*oldCap了
                newThr = oldThr << 1; // 让扩容临界值*2
        }
    	//未进行初始化，且自定义了初始容量（情况一）
        else if (oldThr > 0) ，则新容量设为自定义的值
            newCap = oldThr;//
    	//未进行初始化，且没有定义初始容量（情况二）
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;//使用初始值
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//设置初始阈值
        }
    	//重新计算新的阈值（对应情况二）
        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"})
    	//新建一个为新容量大小的Node数组
        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) {
                    //置空原数组头元素
                    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没有初始化，则创建一个指定容量（默认为8）的Node数组

如果不是第一次插入元素，且要进行扩容的话：

• 计算新的容量和阈值（让他们乘以2）
• 新建一个之前容量为两倍的Node数组
• 将旧数组的值重新计算哈希值，插入到新数组中

树化机制

若当位置的链表长度超过8，且整个数组table的元素个数超过64时，这说明在容量较大的情况下冲突还是很多，这时候就要改变结构了。此时当前的链表的会进行树化，变成一颗红黑树，所有的Node结点变成TreeNode结点。

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //若只是table表的大小不足64，则扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        //若容量达到了64，则树化
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

在jdk1.7和jdk1.8区别

• 底层数据结构不同： JDK1.7是数组+链表； JDK1.7是数组+链表+红黑树
• hash算法不同，jdk1.8的扰动此时更少
• 扩容机制不同：JDK1.7只有一种情况扩容，而JDK1.8有两种情况会扩容（详见上述）；且jdk1.7是插入前扩容，jdk1.8是插入后扩容
• 插入元素方式不同：jdk1.7采用头插法，jdk1.8采用尾插法

经典问题

某条链表上的所有结点hashcode一定相等吗？

一定相等，同一条链表上的元素存储位置下标一定相同，而存储位置下标由于hash值和数组长度-1与运算而来，由于数组长度-1换算成二进制永远是n个1，所以与运算结果（位置下标）相同的话hash值也一定相同，而hash值由hashCode右移16位而来，hash值相同则hashCode相同，则存储位置。

逻辑：位置下标相同→hash值相同→hashCode相同

何时扩容？

两种情况（jdk1.7时只有第一种情况）：

• 一种是元素过多，元素个数达到最大容量的四分之三（默认0.75）时；
• 另一种情况是某链表过长，长度超过8，且当前容量小于64时（注意链表长度每+1，就会扩容一次）

何时树化？

某链表长度超过8，且容量（table表长度）超过64时，将该链表数化为红黑树

为什么hashset和hashmap的实现效果不同？

hashset底层使用hashmap中的value值都统一，不允许key值相同，从而实现了元素无重复。

在hashmap中，value值由用户定义，由于key值不允许相同，故对应value值只能有一个，保存的是最后一个定义的value（即覆盖），故实现了value值唯一，其本质上都是key值唯一。