Java Collection HashMap源码分析

HashMap 底层实现：数组+链表+红黑树

在 JDK1.7 中，HashMap 是由 数组+链表构成的

在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成

详见link。

HashMap 重要的字段

1. Node<K,V>[] table
   • 我们说 HashMap 是由数组+链表+红黑树组成，这里的数组就是 table 字段。后面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 1.8 声明数组的长度（不包含链表+红黑树）总是 2的n次方(一定是合数)，为什么这里要求是合数，一般我们知道哈希算法为了避免冲突都要求长度是质数，这里要求是合数，下面在介绍 HashMap 的hashCode() 方法(散列函数)，我们再进行讲解。
2. size
   • 集合中存放key-value 的实时对数。
3. loadFactor
   • 装载因子，是用来衡量 HashMap 满的程度，计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。
   • 默认的负载因子0.75 是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于1。
4. threshold
   • 计算公式：capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍.
5. TREEIFY_THRESHOLD
   • 当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增) -- 默认值为8
6. UNTREEIFY_THRESHOLD
   • 当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增) -- 默认值为6
7. modCount
   • modCount域变量，就是用于实现hashMap中的fail-fast。出现这种情况，往往是在非同步的多线程并发操作。
     在对Map的做迭代(Iterator)操作时，会将modCount域变量赋值给expectedModCount局部变量。在迭代过程中，用于做内容修改次数的一致性校验。若此时有其他线程或本线程的其他操作对此Map做了内容修改时，那么就会导致modCount和expectedModCount不一致，立即抛出异常ConcurrentModificationException。
   • modCount的使用类似于并发编程中的CAS（Compare and Swap）技术。

//----------------关键字段--------------------

//默认 HashMap 集合初始容量为16（必须是 2 的倍数）	
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
static final int MAXIMUM_CAPACITY = 1 << 30; // aka 2^30

// 此映射中包含的键值映射的数量。（集合存储键值对的数量）
transient int size;

// 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
//主要用于迭代器中的快速失败
transient int modCount;


//默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
static final int TREEIFY_THRESHOLD = 8;

//当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
static final int UNTREEIFY_THRESHOLD = 6;

//初始化使用，长度总是 2的幂
transient Node<K,V>[] table;

//调整大小的下一个大小值（容量*加载因子）。capacity * load factor
int threshold;

//散列表的加载因子。
final float loadFactor;

//----------------补充学习字段--------------------

//序列化和反序列化时，通过该字段进行版本一致性验证
private static final long serialVersionUID = 362498820763181265L; 

/**(JDK1.8新增)
* 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，
* 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* 保存缓存的entrySet（）
*/
transient Set<Map.Entry<K,V>> entrySet;

　　

　　

HashMap 哈希表算法

散列函数来确定索引的位置。散列函数设计的越好，使得元素分布的越均匀。HashMap 是数组+链表+红黑树的组合，我们希望在有限个数组位置时，尽量每个位置的元素只有一个，那么当我们用散列函数求得索引位置的时候，我们能马上知道对应位置的元素是不是我们想要的，而不是要进行链表的遍历或者红黑树的遍历，这会大大优化我们的查询效率。我们看 HashMap 中的哈希算法：

主要分为三步：

　　①、取 hashCode 值： key.hashCode()

　　②、高位参与运算：通过h>>>16，让高16位 异或 原始hash

　　③、取模运算：将取模运算变成位的与运算，(数组的长度-1) & hash 

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

//这一步不在hash函数中，是在后面添加元素putVal()方法中进行位置的确定  
 i = (table.length - 1) & hash;

面试题1：hash值的具体算法是什么？

JDK1.8 中还有个高位参与运算，hashCode() 得到的是一个32位 int 类型的值，通过hashCode()的高16位 异或 低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

下面举例说明下，n为table（数组）的长度：

　　

 

面试题2：为什么要保证数组的长度总是2的n次方？

为了让数组元素分布均匀，我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length)，但是计算机都是二进制进行操作，取模运算相对开销还是很大的，那该如何优化呢？

原因1：HashMap 使用的方法很巧妙，它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对 length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)

原因2：表的长度为2的次幂，那么(length-1)的二进制最后一位一定是1，在对hash值做“与”运算时，最后一位就可能为1，也可能为0，换句话说，取模的结果既有偶数，又有奇数。设想若(length-1)为偶数，那么“与”运算后的值只能是0，奇数下标的bucket就永远散列不到，会浪费一半的空间。

　

HashMap put()添加方法

当了解了以上的变量和用途后，接下来看下put()方法的具体实现：

如上面的截图代码所示，整个put方法的处理过程，可拆分为四部分：

