HashMap和HashTable及ConcurrentHashMap区别详解

素颜马尾好姑娘i 2022-05-19 08:00 208阅读 0赞

Java中的数据存储方式有两种结构，一种是数组，另一种就是链表，前者的特点是连续空间，寻址迅速，但是在增删元素的时候会有较大幅度的移动，所以数组的特点是查询速度快，增删较慢。

而链表由于空间不连续，寻址困难，增删元素只需修改指针，所以链表的特点是查询速度慢、增删快。

那么有没有一种数据结构来综合一下数组和链表以便发挥他们各自的优势？答案就是哈希表。哈希表的存储结构如下图所示：

①hashMap实现了Map接口，实现了将唯一隐射到特定值上。允许一个null键和多个null值。非线程安全。

②hashTable：类似于HashMap，但不允许null键和null值，比HashMap慢，因为它是同步的。它是线程安全的类，它使用sysnchronized来锁住整张hash表来实现线程安全，每次锁住整张表让线程独占。

③ConcurrentHashMap：允许多个修改操作并发进行，关键在于使用了锁分离技术。使用多个锁控制对哈手表的不同部分进行的修改。它内部使用段（Segment）来表示这些不同的部分，每个段其实就是一个小的Hashtable，它们有自己的锁。多个修改操作发生在不同的时段上，它们就可以并发进行。

![Center][]

从上图中，我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点，通过功能类似于hash(key.hashCode())%len的操作，获得要添加的元素所要存放的的数组位置。

HashMap的哈希算法实际操作是通过位运算，比取模运算效率更高，同样能达到使其分布均匀的目的，后面会介绍。

键值对所存放的数据结构其实是HashMap中定义的一个Entity内部类，数组来实现的，属性有key、value和指向下一个Entity的next。

HashMap：

实现了Map接口，实现了将唯一键隐射到特定值上。允许一个NULL键和多个NULL值。非线程安全。

HashTable：

类似于HashMap，但是不允许NULL键和NULL值，比HashMap慢，因为它是同步的。HashTable是一个线程安全的类，它使用synchronized来锁住整张Hash表来实现线程安全，即每次锁住整张表让线程独占。

HashTable和HashMap采用相同的存储机制，二者的实现基本一致，不同的是：

（1）HashMap是非线程安全的，HashTable是线程安全的，内部的方法基本都经过synchronized修饰。

（2）因为同步、哈希性能等原因，性能肯定是HashMap更佳，因此HashTable已被淘汰。

（3） HashMap允许有null值的存在，而在HashTable中put进的键值只要有一个null，直接抛出NullPointerException。

（4）HashMap默认初始化数组的大小为16，HashTable为11。前者扩容时乘2，使用位运算取得哈希，效率高于取模。而后者为乘2加1，都是素数和奇数，这样取模哈希结果更均匀。

## ConcurrentHashMap ##

ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的Hashtable，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。

[Center]: /images/20220519/9749d36916a245ebb43801f06ca64a4c.png