HashMap的实现

• ConcurrentHashMap从JDK1.5开始随着java.util.concurrent包一起引入JDK，主要为了解决HashMap线程不安全，和HashTable效率不高的问题
• HashMap在多线程编程中是线程不安全的，而HashTable使用Synchronized修饰方法而效率低
• ConcurrentHashMap是一个在多线程环境下，线程安全且高性能的HashMap解决方案
• 底层实现：数组+链表+红黑树（since JDK1.8）

@Testpublic void test() {ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();map.put(1, "a");map.put(2, "b");map.put(3, "c");Set<Map.Entry<Integer, String>> entrySet = map.entrySet();for (Map.Entry<Integer, String> entry : entrySet) {Integer key = entry.getKey();String value = entry.getValue();System.out.println(key + " " + value);}System.out.println(map.get(1));}

1. 数组

• 使用一段连续存储单元存储数据，对于指定下标的查找，时间复杂度为O(1)，对于一般的插入删除操作，涉及数组元素的移动，其平均时间复杂度为O(n)
• 通过Object.hashCode()方法得到固定长度哈希值，然后对数组长度取余，得到Object在数组中的坐标
• 默认初始化长度:16，数组长度一定是2的倍数

2.线性链表

• 对于链表的新增、删除操作，在查找到操作位置后，只需要处理结点间的引用即可，时间复杂度为O(1)
• 查找操作需要遍历链表的所有结点，复杂度为O(n)
• 解决哈希冲突，避免数据被覆盖

3.红黑树

3.1概述

• 当哈希冲突严重时，链表冗长导致效率低下
• 红黑树是一种接近平衡的二叉搜索树，在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
• 通过对任何一条从根到叶子的路径上，由于各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此接近平衡。
• 支持查找、插入、删除等操作，平均时间复杂度为O(logn)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NnWwAoYR-1589878270141)(Untitled.png)]

3.2性质

• 每个结点要么是红的，要么是黑的
• 根结点是黑的
• 叶结点都是黑的
• 如果一个结点是红的，那么两个儿子都是黑的
• 对于任意结点而言，到叶结点的每条路径都包含相同数目的黑结点
  

4.HashMap扩容死锁

• 扩容因子：0.75
• 链表转红黑树时，链表长度为8

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;public class DevThread implements Runnable {private static Map<Integer, Integer> map = new HashMap<>();private static AtomicInteger atomicInteger = new AtomicInteger();@Overridepublic void run() {while (atomicInteger.get() < 1000 * 1000) {map.put(atomicInteger.get(), atomicInteger.get());atomicInteger.incrementAndGet();}}
}public class MapDeadLock {public static void main(String[] args) {for (int i = 0; i <10 ; i++) {new Thread(new DevThread()).start();}}
}

5. BATJ一线大厂技术栈

• 分布式架构
• 微服务架构
• 源码分析
• 并发编程
• 性能优化
• 数据结构与算法
• 高并发实战
• 工程化协作