• part1：特殊key值处理，key为null；
• part2：计算table中目标bucket的下标；
• part3：指定目标bucket，遍历Entry结点链表，若找到key相同的Entry结点，则做替换；
• part4：若未找到目标Entry结点，则新增一个Entry结点--JDK1.7 头插法；JDK1.8尾插法。

不知大家有没有发现，上面截图中的put()方法是有返回值的，场景区分如下：

• 场景1：若执行put操作前，key已经存在，那么在执行put操作时，会使用本次的新value值来覆盖前一次的旧value值，返回的就是旧value值；
• 场景2：若key不存在，则返回null值。

HashMap resize()扩容方法

HashMap 中插入元素时，如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity * loadFactor），这里的threshold不是数组的最大长度。

JDK1.7首先是创建一个新的大容量数组，然后依次重新计算原集合所有元素的索引，然后重新赋值。如果数组某个位置发生了hash冲突，使用的是单链表的头插入方法，同一位置的新元素总是放在链表的头部，这样与原集合链表对比，扩容之后的可能就是倒序的链表了。

JDK1.8使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。JDK1.8什么场景下会触发扩容？
场景1：哈希table为null或长度为0；
场景2：Map中存储的k-v对数量超过了阈值threshold；
场景3：链表中的长度超过了TREEIFY_THRESHOLD，但表长度却小于MIN_TREEIFY_CAPACITY。

HashMap 遍历方式

　首先构造一个 HashMap 集合：

1 HashMap<String,Object> map = new HashMap<>();
2 map.put("A","1");
3 map.put("B","2");
4 map.put("C","3");

　　①、分别获取 key 集合和 value 集合。

1 //1、分别获取key和value的集合
2 for(String key : map.keySet()){
3     System.out.println(key);
4 }
5 for(Object value : map.values()){
6     System.out.println(value);
7 }

　　②、获取 key 集合，然后遍历key集合，根据key分别得到相应value

1 //2、获取key集合，然后遍历key，根据key得到 value
2 Set<String> keySet = map.keySet();
3 for(String str : keySet){
4     System.out.println(str+"-"+map.get(str));
5 }

　　③、得到 Entry 集合，然后遍历 Entry

1 //3、得到 Entry 集合，然后遍历 Entry
2 Set<Map.Entry<String,Object>> entrySet = map.entrySet();
3 for(Map.Entry<String,Object> entry : entrySet){
4     System.out.println(entry.getKey()+"-"+entry.getValue());
5 }

　　④、迭代

1 //4、迭代
2 Iterator<Map.Entry<String,Object>> iterator = map.entrySet().iterator();
3 while(iterator.hasNext()){
4     Map.Entry<String,Object> mapEntry = iterator.next();
5     System.out.println(mapEntry.getKey()+"-"+mapEntry.getValue());
6 }

　　基本上使用第三种方法是性能最好的，

　　第一种遍历方法在我们只需要 key 集合或者只需要 value 集合时使用；

　　第二种方法效率很低，不推荐使用；

　　第四种方法效率也挺好，关键是在遍历的过程中我们可以对集合中的元素进行删除。

HashMap fail-fast策略

什么是fail-fast？我们可以称它为"快速失效策略"。

使用场景：当在对HashMap做迭代操作时，可能出现其他线程对该hashmap也做了操作/本线程做了其他修改操作。这里使用到了前面提到的modCount域变量来检测是否被其他线程/该线程修改。一旦出现modCount和expectedModCount不一致，立即抛出异常ConcurrentModificationException。

在HashMap中，我们前面提到的modCount域变量，就是用于实现hashMap中的fail-fast。出现这种情况，往往是在非同步的多线程并发操作。
在对Map的做迭代(Iterator)操作时，会将modCount域变量赋值给expectedModCount局部变量。在迭代过程中，用于做内容修改次数的一致性校验。若此时有其他线程或本线程的其他操作对此Map做了内容修改时，那么就会导致modCount和expectedModCount不一致，立即抛出异常ConcurrentModificationException。

modCount的使用类似于并发编程中的CAS（Compare and Swap）技术。我们可以看到这个方法中，每次在发生增删改的时候都会出现modCount++的动作。而modcount可以理解为是当前hashmap的状态。每发生一次操作，状态就向前走一步。设置这个状态，主要是由于hashmap等容器类在迭代时，判断数据是否过时时使用的。hashmap在迭代数据的时候，无法保证边迭代，边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变，则会快速抛出一个ConcurrentModificationException异常，终止迭代行为。

HashMap在迭代时做"错误"删除操作，导致抛出ConcurrentModificationException异常

