JDK1.7 HashMap

通俗易懂的解释 ↓
漫画：什么是HashMap？
漫画：高并发下的HashMap
详细的解释 ↓
HashMap深度分析
源码解释 ↓
【Java集合源码剖析】HashMap源码剖析

• HashMap是基于链表和数组实现的用于存储key-value键值对的集合。
  内部实现了一个Entry类用来存放键值对。这些键值对分散存储在entry数组中。

• 通过key拿到hashcode，避免hashcode分布不均，所以要对它进行二次hash保证高低位都有算进去，之后用这个值模数组长度就能得到这个键值对在数组中的位置index。

• 模运算性能低所以用位运算代替模，即index=hashcode(key)&(length-1)。
  为了方便进行位运算所以要求entry数组长度即hashmap容量必须是2的n次幂，默认是16。

• hash冲突时使用链地址法。entry数组中每个元素都是一个链表的头结点，使用头插法将元素插入链表头。

• 负载因子，表示hashmap的空间使用程度。默认0.75
  负载因子越大，hashmap能容纳更多的元素，但是相对的链表可能就越长，降低了索引效率。
  负载因子越小，空间就浪费得越多，但是索引效率高。

• 键值对数量 超过 容量*负载因子 的时候进行resize扩容。
  size>=initialCapacity * loadFactor

• 扩容，新建一个数组，长度是原来的两倍，将原数组所有元素rehash到新数组中。

• 非线程安全。
  put时可能元素丢失。
  并发场景下同时扩容，链表可能会发生死循环（rehash时直接头插）

  
  

• modCount 记录被修改或删除的总次数，被声明为volatile，保证了线程之间的可见性。它是在迭代时使用的，开始迭代时记录下该值，迭代过程中拿现有值与它比较，若不相同说明有其他线程增加或删除了元素，抛出异常。fail-fast机制

• key为null时，将它放在entry数组的第一个链表中。

    // 获取“key为null”的元素的值    
    // HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！    
    private V getForNullKey() {    
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
            if (e.key == null)    
                return e.value;    
        }    
        return null;    
    }