HashMap、Hashtable、ConcurrentHashMap的原理与区别

Leefs 2020-03-04 PM 1857℃ 0条

# HashMap、Hashtable、ConcurrentHashMap的原理与区别

### 前言

本篇简单讲述HashMap、Hashtable、ConcurrentHashMap的原理，并对它们之间的区别做一个简单对比，并不从源码层面上做讲解

### 一、基础概念

#### HahTable

+ 1.继承于Dictionary，现了Map、Cloneable、java.io.Serializable接口

+ 2.底层是**数组+链表**实现，和HashMap一样，Hashtable 也是一个**散列表**，它存储的内容是**键值对(key-value)映射**。
+ 3.key和value都不能为null
+ 4.通过`synchronized`进行加锁，实现线程安全

#### **HashMap**

+ 1.底层是**数组+链表**实现
+ 2.key和value可以为null
+ 3.线程不安全
+ 4.初始size为**16**，扩容：newsize = oldsize*2，size一定为2的n次幂
+ 5.扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
+ 6.插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
+ 7.当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀

#### ConcurrentHashMap

+ 1.继承于AbstractMap

+ 2.底层采用分段的数组+链表实现
+ 3.不能存储null键和值
+ 4.线程**安全**
+ 5.通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
+ 6.Segment继承了`ReentrantLock`，实现线程安全，每次加锁的操作， 实际是锁住了每一个`Segment`，这样保证了整体的线程安全。
+ 7.扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

### 二、**HahTable和ConcurrentHashMap实现线程安全的区别**

+ 1.HahTable通过`synchronized`进行加锁，ConcurrentHashMap通过Segment继承了`ReentrantLock`进行加锁
+ 2.Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
+ 3.ConcurrentHashMap有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁

ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表，从而在同一时刻只能由一个线程对其进行操作；而ConcurrentHashMap中则是一次锁住一个桶。

ConcurrentHashMap默认将hash表分为16个桶，诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。

### 三、ConcurrentHashMap和HashMap区别

+ 1.ConcurrentHashMap比HashMap多出了一个类Segment，而Segment是一个可重入锁
+ 2.ConcurrentHashMap是使用了锁分段技术来保证线程安全的

**锁分段技术**：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问

### 四、负载极限

“负载极限”是一个0～1的数值，“负载极限”决定了hash表的最大填满程度。当hash表中的负载因子达到指定的“负载极限”时，hash表会自动成倍地增加容量（桶的数量），并将原有的对象重新分配，放入新的桶内，这称为rehashing。

HashMap和Hashtable的构造器允许指定一个负载极限，HashMap和Hashtable默认的“负载极限”为0.75，这表明当该hash表的3/4已经被填满时，hash表会发生rehashing。

**“负载极限”的默认值（0.75）是时间和空间成本上的一种折中：**

+ 1.较高的“负载极限”可以降低hash表所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap的get()与put()方法都要用到查询）
+ 2.较低的“负载极限”会提高查询数据的性能，但会增加hash表所占用的内存开销

*附：参考文章链接https://www.cnblogs.com/heyonggang/p/9112731.html*

标签: Java, JavaSE

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/684.html

上一篇 GET和POST两种基本请求方法的区别

下一篇【转载】并发问题是怎样造成的

HashMap、Hashtable、ConcurrentHashMap的原理与区别

评论已关闭

栏目分类

标签云

友情链接申请

HashMap、Hashtable、ConcurrentHashMap的原理与区别

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请