HashMap原理

1、必备运算知识

1、逻辑运算符

  • 逻辑与 & 同真为真
  • 短路与 && 同真为真 效率高
  • 逻辑或 | 有真则真
  • 短路或 || 有真则真 效率高
  • 非 ！
  • 异或 a^b 不同则真

2、原码、反码、补码

  1. 二进制最高位为符号位 0正1负
  2. 正数 三码合一
  3. 负数的反码 符号位不变，其他位取反
  4. 负数的补码 = 反码 + 1
  5. 0 的反码补码都为0
  6. 计算机补码运算，原码显示

3、位运算符

  • & 按位与
  • | 按位或
  • ^ 按位异或
  • ~ 按位取反
  • >> 算术右移 右移n位：本质是除以2
  • << 算术左移 左移n位：本质是乘以2
  • >>> 逻辑右移 低位溢出，高位补0

2、内部数据结构

HashMap原理 - 图1

链表平均查找长度n/2 红黑树查找长度log（n）

3、数据存储原理

HashMap原理 - 图2

  1. 判断数组是否为空，为空进行初始化;
  2. 不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
  3. 查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
  4. 存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
  5. 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)
  6. 如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8并且数组长度大于64， 大于的话链表转换为红黑树；
  7. 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍

3.1初始容量大小

HashMap原理 - 图3

这个方法保证了HashMap总是使用2的幂作为哈希表的大小

（另：hash值的范围很大，内存放不下。于是对长度取模运算%，但如果除数是2 的幂，那么取模和除数减一的位与运算相同，但是位与运算效率高）

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

3.2HashMap的哈希函数

hash函数是先拿到 key 的hashcode，是一个32位的int值，然后让hashcode的高16位和低16位进行异或操作

  1. static final int hash (object key){
  2.     int h;
  3.     return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16)
  4. }

扰动函数，减少hash碰撞

3.3底层原理

HashMap通过key的HashCode 经过扰动函数处理得出hash值，然后通过（n-1) & hash 判断存放位置。（n指的是数组长度）

其余的看链接

https://blog.csdn.net/zhengwangzw/article/details/104889549