public static void main(String[] args) {
  Map<String, Integer> testMap = new HashMap<>();
  testMap.put("s1", 11);
  testMap.put("s2", 22);
  testMap.put("s3", 33);

  for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
      String key = entry.getKey();
      if ("s1".equals(key)) {
          testMap.remove(key);
      }
  }
}

---- output ---
Exception in thread "main" java.util.ConcurrentModificationException
  at java.util.HashMap$HashIterator.nextNode(HashMap.java:1437)
  at java.util.HashMap$EntryIterator.next(HashMap.java:1471)
  at java.util.HashMap$EntryIterator.next(HashMap.java:1469)
    ...

HashMap在迭代时做"正确"删除操作

在迭代时做正确的删除Map元素的姿势：只有一个，Iteator的remove()方法

Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
    Entry<String, Integer> next = iterator.next();
    System.out.println(next.getKey() + ":" + next.getValue());
    if (next.getKey().equals("s2")) {
        iterator.remove();
    }
}

 

HashMap 线程不安全在哪里？

数据覆盖问题

JDK7头插法，JDK8尾插法

两个线程执行put()操作时，可能导致数据覆盖。JDK7版本和JDK8版本的都存在此问题，这里以JDK7头插法为例。

假设A、B两个线程同时执行put()操作，且两个key都指向同一个buekct，那么此时两个结点，都会做头插法。 先看这里的代码实现：

public V put(K key, V value) {
    ...
    addEntry(hash, key, value, i);
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    ...
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

看下最后的createEntry()方法，首先获取到了bucket上的头结点，然后再将新结点作为bucket的头部，并指向旧的头结点，完成一次头插法的操作。
当线程A和线程B都获取到了bucket的头结点后，若此时线程A的时间片用完，线程B将其新数据完成了头插法操作，此时轮到线程A操作，但这时线程A所据有的旧头结点已经过时了（并未包含线程B刚插入的新结点），线程A再做头插法操作，就会抹掉B刚刚新增的结点，导致数据丢失。

其实不光是put()操作，删除操作、修改操作，同样都会有覆盖问题。

扩容时导致死循环

JDK7头插法，JDK8尾插法

这是最常遇到的情况，也是面试经常被问及的考题。但说实话，这个多线程环境下导致的死循环问题，并不是那么容易解释清楚，因为这里已经深入到了扩容的细节。这里尽可能简单的描述死循环的产生过程。

另外，只有JDK7及以前的版本会存在死循环现象，在JDK8尾插法中，resize()方式已经做了调整，使用两队链表，且都是使用的尾插法，及时多线程下，也顶多是从头结点再做一次尾插法，不会造成死循环。而JDK7能造成死循环，就是因为resize()时使用了头插法，将原本的顺序做了反转，才留下了死循环的机会。

在进一步说明死循环的过程前，我们先看下JDK7中的扩容代码片段：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

其实就是简单的链表反转，再进一步简化的话，分为当前结点e，以及下一个结点e.next。我们以链表a->b->c->null为例，两个线程A和B，分别做扩容操作。

原表：

线程A和B各自新增了一个新的哈希table，在线程A已做完扩容操作后，线程B才开始扩容。此时对于线程B来说，当前结点e指向a结点，下一个结点e.next仍然指向b结点（此时在线程A的链表中，已经是c->b->a的顺序）。按照头插法，哈希表的bucket指向a结点，此时a结点成为线程B中链表的头结点，如下图所示：

a结点成为线程B中链表的头结点后，下一个结点e.next为b结点。既然下一个结点e.next不为null，那么当前结点e就变成了b结点，下一个结点e.next变为a结点。继续执行头插法，将b变为链表的头结点，同时next指针指向旧的头节点a，如下图：

此时，下一个结点e.next为a节点，不为null，继续头插法。指针后移，那么当前结点e就成为了a结点，下一个结点为null。将a结点作为线程B链表中的头结点，并将next指针指向原来的旧头结点b，如下图所示：

此时，已形成环链表。同时下一个结点e.next为null，流程结束。

 

HashMap 如何改造成线程安全？

方法一:通过Collections.synchronizedMap()返回一个新的Map,这个新的map就是线程安全的. 这个要求大家习惯基于接口编程,因为返回的并不是HashMap,而是一个Map的实现.

方法二:使用java.util.concurrent.ConcurrentHashMap. 这个方法比方法一有了很大的改进. ConcurrentHashMap的详细解析请看其他文章。

 

参考

java.util.HashMap 类 https://www.cnblogs.com/ysocean/p/8711071.html

HashMap的5大面试题，看这一篇就够了！https://zhuanlan.zhihu.com/p/95509849