HashMap源码简单分析

HashMap源码简单分析 hashMap总结 hashMap结构

hashMap结构如图 一般是由数组和链表组成 红黑树暂时忽略 比较难 也没什么必要

数组：

transient Node[] table;

链表：

static class Node implements Map.Entry {
        final int hash;
        final K key;	
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
 }

数组我们很好理解,而这里的链表我的好好说说，从上面的结构可以看到 Node next; 其实就是下一个节点，简单来说就是套娃,举个例子 就是A包含B ,B包含C 依次下去，其实数组每个位置其实只是放了一个node节点对象，只是我们不停的获取node节点对象中next属性从而获取下一个node节点的值从而构成了我们所说的链表

注意：我们本文将数组中位置称为bucket. 比如说数组1号位置 我们称为1号bucket

重点：

​ (1)负载因子:

final float loadFactor; //键值对数量/数组长度 = loadFactor  不能超过这个值，否则就要扩容 

​ (2)键值对最大数量

int threshold; //键值对最大数量  = 数组长度*loadFactor

put 源码分析

  public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
 }
 	
	//hashMap的hash算法
   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 

当我们使用put方法的时候,底层实际上去调用的putVal的方法,这边我们需要注意点是hashMap使用自己的hash算法.

(1) hash()算法

 	static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

hashMap的hash算法是根据key来进行计算的,我们这边需要把这个算法进行拆分为3个部分，【1】h = key.hashCode()，【2】h >>> 16，【3】^

【1】h = key.hashCode()

这个就是跟key本身的hash算法有关的,hash值是32位的 0000 0000 0000 0000 0000 0001 0000 0000，一般我们我们是String,HashMap 内部实现是通过 key 的 hashcode 来确定 value 的存储位置，因为字符串是不可变的，所以当创建字符串时，它的 hashcode 被缓存下来，不需要再次计算，所以相比于其他对象更快。

【2】h >>> 16

这个是将计算后的hash值无符号右移16位.比如说 h = 0000 0000 0000 0001 0000 0001 0000 0000 右移16位后得到 0000 0000 0000 0000 0000 0000 0000 0001

【3】^

这个是进行异或的位运算 之所以进行位运算 就是让这些存放的更加均匀 0000 0000 0000 0001 0000 0001 0000 0000 ^ 0000 0000 0000 0000 0000 0000 0000 0001 = 0000 0000 0000 0001 0000 0001 0000 0001

注意点：为什么更加均匀了 ？？？

解答： 因为1出现的次数可能会增加了.这跟他确定键值对存储到数组哪个位置有关系。

tab[i = (n - 1) & hash] //确定键值对存储到数组哪个位置     n=数组长度 hash=hashMap中hash算法值

这边是进行&运算 如果说hash值中1 次数增加了 那么进行计算后的结果值就会增加 举个例子

0000 0000 0000 0000 0000 0000 0000 0100  hash值   
&
0000 0000 0000 0000 0000 0000 0000 0111  n-1(数组长度 -1)     
0000 0000 0000 0000 0000 0000 0000 0100

0000 0000 0000 0000 0000 0000 0000 1100  hash值   
&
0000 0000 0000 0000 0000 0000 0000 0111  n-1(数组长度 -1)     
0000 0000 0000 0000 0000 0000 0000 0100

上面我们可以发现当hash值变化,数组值不变化，进行位计算后值却没有变化，那么他们将放在数组同一个位置上，这就是由于hash值中1的数量太少，造成键值对还是在同一个数组的位置上，1进行&位计算后的结果有2种情况可以是0或者1,如果0来进行&计算那么只有可能是0。所以说hash值中1越多越好,涉及到概率的问题了.你懂的.......

putVal 源码分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {

        Node[] tab; Node p; int n, i;
        
    	//判断HashMap中数组是否设置默认的初始值 一般第一次put都会走这里,用resize方法进行设置数组的默认值 
        if ((tab = table) == null || (n = tab.length) == 0){
            n = (tab = resize()).length;
        }
        
    	//判断数组某个位置上是否存在node对象 	
        if ((p = tab[i = (n - 1) & hash]) == null){
            //不存在 说明不存在链表，就添加一个node对象进去作为链表的头-》这里需要熟悉上面所讲的链表结构 
            tab[i] = newNode(hash, key, value, null);
        }else {
            //存在 添加到链表的尾部
            Node e; K k;
            
          
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //存储的key与bucket中的第一个节点key相同则替换value
                e = p;
            else if (p instanceof TreeNode)
                //bucket里面是红黑树
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                //bucket是链表
                for (int binCount = 0; ; ++binCount) {
                    //如果链表最后一个节点next属性为null 则将要存储的键值对作为最后一个节点
                    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相同 就替换对应的value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
  
        }
        ++modCount;
    
    	//判断数组中键值对的数量是否大于可负载键值对的最大数量 大于则扩容 
        if (++size > threshold)
            resize();
    
        return null;
    }

resize 源码分析

final Node[] resize() {
    	//扩容之前的数组 以及长度 可负载键值对数量	
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
    	//扩容后的数组 以及可负载的键值对数量
        int newCap, newThr = 0;
    
    	
        if (oldCap > 0) {
      		//当扩容之前的数组长度大于0
            //扩容之前的数组长度大于等于最大长度 1 << 30 数组长度不发生变化 不会在进行扩容了
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)	//注意 这里是将扩容之前的数组长度*2 赋值给扩容后的数组长度 并且判断扩容后的长度是否小于1 << 30最大长度 并且扩容前的数组长度大于等于16 这时候他的可负载的键值对*2 并赋值给扩容后的可负载键值对数量
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr; //这里暂时没有理解 应该问题不大 
        else {               
            //当new HashMap() 第一次put 会走这里进行初始化 设置新数组的默认长度是16 且 计算他的可负载键值对数量 16*0.75 = 12 
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    
    	// 只有当new hash(15) 设置了初始容量值小于16且需要扩容的时候才会走这里  这里也是计算可负载键值对数量
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
    
    
    
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
    	
    	//上面是将扩容后的数组长度 可负载的键值对数量设置好 下面则是设置分拆数组的链表
    	//遍历数组 进行真正的扩容 
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node 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)e).split(this, newTab, j, oldCap);
                    else { 
                        //我们主要分析这边
                        //这里是数组是链表 且链表中值数量大于等于2 才会进行链表分拆 此处主要是用的尾插法
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        
                        //简单总结一下： 这里利用链表中每个节点的hash值和扩容前数组长度进行与运算 = 0 放在低位链表  !=0 放在高位链表  遍历完链表后高为链表放到 数组下标为[原有数组下标+扩容前数组长度] 位置下
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                // 简单分析低位链表如何设置的 拿到第一个低位键值对节点 放在第一位 拿到第二个低位键值对节点将其存入第一位键值对节点next属性中,同时把第二位键值对节点暴露出来.依次这样,高位链表同理
                                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;
    }

1.7 死循环分析

hashMap 在1.7的时候使用的是头插法 而 1.8使用的是尾插法 但是他们目前来说都会造成一个最重要的问题就是多线程put的时候会死循环的问题 只是死循环的地点不同 一个是 *** 作链表扩容的时候 一个是变树的阶段 本文章只针对1.7多线程 *** 作链表的时候造成的死循环做出分析

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;　　　　　//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);　　　　　　　　　 //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }