HashMap底层执行原理——数据结构

落日映苍穹つ 2022-03-17 05:17 312阅读 0赞

# 一：HashMap底层执行原理 #

# #

## 1.HashMap的存储结构 ##

数组、链表、红黑树(jdk1.8)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTcyNjk3_size_16_color_FFFFFF_t_70][]

##    2. 特点 ##

1.快速存储

2.快速查找(时间复杂度O(1))

3.可伸缩

## 3.**hash算法**     ##

所有的对象都有hashCode(使用key的)

hash值的计算

(hashCode) ^ (hashCode >>> 16)

##    4.**数组下标计算** ##

数组默认大小:16  
数组下标：hash&(16-1)   =  hash% 16

## 5.**Hash****冲突** ##

不同的对象算出来数组下标是相同时

**单向链表：**用于解决Hash冲突的方案,加入一个next记录下一个节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTcyNjk3_size_16_color_FFFFFF_t_70 1][]

## 6.**扩容** ##

数组变长2倍  0.75

## 7.**触发条件** ##

数组存储比例达到75%  --- 0.75

## 8.**红黑树** ##

一种二叉树，高效的检索效率

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTcyNjk3_size_16_color_FFFFFF_t_70 2][]

## 9.**触发条件** ##

在链表长度大于8的时候，将后面的数据存在红黑树中

# \#\# 二. HashTable 和 currentHashMap 是如何确保线程安全的 #

**HashTable** : 都在方法前面加了synchronized 关键字， 把整个数据都放到一个大桶里面， 只允许一个线程访问， 其他线程处于阻塞状态。效率低， 所以有了currentHashMap

**currentHashMap**  ：   
JDK 1.7--> 分段锁思想， 将一个大桶分成若干个小桶（假设有1000个数据， 分成16 个桶）， 不同线程可以拿不同桶里面的数据  
JDK 1.8-->相比较与1.7 ， 1.8 锁的粒度更小了， 如果有1000 个数据， 就有1000 个锁（桶））， 每个桶都有自己独立的说， 可并发的线程数变多

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTcyNjk3_size_16_color_FFFFFF_t_70]: /images/20220317/d5f2430749ba4da691730bbfa0fad2b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTcyNjk3_size_16_color_FFFFFF_t_70 1]: /images/20220317/4ec8fdd66322466fa6f9965fec84ca96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTcyNjk3_size_16_color_FFFFFF_t_70 2]: /images/20220317/0612929e40de415eb993b4e0964a0339.png