HashMap原理

请设置文章作者

发布于：Jun 27, 2019

次浏览

基本

hashmap有数组+链表组成

基于红黑树的hashmap就是当链表达到一定长度时把链表变成红黑树

向map中put元素，如果key重复，会覆盖并把老的元素返回出来

1
2
3
4
5
6
7
8
9
10

| array | 1 | 2 | ... | N |
|-------|---|---|-----|---|
  |       |   |   |     |   
  |       |   |   |     |   
 链表   value
  |       |   |   |     |   
  |       |   |   |     |   
        value
  |       |   |   |     |   
  |       |   |   |     |

• hashmap初始化数组容量的时候必须的一个二的幂次方数
  • 这样方便控制取值范围

    1 2 3 4 5 6 7 8 9

    2^k-1会得到一个全是1的二进制数：0001 1111 用这个数与hash code与运算即可以截断hash code，只保留低位k-1位 0000 0111 0101 1010 --------- 0000 0010 高位数先右移在与这个111与运算就可得到想要的任意位 提高散列性，防止链表过长，提高get的效率

取小于一个数的最大二次幂算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

func (int i){
    i |= (i >> 1)
    i |= (i >> 2)
    i |= (i >> 4)
    i |= (i >> 8)
    i |= (i >> 16)
    return i-(i >>> 1)
}

return前的一系列移位操作把有效位全部变成了1
在用结果减去移1位后的结果(i>>>1)，就得到只有最高位为1

        0001 ****
>>1      0000 1***
        ---------
        0001 1***
>>2     0000 0110
...直到int的64位都保
        0001 1111
        0000 1111
    res

扩容时：新建数组 -> 迁移到新数组

多线程的情况

在多线程情况下，扩容时可能会同时创建多个个数组。在JDK1.7中会出现问题

put(key, value)方法

• 确定下标
  • hashcode & (lenght-1)
  • 因为hashmap的长度只会是2的次幂，所以减1后每一个有效位(除了最高有效位)都是1
• 解决哈希冲突
  • 计算hashcode的时候，有可能会得到同样的值，这时候发生哈希冲突
  • 链表法
    • 插入在链表头部(1.7)
  • 再散列法

get(key)方法

• 计算下标
• 找到key对应的值
  • 如果是链表法解决的哈希冲突则
    • 遍历寻找key

ConcurrentHashMap

ConcurrentHashMap解决多线程情况下出现的问题

ConcurrentHashMap使用一个并发级别来指定多少个元素共享一个锁，ConcurrentHashMap称这个所为segment。

• 初始化
  • 根据并发级别来确定segment的容量，一个segment对象就相当于一个小的hashmap