HashMap 源码分析-基础结构

HashMap 源码比较多，相关的面试题也比较多，但是这些基本也都是考察源码的相关问题。

底层结构

底层数据结构主要是：数组 + 链表 + 红黑树。

特点：当链表的长度大于等于 8 时，链表会转化成红黑树；当红黑树大小小于等于 6 时，红黑树会转化成链表

从 HashMap 的类注释中可获得的信息：

1. 允许 null 值存在

2. 线程不安全

3. load factor 表示扩容因子，默认值为 0.75

4. 不扩容的条件：数组容量 > 需要的数组大小 /load factor；反之，不满足这个条件就会进行扩容

5. 如果需要插入的数据量比较大的话，建议在 new HashMao 时就先设置成足够的大小，为了避免在插入过程中不断的进行扩容，耗费不必要的性能

6. Collections 中的 synchronizedMap 也可以实现线程安全，其主要实现方法是在每个方法上都加上了 synchronized 锁

7. 迭代过程中，如果 HashMap 的结构被修改，会快速失败。(类似 ArrayList，用 modCount 记录修改次数)

源码：

public class HashMap<K,V> extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    static final int MAXIMUM_CAPACITY = 1 << 30;
       static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;

    static final int MIN_TREEIFY_CAPACITY = 64;        .........    
    transient Node<K,V>[] table;
      transient Set<Map.Entry<K,V>> entrySet;
      transient int size;
       transient int modCount;        int threshold;            .......        static class Node<K,V> implements Map.Entry<K,V> {    ..........    }
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {    ..........    }        ..........

1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 初始容量为 16（2 的 4 次方）

2. static final int MAXIMUM_CAPACITY = 1 << 30; HashMap 最大容量为 2 的 30 次方

3. static final float DEFAULT_LOAD_FACTOR = 0.75f; 扩容（负载）因子默认值为 0.75

4. static final int TREEIFY_THRESHOLD = 8; 当链表长度大于等于 8 时，链表会转换成红黑树

5. static final int UNTREEIFY_THRESHOLD = 6; 当大小小于等于 6 时，红黑树转换为链表

6. static final int MIN_TREEIFY_CAPACITY = 64; 约定当数组容量大于 64 时，链表达到转换成红黑树的条件

7. transient int modCount; 记录迭代过程中 HashMap 是否发生修改

8. transient int size; 记录 HashMap 的实际大小

9. transient Node<K,V>[] table; 存放数据的数组

10. int threshold; 扩容的条件

11. static class Node<K,V> implements Map.Entry<K,V> 链表的节点

12. static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 红黑树的节点