HashMap

HashMap结构

重要属性

• DEFAULT_INITIAL_CAPACITY：默认初始容量 16
• MAXIMUM_CAPACITY：最大容量
• DEFAULT_LOAD_FACTOR：扩容负载因子0.75
• TREEIFY_THRESHOLD：树化阈值 8
• MIN_TREEIFY_CAPACITY：树化阈值，链表长度 64
• UNTREEIFY_THRESHOLD：树退化阈值 ，6

Map$Node结构

static class Node<K,V> implements Map.Entry<K,V> {      final int hash;      final K key;      V value;      Node<K,V> next;}

HashMap中的路由寻址算法

• 首先初始化容量信息，如果传进来cap，则计算大于当前cap的最近的一位2的倍数,后续高效率获取桶下表位置

static final int tableSizeFor(int cap) {      int n = cap - 1;      n |= n >>> 1;      n |= n >>> 2;      n |= n >>> 4;      n |= n >>> 8;      n |= n >>> 16;      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  }

传递进来：10，最终走完运算之后得到15，转换为2进制为：1111 ，此时加1必然得到一个2的倍数即16 > 10000，所以16是距离10最近的一个2的倍数，2^4 = 16

综上：HashMap的容量始终都是2的幂次方 1，2，4，8，16，32，64，128 等等之类的数字
所以 HashMap采用的寻址算法为：key.hashCode() & (cap - 1) 其含义等价于 key.hash() mod cap

HashMap中的扰动函数

原因：让Key值的高位也参与路由运算 。当数组的长度很短时，只有低位数的hashcode值能参与运算。而让高16位参与运算可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。并且使得高16位和低16位的信息都被保留了。
Tips: int 默认占用4字节，32比特位，所以右移16位就得到低位，异或运算(^) : 相同为0，不同为1

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

HashMap 添加数据的流程

• 第一次添加数据，初始化容量，惰性初始化
  • 通过寻址算法key.hashCode() & (cap - 1)找到对应的桶下标
    • 对应下标为Null 直接 new Node 添加到容器当中
    • 对应下标不为空，是否是重复添加，是则覆盖更新
    • 是否是树节点，如果是进行树的插入逻辑
    • 是否为链表，是否有相同数据，如果没有则在尾端插入

存放机制：

• 为空：直接存放
• 为链：追加链尾
• 为树：执行红黑树逻辑

HashMap扩容机制

• 当容器超过阈值，即超过容器的0.75倍，进行扩容2倍
• copy数据到新容器
  • 单节点：直接存放
  • 树节点：拆分树，重新映射
  • 链条节点：拆分链条
  • 算法：hash & cap
    • != 0 高链：当前索引下标 + 旧容量位置
    • == 0 低链：存放当前索引位置

拆分高低链

问题：
1、HashMap是如何取数据的？请简述其流程

• 首先经过寻址算法找到具体哈希槽
• 判断节点类型
  • 空：直接返回null
  • 链：遍历比较
  • 树：执行红黑树的查找逻辑
  • 单值：直接返回

2、loadFactor负载因子的意义是什么？

• 作用：当容器内数量大于总容量的3/4开启扩容机制
• 意义：
  • 在空间和时间之间取得较好的权衡
  • 当此值选择较大时，节省了空间，链表变得较长，hash冲突的几率就会变高，同时影响性能
  • 小于这个值则会，减少了hash冲突，频繁的扩容，占用空间更多

3、为什么HashMap表格容量大小是2的幂次方？

• 寻址更快，利用二进制运算获取哈希槽的效率更高

4、你还知道哪些方法key减少Hash冲突

• 扩大初始化的容量
• 开放地址法(再散列法)
• 再哈希法Rehash
• 链地址法（拉链法）

5、 HashMap 1.7 和 1.8 有什么不同？

• 1.7：数组 + 链表
• 1.8： 数组 + （链表 ｜ 红黑树）
• 插入元素：七上八下即 1.7 头插法(多线程修改会有死链问题) 、1.8尾插法

6、 为何要用红黑树，为何不一上来就树化，树化的阈值为何时8 ，何时会退化为链表？

• 为何要用红黑树？

  • 当发生树化操作的时候，这个时候数据非正常状态的，正常场景下不会一下子产生特别多的Hash冲突，只有时非常规的场景下才会触发红黑树

  • 解决了超长链表的查询效率低下的问题，但是小数据量的链表不比红黑树的查询效率要低

  • hash 值如果足够随机，则在hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过8的链表出现概率是

    0.00000006，选择8 就是为了让树化几率足够小

• 树化的两个条件
  • 容量>= 64
  • 超过树化阈值8
• 退化链表的条件
  • 扩容时，树的节点<= 6
  • remove节点时,若root、root.left、root.right、root.left.left 有一个为null，也会退化为链表