八股碎碎念01——HashMap原理
Java面试题周总结
HashMap
HashMap实现原理
Java 1.7版本
在Java1.7中HashMap通过数组+链表的方式实现，由于链表查询速度为O(n)，因此在插入大量元素后查询速度会明显降低。
Java 1.8版本
在Java1.8中对HashMap进行改进，采用数组+链表/红黑树实现数据存储。在使用HashMap过程中当数组长度达到64且链表长度为8时会自动转换为红黑树，而当链表长度小于6时又会退化为链表。
红黑树是一种自平衡二叉搜索树，通过使用双倍于链表节点的空间换取O(logn)的数据查询速度，典型的以空间换时间。
HashMap底层实现
Java1.7拉链法
拉链法就是数组+链表组合，遇到Hash冲突时先判断HashCode相同则覆盖，不相同就插入。链表里存放的是一个键值对，我们Hash冲突时，用Hash值找到桶的位置，再遍历链表，通过key找到我们对应的键值对
Java1.8红黑树
当HashMap空间不够用时优先扩容数组，当数组长度为64且链表长度为8时则链表转换为红黑树。
常见解决Hash冲突的方法
拉链法
在Java1.7中使用数组+链表的数据存储方式，当出现Hash碰撞时通过在链表中逐一比对存储对象的hash值，相同的覆盖，不同的向后插入
重Hash法
当发生Hash碰撞之后，将发生碰撞的对象再次进行Hash值计算，得出结果后再存入。
开放寻址
在哈希表中找到另一个可用的位置来存储冲突的键值对。
扩容
扩容哈希桶，降低碰撞风险。
HashMap是否是线程安全
- 答案：非线程安全
- 扩容策略的线程不安全
- 多线程下put方法使用不当导致前一个key被后一个key覆盖
Java1.7头插法
Java1.7的HashMap使用数组+链表的方式，而在向链表插入数据时使用头插法，因此在多线程插入数据时由于缺乏同步机制，导致链表的next可能会指向自己形成循环链表。
Java1.8尾插法
Java1.8中对链表插入方法进行改进，从原先的头插法变为尾插法。防止生成循环链表。但是在多线程put下依然会存在数据不一致的问题。
解决方案(Java1.8)
- 使用synchronized关键字+CAS
- 使用ConcurrentHashMap
ConcurrentHashMap底层原理
Java1.7
在Java1.7中ConcurrentHashMap通过Segment分段锁实现。Segment数组不可扩容，默认长度为16，刚好是ConcurrentHashMap初始化后的长度，因此ConcurrentHashMap支持16个线程并发操作。
Segment默认分段为16，每个部分都相当于一个哈希表。Segment自带锁，因此可以实现并发。
Java1.8
在Java1.8中通过synchronized和CAS实现并发，加锁粒度为链表（红黑树）节点。由于加锁粒度更细，因此在并发操作时效率更高。
在ConcurrentHashMap中已经使用了synchronized为什么还要使用CAS
CAS是轻量级自旋锁，在线程竞争锁不频繁的时候可以通过CAS保证数据一致性。但当线程竞争较为激烈时，则需要使用synchronized。在HashMap中，通过Hash碰撞的情况来确定使用synchronized还是CAS。当Hash碰撞不经常发生时则说明HashMap中存储的元素不算多或没有太多线程竞争，此时使用CAS可以保证数据一致性，同时也能降低性能开销。而Hash碰撞已经较为严重时则说明HashMap容量将满或多线程竞争较为激烈，因此需要使用synchronized。
在Java1.8中如何实现线程安全
- 答： Java1.8是通过CAS和synchronized实现线程安全
添加元素时判断是否为空
如果为空则使用 volatile 加 CAS 来初始化，如果容器不为空，则根据存储的元素计算位置是否为空。
存储位置
如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；如果根据存储的元素计算结果不为空，则使用 synchronized，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。
使用乐观锁还是悲观锁
CAS是乐观锁，synchronized是悲观锁
- 乐观锁：乐观锁总是假设最好的情况，认为共享资源每次被访问的时候不会出现问题，线程可以不停地执行，无需加锁也无需等待，只是在提交修改的时候去验证对应的资源（也就是数据）是否被其它线程修改了（具体方法可以使用版本号机制或 CAS 算法）。
- 悲观锁：悲观锁总是假设最坏的情况，认为共享资源每次被访问的时候就会出现问题(比如共享数据被修改)，所以每次在获取资源操作的时候都会上锁，这样其他线程想拿到这个资源就会阻塞直到锁被上一个持有者释放。