0. Java 容器
1. HashTable、HashMap、ConcurrentHashMap 线程安全对比
HashMap:异步的,线程不安全;
HashTable:同步的,synchronized针对的是整个hash表,是独占锁,同一时刻只能有一个线程访问操作,线程安全;
ConcurrentHashMap:异步的,使用分段锁机制,当某线程访问操作某段数据,其它段数据依然可以让其它线程访问操作,线程安全;
2. 分析
HashTable
-
- HashTable底层是通过数组+链表实现的,KV都不能为NULL,线程安全的;
- 初始size为11,扩容:newsize = oldsize * 2 + 1;
- 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length;
/** * Constructs a new, empty hashtable with a default initial capacity (11) * and load factor (0.75). */ public Hashtable() { this(11, 0.75f); }
HashMap
-
- HashMap底层是通过数组+链表实现的,KV都可以为NULL,线程不安全;
- 初始size为16,扩容:newsize = oldsize * 2,size一般为2的n次幂;
- HashMap扩容针对整个Map,每次扩容后,需要对数组中的元素重新计算位置,再重新插入;
- HashMap都是先扩容再判断是否需要扩容,所以会有无效扩容(无效扩容就是扩容后再不插入数据的扩容就叫无效扩容);
- HashMap容量大于75%时就会触发扩容;
- 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length;
ConcurrentHashMap
-
- ConcurrentHashMap底层是通过数组+链表实现的,是线程安全的;
- 通过将Map分为N段Segment,提供相同线程安全(就是分段加锁)。默认分为16段;
- ConcurrentHashMap当数组容量超过75%会触发扩容,但是不会对整个Map扩容,在插入前判断是否需要扩容,有效避免无效扩容;
/** * The default initial table capacity. Must be a power of 2 * (i.e., at least 1) and at most MAXIMUM_CAPACITY. */ private static final int DEFAULT_CAPACITY = 16; /** * The default concurrency level for this table. Unused but * defined for compatibility with previous versions of this class. */ private static final int DEFAULT_CONCURRENCY_LEVEL = 16; /** * The load factor for this table. Overrides of this value in * constructors affect only the initial table capacity. The * actual floating point value isn't normally used -- it is * simpler to use expressions such as {@code n - (n >>> 2)} for * the associated resizing threshold. */ private static final float LOAD_FACTOR = 0.75f;