Skip to main content

数据结构 - HashMap

HashMap 是一种数据加链表加红黑数的键值对数据结构。

初始化​

图中代码逻辑就是对高位上的第一个1以后的0进行补位操作。

更改输入框中的值试试：
int n =  - 1 // n = 536870912
n |= n >>> 1;
0010 0000 0000 0000 0000 0000 0000 0000
0001 0000 0000 0000 0000 0000 0000 0000 // 右移1位
0011 0000 0000 0000 0000 0000 0000 0000 // 逻辑与运算

n |= n >>> 2;
0011 0000 0000 0000 0000 0000 0000 0000
0000 1100 0000 0000 0000 0000 0000 0000 // 右移2位
0011 1100 0000 0000 0000 0000 0000 0000 // 逻辑与运算

n |= n >>> 4;
0011 1100 0000 0000 0000 0000 0000 0000
0000 0011 1100 0000 0000 0000 0000 0000 // 右移4位
0011 1111 1100 0000 0000 0000 0000 0000 // 逻辑与运算

n |= n >>> 8;
0011 1111 1100 0000 0000 0000 0000 0000
0000 0000 0011 1111 1100 0000 0000 0000 // 右移8位
0011 1111 1111 1111 1100 0000 0000 0000 // 逻辑与运算

n |= n >>> 16;
0011 1111 1111 1111 1100 0000 0000 0000
0000 0000 0000 0000 0011 1111 1111 1111 // 右移16位
0011 1111 1111 1111 1111 1111 1111 1111 // 逻辑与运算

// 最终结果：1073741824
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

put​

resize​

  1. HashMap的初始大小是16，扩展因子为0.75，在capacity（链表的容量）大于64且槽的链表长度大于等于8的时候，槽的存储结构会转为树化 如果小于6的时候会重新变为链表结构。

  2. HashMap的扩容机制：在每次put操作后HashMap都会根据++size 是否大于 threshold来进行扩容，每次会扩容的大小都是threshold的两倍 在申请完新的tab后会从新计算每一个node索引。

  3. threshold每次扩容都会取大于当前值的2的32次方