版权声明：本文为小斑马学习总结文章，技术来源于韦东山著作，转载请注明出处！
最近无意中发现有很多对Map尤其是HashMap的线程安全性的话题讨论，在我的理解中，对HashMap的理解中也就知道它是线程不安全的，以及HashMap的底层算法采用了链地址法来解决哈希冲突的知识，但是对其线程安全性的认知有限，故写这篇博客的目的就是让和我一样对这块内容不熟悉的小伙伴有一个对。
一、哈希表
这里先说一下哈希表的定义：哈希表是一种根据关键码去寻找值的数据映射结构，该结构通过把关键码映射的位置去寻找存放值的地方，说起来可能感觉有点复杂，我想我举个例子你就会明白了，最典型的的例子就是字典，大家估计小学的时候也用过不少新华字典吧，如果我想要获取“按”字详细信息，我肯定会去根据拼音an去查找 拼音索引（当然也可以是偏旁索引），我们首先去查an在字典的位置，查了一下得到“安”，结果如下。这过程就是键码映射，在公式里面，就是通过key去查找f(key)。其中，按就是关键字（key），f（）就是字典索引，也就是哈希函数，查到的页码4就是哈希值。
二、哈希冲突
但是问题又来了，我们要查的是“按”，而不是“安，但是他们的拼音都是一样的。也就是通过关键字按和关键字安可以映射到一样的字典页码4的位置，这就是哈希冲突（也叫哈希碰撞），在公式上表达就是key1≠key2，但f(key1)=f(key2)。冲突会给查找带来麻烦，你想想，你本来查找的是“按”，但是却找到“安”字，你又得向后翻一两页，在计算机里面也是一样道理的。
但哈希冲突是无可避免的，为什么这么说呢，因为你如果要完全避开这种情况，你只能每个字典去新开一个页，然后每个字在索引里面都有对应的页码，这就可以避免冲突。但是会导致空间增大（每个字都有一页）。
既然无法避免，就只能尽量减少冲突带来的损失，而一个好的哈希函数需要有以下特点：
-
1.尽量使关键字对应的记录均匀分配在哈希表里面（比如说某厂商卖30栋房子，均匀划分ABC3个区域，如果你划分A区域1个房子，B区域1个房子，C区域28个房子，有人来查找C区域的某个房子最坏的情况就是要找28次）。
-
2.关键字极小的变化可以引起哈希值极大的变化。
比较好的哈希函数是time33算法。PHP的数组就是把这个作为哈希函数。
核心的算法就是如下：
unsigned long hash(const char* key){
unsigned long hash=0;
for(int i=0;i<strlen(key);i++){
hash = hash*33+str[i];
}
return hash;
}
三、哈希冲突解决办法
如果遇到冲突，哈希表一般是怎么解决的呢？具体方法有很多，百度也会有一堆，最常用的就是开发定址法和链地址法。
1.开发定址法
如果遇到冲突的时候怎么办呢？就找hash表剩下空余的空间，找到空余的空间然后插入。就像你去商店买东西，发现东西卖光了，怎么办呢？找下一家有东西卖的商家买呗。
由于我没有深入试验过，所以贴上在书上的解释：
2.链地址法
上面所说的开发定址法的原理是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入，但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(空间/插入数据)>=1。
那有没有一种方法可以解决这种问题呢？链地址法可以，链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。我感觉业界上用的最多的就是链地址法。下面从百度上截取来一张图片，可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353...}，而我的哈希算法是H(key)=key mod 16，第一个数据1的哈希值f(1)=1，插入到1结点的后面，第二个数据12的哈希值f(12)=12，插入到12结点，第三个数据26的哈希值f(26)=10，插入到10结点后面，第4个数据337，计算得到哈希值是1，遇到冲突，但是依然只需要找到该1结点的最后链结点插入即可，同理353。
四、HashMap底层实现
HashMap允许使用null作为key或者value，并且HashMap不是线程安全的，除了这两点外，HashMap与Hashtable大致相同，下面是官方API对HashMap的描述：
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
如果有多个线程对Hash映射进行访问，那么至少有一个线程会对哈希映射进行结构的修改：结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。
那么很显然，当多个线程同时（严格来说不能称为同时，因为CPU每次只能允许一个线程获取资源，只不过时间上非常短，CPU运行速度很快，所以理解为同时）修改哈希映射，那么最终的哈希映射（就是哈希表）的最终结果是不能确定的，这只能看CPU心情了。如果要解决这个问题，官方的参考方案是保持外部同步，什么意思？看下面的代码就知道了：
Map m = Collections.synchronizedMap(new HashMap(...));
但是不建议这么使用，因为当多个并发的非同步操作修改哈希表的时候，最终结果不可预测，所以使用上面的方法创建HashMap的时候，当有多个线程并发访问哈希表的情况下，会抛出异常，所以并发修改会失败。比如下面这段代码：
for (int i = 0; i < 20; i++) {
collectionSynMap.put(i, String.valueOf(i));
}
Set<Entry<Integer,String>> keySets = collectionSynMap.entrySet();
Iterator<Entry<Integer, String>> keySetsIterator = keySets.iterator();
try {
while(keySetsIterator.hasNext()){
Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
System.out.println(entrys.getValue());
if(entrys.getValue().equals("1")){
System.out.println(entrys.getValue());
collectionSynMap.remove(1);
//keySetsIterator.remove();
}
}
} catch (Exception e) {
e.printStackTrace();
就会抛出ConcurrentModificationException异常，因为在使用迭代器遍历的时候修改映射结构，但是使用代码中注释的删除是不会抛出异常的。
通过上面的分析，我们初步了解HashMap的非线程安全的原理，下面从源码的角度分析一下，为什么HashMap不是线程安全的：
public V put(K key, V value) {
//这里省略了对重复键值的处理代码
modCount++;
addEntry(hash, key, value, i);
return null;
}
那么问题应该处在addEntry()上，下面来看看其源码：
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果达到Map的阈值，那么就扩大哈希表的容量
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//创建Entry键值对，此处省略这部分代码
假设有线程A和线程B都调用addEntry()方法，线程A和B会得到当前哈希表位置的头结点（就是上面链地址法的第一个元素），并修改该位置的头结点，如果是线程A先获取头结点，那么B的操作就会覆盖线程A的操作，所以会有问题。
下面再看看resize方法的源码：
void resize(int newCapacity) {
//此处省略如果达到阈值扩容为原来两倍的过程代码
Entry[] newTable = new Entry[newCapacity];
//把当前的哈希表转移到新的扩容后的哈希表中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
所以如果有多个线程执行put方法，并调用resize方法，那么就会出现多种情况，在转移的过程中丢失数据，或者扩容失败，都有可能，所以从源码的角度分析这也是线程不安全的。
HashMap测试代码
for (int i = 0; i < 40; i++) {
hashMap.put(i, String.valueOf(i));
}
Set<Entry<Integer,String>> keySets = hashMap.entrySet();
final Iterator<Entry<Integer, String>> keySetsIterator = keySets.iterator();
Thread t3 = new Thread(){
public void run(){
try {
while(keySetsIterator.hasNext()){
Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
System.out.println(entrys.getValue());
if(entrys.getValue().equals("1")){
System.out.println(entrys.getValue());
hashMap.remove(1);
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
};
Thread t4 = new Thread(){
public void run(){
try {
while(keySetsIterator.hasNext()){
Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
System.out.println(entrys.getValue());
if(entrys.getValue().equals("1")){
System.out.println(entrys.getValue());
hashMap.remove(1);
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
};
t3.start();
t4.start();
这段代码启动了两个线程并发修改HashMap的映射关系，所以会抛出两个ConcurrentModificationException异常，通过这段测试代码在此证明了HashMap的非线程安全。
Hashtable的底层实现
在介绍HashMap提到Hashtable是线程安全的，那么H啊时table是如何实现线程安全的呢？有了上面的介绍，我们直接从源码中分析其线程安全性：
public synchronized V put(K key, V value) {
// 保证value值不为空，此处省略其代码
// 保证key是不重复的，此处省略其代码
//查过阈值则扩容，此处省略
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
通过源码可以很明显看到其put方法使用synchronized关键字，在线程中这是实现线程安全的一种方式，所以Hashtable是线程安全的。
Hashtable的测试案例
下面使用一段测试代码验证Hashtable的线程安全：
Thread t3 = new Thread(){
public void run(){
for (int i = 0; i < 20; i++) {
hashTable.put(i, String.valueOf(i));
}
}
};
Thread t4 = new Thread(){
public void run(){
for (int i = 20; i < 40; i++) {
hashTable.put(i, String.valueOf(i));
}
}
};
t3.start();
t4.start();
//放完数据后，从map中取出数据，如果map是线程安全的，那么取出的entry应该和放进去的一一对应
for (int i = 0; i < 40; i++) {
System.out.println(i + "=" + hashTable.get(i));
最后得到的输出结果是这样的：
CocurrentHashMap详解
ConcurrentHashMap的测试案例
下面仍然通过一段测试程序验证ConcurrentHashMap的线程安全：
Thread t5 = new Thread(){
public void run(){
for (int i = 0; i < 20; i++) {
concurrentHashMap.put(i, String.valueOf(i));
}
}
};
Thread t6 = new Thread(){
public void run(){
for (int i = 20; i < 40; i++) {
concurrentHashMap.put(i, String.valueOf(i));
}
}
};
t5.start();
t6.start();
for (int i = 0; i < 40; i++) {
System.out.println(i + "=" + concurrentHashMap.get(i));
最后，控制台输出的结果如下：
说了那么多，针对Map子类的安全性可以总结如下几点：
- HashMap采用链地址法解决哈希冲突，多线程访问哈希表的位置并修改映射关系的时候，后执行的线程会覆盖先执行线程的修改，所以不是线程安全的
- Hashtable采用synchronized关键字解决了并发访问的安全性问题但是效率较低.。
- ConcurrentHashMap使用了线程锁分段技术，每次访问只允许一个线程修改哈希表的映射关系，所以是线程安全的
网友评论