HashMap 方法及特性

源码版本 1.8.0.25，HashMap 方法以及特性简单介绍思维导图。基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap

• 静态参数
  • int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    • 默认的初始容量 2^4 = 16 - 必须为2的幂。
  • int MAXIMUM_CAPACITY = 1 << 30;
    • 最大容量 2^30；如果构造方法指定了更大值，应该使用 2^30。容量必须是2的幂并且小于等于 2^30
  • float DEFAULT_LOAD_FACTOR = 0.75f;
    • 在构造函数中未指定时扩容系数的话，默认扩容系数
  • int TREEIFY_THRESHOLD = 8;
    • 添加键值对时，当map已有键值对数量超过此计数阈值，将链表转化为树。至少应该为8
  • int UNTREEIFY_THRESHOLD = 6;
    • 在调整大小操作期间，键值对数量少于此阈值时，将树转回链表。 应小于 TREEIFY_THRESHOLD，至少应该为6
  • int MIN_TREEIFY_CAPACITY = 64;
    • 数据转化为树时，整个 table的最小容量。至少为 4倍 TREEIFY_THRESHOLD
• 字段
  • transient Node<K,V>[] table;
    • 该表在首次使用时初始化，并根据需要调整大小。长度始终是2的幂
  • transient Set<Map.Entry<K,V>> entrySet;
    • 转化为set集合用于迭代
  • transient int size;
    • 当前 map包含的键值对数量
  • transient int modCount;
    • 修改次数，线程不安全类的 fast-fail 机制
  • int threshold;
    • 阈值，超过这个值就需要进行扩容（容量 * 扩容系数）
    • 默认值 DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12
  • final float loadFactor;
    • 哈希表的扩容系数
• 内部类
  • Node<K,V>
    • 最主要的内部类，所有节点的实现，包含：hash、key、value、next字段
  • TreeNode<K,V>
    • 继承Node类，用于红黑树的实现，内部有包含很多方法，例如：红黑树转化、树节点添加等
  • KeySet
    • keySet()使用，返回 key 的一个 set集合
  • Values
    • values() 方法使用，返回 values 的 Collection 集合
  • EntrySet
    • Set<Map.Entry<K,V>> entrySet() 使用，键值对遍历使用
• 主要方法
  • int hash(Object key)
    • 计算 key键的 hashcode值，key 为 null, hashcode 为 0
    • 在计算哈希表槽位时，高位码可能会被剔除，所以进行了右移16位和异或计算，在低位同时保留高位和低位特征
    • 使用异或计算，而不是与、或计算是因为，这两种计算结果会明显向0或1靠拢
    • 所有这些措施，目的就是减少 hash 碰撞
  • Node<K,V>[] resize()
    • 初始化或扩容哈希表；在构造方法后第一次进行添加是调用；在 HashMap 键值对超过阈值（扩容系数*容量）时调用
    • 在扩容时，会对原本桶内的链表和树进行拆分，分为高位和低位，重新插入
  • V put(K key, V value)
    • 添加键值对，覆盖原有 key的 value值
    • 链表尾部加入元素后，如果链表大于等于8个节点，转化为红黑树
    • 新插入键值对后判断是否当前含有键值对数量大于阈值，大于则进行扩容
  • V get(Object key)
    • 返回指定键所映射到的值；如果此映射不包含键的映射关系，则返回 null
    • 内部顺序大致分为：判断hashmap是否合理，hash所在桶是否空，第一个节点是否为目标节点，区分链表和红黑树查找
  • treeifyBin( tab, hash)
    • 将链表转化为红黑树，大致顺序为：判断哈希表长是否太小，转化为双向链表，再转为红黑树
  • removeNode
    • 删除节点，大致流程：判断hashmap是否初始化，桶内是否为空，第一个节点是否为目标，区分链表和红黑树
• 特性列举
  • 一个桶内节点数量达到8个进行红黑树转化；
  • 添加元素后，键值对数量大于阈值进行扩容；扩容拆分树时，拆分后小于等于 6个节点退化为链表
  • 哈希算法右移和异或操作、哈希表容量确定为2的幂，这些都是为了哈希表分布均匀，减少碰撞
  • 扩容时，对原先的链表和树进行拆分，按hash特点分为高位和低位，低位索引不变，高位索引加原长度