文章目录

一、HashMap
二、HashMap为什么线程不安全
三、如何让HashMap线程安全
四、ConcurrentHashMap
五、CAS是什么
六、ConcurrentHashMap1.7和1.8的区别
七、HashMap和HashTable区别
总结

一、HashMap

key-value：HashMap是key-value形式存储的数据结构，key、value都可以为null，但是key只可以有一个null，因为Map的key是不允许重复的。
默认容量：如果在new HashMap的时候没有设置默认值，那么默认容量就是16，如果设置了默认值，那么默认容量就是传入值的向上最接近2的幂等的值。
例如：HashMap map = new HashMap(3); 默认容量就是4；
hash冲突：hashMap是通过链地址法解决hash冲突，多次hash降低hash冲突。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//扰动函数：让高低位都去参与运算
//目的减少hash冲突
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

线程安全：hashMap在并发的时候会有数据丢失，因为多线程去运行，put的时候值会被覆盖，扩容的时候也是不安全的，并发的时候链表会形成死循环。所以hashMap是线程不安全的。
数据结构：hashMap底层数据结构是数组+链表或者数组+红黑树。链表长度大于等于8并且数组长度大于等于64时，链表会转换为红黑树，链表长度小于6时，红黑树会转换为链表。链表长度限制为小于6，也是为了避免链表和红黑树之间频繁转换。
自动扩容：hashMap的扩容因子是0.75，当HashMap中的元素个数超过数组大小的0.75倍时，就会调用resize()方法进行数组扩容，每次扩容的容量都是之前容量的2倍。
首次put时会触发扩容(算是初始化)，然后存入数据，然后判断是否需要扩容。
不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容。

二、HashMap为什么线程不安全

数据丢失：
①并发赋值被覆盖：在createEntry()方法中，新添加的元素直接放在头部，使元素之后可以更快访问，但是如果两个线程同时执行到此处，会导致其中一个线程的赋值被覆盖。
②已遍历区间新增元素丢失：当某个线程在transfer()方法迁移时，其他线程新增的元素可能落在已遍历过的哈希槽上，遍历完成后，table数组引用指向了newTable，新增元素丢失。
③新表被覆盖：如果resize完成，执行了table=newTable，则后续元素就可以在新表上进行插入，但如果多线程同时resize，每个线程都会new一个数组，这是线程内的局部对象，线程之间不可见，迁移完成后resize的线程会赋值给table线程共享变量，可能会覆盖其他线程的操作，在新表中插入的对象都会被丢弃。
死循环：
扩容时resize调用transfer使用头插法迁移元素，虽然newTable是局部变量，但原先table中的Entry链表是共享的，问题是Entry的next指针并发修改，某线程还没有将table设为newTable时用完了CPU时间片，导致数据丢失或死循环。

三、如何让HashMap线程安全

Collections中提供了一个方法synchronizedMap()

Map map = Collections.synchronizedMap(hashMap);

四、ConcurrentHashMap

为了避免HashMap的线程安全问题引出了ConcurrentHashMap。
ConcurrentHashMap是由数组、单向链表、红黑树组成的，默认长度是16。key-value都不支持null。
当数组长度大于64并且链表长度大于等于8时，单向链表会转为红黑树，链表长度小于6，红黑树会退化成单向链表。
hach冲突：ConcurrentHashMap是通过链地址法来解决hash冲突的。
并发安全的主要实现是通过对指定的Node节点加锁，来保证数据更新的安全性。
ConcurrentHashMap在性能优化方面主要体现在两点

当线程竞争不激烈时，直接采用CAS来实现元素个数的原子递增。
如果线程竞争激烈，使用一个数组来维护元素个数，如果要增加总的元素个数，则直接从数组中随机选择一个，再通过CAS实现原子递增，它的核心思想是引入了数组来实现对并发更新的负载。

五、CAS是什么

CAS全称为Compare and swap 比较替换。
假设有三个操作数，内存值V，旧的预期值A，要修改的值B，当且仅当预期值A和内存值V相同时，才会将内存值A修改为B并返回true，否则什么都不做。当然cas要与volatile变量配合使用，这样才能保证每次拿到的变量是主内存中最新的那个值，否则旧的预期值A对某条线程来说，用于是一个不会变的值A，只要某次CAS操作失败，永远都不可能成功。

六、ConcurrentHashMap1.7和1.8的区别

1.7采用数组+单链表，扩容采用头插法，并发情况下链表闭环，采用分段锁，采用的锁是Reentrantlock。
1.8采用数组+红黑树，扩容采用尾插法，采用Node节点，采用的锁是Synchronized+node。

七、HashMap和HashTable区别

HashMap和HashTable都实现了Map接口。
都可以存储key-value数据。
HashMap可以把null作为key或者value，HashTable不可以。
HashMap线程不安全，但是效率高，HashTable线程安全，但是效率相对低。
HashMap的迭代器(Iterator)是fail-fast(快速失败)迭代器，而HashTable的enumerator迭代器不是fail-fast的。

fail-fast：是多线程并发操作集合时的一种失败处理机制，就是最快的实际能把错误抛出而不是让程序执行。

总结

人人都有一个进大厂的梦，希望以上的内容能够对你我这样的人有所帮助。

玖叶教程网

前端编程开发入门

每日一练进击大厂「DAY3」HashMap