HashMap源码浅析1.7

Jdk 1.7

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：国际域名空间、虚拟主机、营销软件、网站建设、岚山网站维护、网站推广。

1. 数据结构

   1.7版本的HashMap采用数组加链表的方式存储数据,数组是用来存储数据的在数组的位置,链表则时用来存放数据的,由于根据hash可能发生碰撞,一个位置会出现多个数据,所以采用链表结构来存储数据,结构如下图所示.

   

2. 基本成员变量
   capacity数组的长度

   // 当前数组的容量,始终保持2^n,可以扩容,扩容后是当前线程的2倍
       // 1 << 4 = 1 * 2^4   1的二进制左移4位
       static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

   capacity的最大值 (扩容时,如果已经是最大值,会设置成Integer.MAX_VALUE)

   // 如果传入的值大于该值,也会替换为 1 << 30(2 ^ 30)
       static final int MAXIMUM_CAPACITY = 1 << 30;

   factor负载因子(用来算阈值)

   // 负载因子 默认值为 0.75
       static final float DEFAULT_LOAD_FACTOR = 0.75f;

   threshold阈值(capacity * factor),扩容时用来判断有没有大于等于这个值
   int threshold;

   size

   // map的容量
       transient int size;

   Entry(存储数据的地方)

   static class Entry implements Map.Entry {
       // 就是传输key
       final K key;
       // 就是value
       V value;
       // 用于指向单项链表的下一个Entry
       Entry next;
       // 通过key计算的hash值
       int hash;
   
       /**
        * Creates new entry.
        */
       Entry(int h, K k, V v, Entry n) {
           value = v;
           next = n;
           key = k;
           hash = h;
       }

3. 构造方法
   有参构造

   public HashMap(int initialCapacity, float loadFactor) {
                   // 容量不能小于0
                   if (initialCapacity < 0)
                           throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
                   // 容量大于MAXIMUM_CAPACITY时,等于MAXIMUM_CAPACITY
                   if (initialCapacity > MAXIMUM_CAPACITY)
                           initialCapacity = MAXIMUM_CAPACITY;
                   // loadFactor不能小于等于0
                   if (loadFactor <= 0 || Float.isNaN(loadFactor))
                           throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
   
                   this.loadFactor = loadFactor;
                   threshold = initialCapacity;
                   init();
               }

   无参构造
   // 使用默认的容量和负载因子

   public HashMap() {
                       this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
               }

4. 基本方法
   Put方法(具体流程看下面的执行流程分析或者代码注释)
   具体执行流程:
   (1) 判断当前table是否为EMPTY_TABLE={},证明没有初始化,调用inflateTable初始化,具体详见后面inflateTable()方法代码分析.
   (2) 判断key是否为null,是null调用putForNullKey插入方法(证明1.7的HashMap允许key为null),具体详见后面putForNullKey()方法代码分析.
   (3) 获取当前key的hash,然后算出hash在数组的位置i(hash & (tab.length - 1)).给大家解释下为什么数组的长度必须是2的冥,是和算i的位置有关系,因为如果一个数是2的冥次方,假如这个数是n,那么 hash % n = hash & (n -1),这就是为什么i的位置一定会在数组长度范围中,因为取得是余数,还有就是位运算比直接取余效率高.
   (4) 判断当前位置上有没有值table[i],如果有值,遍历链表,找出相同的key和hash,然后替换value,返回旧的value(oldOvalue).
   (5) 如果没有找到相同的key和hash,那么就添加这个节点(Entry),方法addEntry().
   (6) 在addEntry()方法里面判断需不需扩容,需要就扩容,调用扩容方法resize(),然后在调用 createEntry()方法添加节点,size++.

           // 插入
           public V put(K key, V value) {
                   // 当插入第一个元素时,需要初始化
                   if (table == EMPTY_TABLE) {
                           // 初始化
                           inflateTable(threshold);
                   }
                   // key为null是
                   if (key == null)
                           // 找出key为null,替换返回旧值
                           // 没有则新添加一个key为null的Entry
                           return putForNullKey(value);
                   // 计算hash值
                   int hash = hash(key);
                   // 根据hash,找出table的位置
                   int i = indexFor(hash, table.length);
                   // 因为在table[i]中,可能存在多个元素(同一个hash),所以要基于链表实现
                   // 循环table[i]上的链表(不为空),存在就修改,返回旧值(oldValue)
                   for (Entry e = table[i]; e != null; e = e.next) {
                           Object k;
                           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                                   V oldValue = e.value;
                                   e.value = value;
                                   e.recordAccess(this);
                                   return oldValue;
                           }
                   }
   
                   modCount++;
                   // 为空或者不存在,则新添加(需要计算容量)
                   addEntry(hash, key, value, i);
                   return null;
           }

   inflateTable初始化方法(懒加载,只有第一次调用put方法时才初始化)

               // 初始化table
               private void inflateTable(int toSize) {
                       // Find a power of 2 >= toSize
                       // 计算出大于等于toSize最邻近的2^n(所以capacity一定是2^n)
                       int capacity = roundUpToPowerOf2(toSize);
                       // 在此计算阈值 capacity * loadFactor
                       threshold = (int) Math.min(capacity * loadFactor, 
                       MAXIMUM_CAPACITY + 1);
                       // 创建capacity大小的capacity数组就是hashmap的容器
                       table = new Entry[capacity];
                       initHashSeedAsNeeded(capacity);
               }

   putForNullKey方法(存储key为null的数据)
   具体执行流程:
   (1) 遍历table[0]处的链表(说明nullkey永远存在table[0]位置)
   (2) 找到key==null 的数据,替换value,返回旧的value
   (3) 没有找到,就在table[0]位置添加一个key为null的Entry,调用addEntry()方法.

       private V putForNullKey(V value) {
                       // 遍历table[0]的链表
                       // 找到key等于null的,把值覆盖,返回旧值(oldValue)
                       for (Entry e = table[0]; e != null; e = e.next) {
                               if (e.key == null) {
                                       V oldValue = e.value;
                                       e.value = value;
                                       e.recordAccess(this);
                                       return oldValue;
                               }
                       }
                       modCount++;
                       // 没有找到就添加一个key为null的Entry
                       addEntry(0, null, value, 0);
                       return null;
               }

   addEntry方法(判断是否需要扩容,然后在添加节点Entry)
   执行流程:
   (1) 判断是否需要扩容,size(每次添加一个entry size++)>=threshold(阈值)并且当前这个key的hash算出的位置必须有元素才扩容,具体详解看代码注释.
   (2) 如果满足扩容条件,调用扩容方法resize(2 * table.length),table长度扩大2倍,然后重新算当前key的hash和位置bucketIndex.
   (3) 调用createEntry()方法,添加节点.

               // 添加节点到链表
               void addEntry(int hash, K key, V value, int bucketIndex) {
                       /*
                       * 扩容机制必须满足两个条件
                       * (1) size大于等于了阈值
                       * (2) 到达阈值的这个值有没有发生hash碰撞
                       *  所以阈值在默认情况下是12 是一个重要节点
                       *  扩容范围是12-27
                       *  最小12进行扩容,最大27时必须进行扩容
                       *  分析最小12扩容
                       *   当size是12时,判断有没有hash碰撞,有扩容,没有继续不扩容.
                       *   分析最大27扩容
                       *   当12没有进行扩容时,size大于阈值就一直满足了
                       *   就只需要判断接下来的hash有没碰撞,有就扩容,没有就不扩容
                       *   最大是一种极端情况,前面11个全部在一个table索引上,接下来
                       *   15个全部没有碰撞,11+15=26,table所有索引全部有值,在插入一个
                       *   值必须碰撞就是26+1=27最大进行扩容
                       * */
                       if ((size >= threshold) && (null != table[bucketIndex])) {
                               // 扩容(方法里面重点讲)
                               resize(2 * table.length);
                               // 计算hash,null时为0
                               hash = (null != key) ? hash(key) : 0;
                               // 计算位置
                               bucketIndex = indexFor(hash, table.length);
                       }
   
                       createEntry(hash, key, value, bucketIndex);
               }

   createEntry方法(在传入位置加入一个节点)

   // 创建一个新的Entry,放在链表的表头,size++
               void createEntry(int hash, K key, V value, int bucketIndex) {
                       // 这里可以理解为当前的第一个节点
                       Entry next = table[bucketIndex]; 
                       // 创建一个新的节点,next节点是当前的第一个节点,然后设置到bucketIndex位置
                       table[bucketIndex] = new Entry<>(hash, key, value, next); 
                       size++;
               }

   resize方法(扩容方法,扩容成原来的2倍)
   执行流程:
   (1) 计算oldTable的长度,如果oldTable的长度已经是最大值了,那么就把阈值设置成Integer.MAX_VALUE,return.
   (2) 根据新的容量创建table.
   (3) 调用transfer方法转移数据.
   (4) 将新table赋值给旧table,重新就算阈值.

       void resize(int newCapacity) {
                       Entry[] oldTable = table;
                       int oldCapacity = oldTable.length;
                       // 如果当前值已经是最大值了(2^30),就设置阈值为Integer的最大值
                       if (oldCapacity == MAXIMUM_CAPACITY) {
                               threshold = Integer.MAX_VALUE;
                               return;
                       }
   
                       // 根据传入Capacity重新创建新数组,扩容完成
                       Entry[] newTable = new Entry[newCapacity];
                       // 把原来的数据迁移到新的table(newTable)
                       transfer(newTable, initHashSeedAsNeeded(newCapacity));
                       // 将table设为新table(newTable)
                       table = newTable;
                       // 设置新的阈值
                       threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
               }

   transfer方法(负载转移数据,把旧table的数据迁移到新table,至此扩容完成)
   注意:扩容完成后链表的顺序会反转,如下图解释.
   

               // 扩容之后迁移数据(重新计算hash,分配地址),很耗性能
               // 顺便提一下jdk7(get死循环)就是扩容时造成,造成环形链表
               void transfer(Entry[] newTable, boolean rehash) {
                       // 新数组的容量
                       int newCapacity = newTable.length;
                       // 遍历原table
                       for (Entry e : table) {
                               // 轮询e不等于null
                               while(null != e) {
                                       // 保存下个元素
                                       Entry next = e.next;
                                       if (rehash) {
                                               // 计算出key的hash
                                               e.hash = null == e.key ? 0 : hash(e.key);
                                       }
                                       // 计算出table的位置
                                       int i = indexFor(e.hash, newCapacity);
                                       e.next = newTable[i];
                                       newTable[i] = e;
                                       e = next;
                               }
                       }
               }

   get方法(通过key获取数据)
   执行流程:
   (1) 判断key是否为null,为null调用getForNullKey()方法
   (2) 不为null,调用getEntry方法

           // get方法
               public V get(Object key) {
                       // key等于null
                       if (key == null)
                               return getForNullKey();
                       // 不为null是查找
                       Entry entry = getEntry(key);
   
                       return null == entry ? null : entry.getValue();
               }

   getForNullKey()方法(遍历table[0]位置数据,找到key==null的返回)

            private V getForNullKey() {
                       // 没数据
                       if (size == 0) {
                               return null;
                       }
                       // 从table[0]处遍历链表,找到key=null的返回
                       for (Entry e = table[0]; e != null; e = e.next) {
                               if (e.key == null)
                                       return e.value;
                       }
                       return null;
               }

   getEntry()方法(根据hash算出位置,遍历当前位置的数据,找到key和hash相同的返回)

       final Entry getEntry(Object key) {
                       // 没数据
                       if (size == 0) {
                               return null;
                       }
                       // 获取hash
                       int hash = (key == null) ? 0 : hash(key);
                       // 获取table的位置,找到hash和key相同的返回
                       for (Entry e = table[indexFor(hash, table.length)];
                                e != null;
                                e = e.next) {
                               Object k;
                               if (e.hash == hash &&
                                               ((k = e.key) == key || (key != null && key.equals(k))))
                                       return e;
                       }
                       return null;
               }

   remove()方法

           final Entry removeEntryForKey(Object key) {
                       // 没数据
                       if (size == 0) {
                               return null;
                       }
                       // 获取hash
                       int hash = (key == null) ? 0 : hash(key);
                       // 计算位置
                       int i = indexFor(hash, table.length);
                       // 获取i位置的entry
                       Entry prev = table[i];
                       Entry e = prev;
   
                       // 遍历链表
                       while (e != null) {
                               Entry next = e.next;
                               Object k;
                               // 找到了hash和key相等的
                               if (e.hash == hash &&
                                               ((k = e.key) == key || (key != null && key.equals(k)))) {
                                       modCount++;
                                       // 容量减减
                                       size--;
                                       // 说明是第一个元素
                                       // 把头结点设置成他的下一个元素
                                       if (prev == e)
                                               table[i] = next;
                                       // 删除当前e,把上一个元素的next指向当前e.next
                                       // 1 -2 -3-null 删除2,把1的next指向2的next,就是1-3-null
                                       else
                                               prev.next = next;
                                       e.recordRemoval(this);
                                       return e;
                               }
                               prev = e;
                               e = next;
                       }
   
                       return e;
               }

5. 总结:

   1.7HashMap需要注意的是在扩容时,不是到达阈值就会扩容的,还要判断当前位置是否有值,来决定会否扩容,还有就是扩容的时候是遍历了每个位置的链表,重新计算hash和位置,然后插入新的table,每条链的顺序是和原来相反的,这样如果数据量很大,其实很消耗性能.还有就是采用链表的数据结构来存储数据,如果hash碰撞严重的话,这条链就会很长,这样不管是get,或者put都需要遍历链,这样也遍历也很慢,这是1.7HashMap个人觉得一些缺陷吧(因为看了1.8 HashMap 源码浅析).
   PS 1.7的HashMap在多线程下扩容会导致环链,然后导致再次遍历链表的时候回是死循环,进而cpu100%,所以多线程下就不要用HashMap.