Java 集合类
Collections 框架图
List 框架图
Set 框架图
Map 框架图
Queue 框架图
HashMap
并发下的 HashMap 会有哪些安全问题?
这里我只是简单的说了写覆盖跟不可重复读(联想到数据库了),面试官就放我过了。
添加元素时头插还是尾插?
1.7 头插,1.8 尾插。
数组长度为什么必须是 2 的指数幂
减少哈希冲突,均匀分布元素。
1)通过将 Key 的 hash 值与 length-1 进行 & 运算,实现了当前 Key 的定位,2 的幂次方可以减少冲突(碰撞)的次数,提高 HashMap 查询效率;
2)如果 length 为 2 的次幂,则 length-1 转化为二进制必定是 11111…… 的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;如果 length 不是 2 的次幂,比如 length 为 15,则 length-1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。
如何扩容的
(1) 初始扩容因子
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
为什么是
0.75
这个值呢?
这是因为对于使用链表法的哈希表来说,查找一个元素的平均时间是 O(1+n)
,这里的 n
指的是遍历链表的长度,因此加载因子越大,对空间的利用就越充分,这就意味着链表的长度越长,查找效率也就越低。如果设置的加载因子太小,那么哈希表的数据将过于稀疏,对空间造成严重浪费。
(2) 何时扩容
首次 put
的时候,如果 table
为空,会执行扩容:
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
在 put
方法中,size++
之后的值如果大于 threshold
,那么也会执行 resize
方法。
if (++size > threshold)
resize();
(3) 扩容扩多少
首次扩容:
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
非首次扩容,新的容量和新的 threshold
都是翻一倍:
newCap = oldCap << 1;
newThr = oldThr << 1;
(4) 为何扩容
为了避免散列表性能下降。碰撞越来越严重。越来越多的链表。速度越来越慢。
元素如何迁移
- 创建新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- 遍历旧数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// ...
}
}
- 如果
e.next
不为空,即数组里面只存储了这一个元素
newTab[e.hash & (newCap - 1)] = e;
- 如果
e
是TreeNode
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- 如果
e
有next
,维持原来的顺序,挂到新的数组上
原来的元素在重新计算 hash
之后,会放到两个数组的坑里面。
// (e.hash & oldCap) == 0 的属于 loHead
newTab[j] = loHead;
// 否则属于 hiHead
newTab[j + oldCap] = hiHead;
头插法设计思路
JDK1.7是考虑新增数据大多数是热点数据,所以考虑放在链表头位置,也就是数组中,这样可以提高查询效率,但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树,这样一来在数组后节点长度不断增加时,遍历一次的次数就会少很多,相比头插法而言,尾插法操作额外的遍历消耗已经小很多了。
也有很多人说避免多线程情况下hashmap扩容时的死循环问题,我个人觉得避免死循环的关键不在尾插法的改变,而是扩容时,用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。
get 方法如何实现的
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- 首先使用
(n - 1) & key.hash
定位到这个key
应该落到table
的哪一个桶里面,其中n
是指table
的长度。 - 然后看这个桶里面的
first
元素是否是目标值,如果是,直接返回。 - 否则看
first
是否属于TreeNode
,如果是TreeNode
,则调用getTreeNode
方法;否则沿着e.next
往下遍历,并依次检查条件key.hash == k.hash
并且key.equals(k)
。
红黑树
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD
). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5
on average for the default resizing threshold of 0.75
, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k
are (exp(-0.5) pow(0.5, k) / factorial(k))
. The first values are:
根据泊松分布实验发现,假设hashmap长度length为16,假设放入12(0.75*16)个数据到hashmap中,链表中存放8个节点的概率仅为0.00000006,而链表中存放1~7节点的概率为:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
红黑树 VS AVL
红黑树的平衡性并不如 AVL 树,它维持的只是一种大致上的平衡 , 并不严格保证左右子树的高度差不超过 l 。这导致在相同节点数的情况下,红黑树的高度可能更高 ,也就是说 , 平均查找次数会高于相同情况下的 AVL 树。在插入时,红黑树和AVL 树都能在至多两次旋转内恢复平衡。在删除时,由于红黑树只追求大致上的平衡 , 因此红黑树能在至多三次旋转内恢复平衡,而追求绝对平衡的 AVL 树,则至多需要 O(logn) 次旋转。 AVL 树在插入与删除肘,将向上回溯确定是否需要旋转,这个回溯的时间成本最差可能为 O(logn),而红黑树每次向上回溯的步长为 2 , 回溯成本降低。面对频繁的插入和删除 ,红黑树更为合适;面对低频修改、大量查询时,AVL 树将更为合适。
key、Value 可否为 null
并发问题
(1) 数据丢失
新添加的元素直接放在 slot
槽上,如果两个线程同时执行到这里,那么一个线程的赋值就会被另一个覆盖掉:
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
(2) 循环死链
whilte (null != e) {
Entry<K, V> next = e.next;
e.next = newTable[5883];
newTable[5883] = e;
e = next;
}
TreeMap
如何保证有序
TreeMap 底层是红黑树结构,而红黑树本质是一颗二叉查找树。如下是 put
方法的部分细节即可:
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
LinkedHashMap
特点
- 循环双向链表
- key 和 value 都允许为空
- key 重复会覆盖
- 有序的
- LinkedHashMap 是非线程安全的
Entry
LinkedHashMap
的 Entry<K,V>
继承了 HashMap.Node<K,V>
的数据结构,并且新增了 before
,after
来维护链表插入/访问顺序。head
存储第一个头结点,tail
存储尾结点,accessOrder=true
链表维护访问顺序,false
链表维护插入顺序。这个访问顺序指的是按照最近被访问的Entry的顺序进行排序(从最近最少访问到最近最多访问)。基于这点可以简单实现一个采用**LRU(Least Recently Used)**策略的缓存。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
get
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
ConcurrentHashMap
jdk1.8
之前,ConcurrentHashMap
采用分段锁(Segment),对不同段的Entry
进行操作互不影响;jdk1.8
之后,ConcurrentHashMap
直接使用Node数组+链表+红黑树,通过synchronized
和CAS
来保证并发的可靠性。
插入流程
在插入的時候,有多个地方用到了 synchronized
,以 putVal
举例子,在发现想要插入的这个槽的 Node<K, V>
不为空的时候,就会去 synchronized (node)
,去锁住这个槽的链表的第一个 Node<K, V>
节点。
扩容流程
JDK7 获取集合大小流程
JDK8 获取集合大小流程
- 并发量较小,优先使用 CAS 直接更新 baseCount
- 更新 baseCount 冲突,则会认为进入到比较激烈的竞争状态,通过启用 counterCells 减少竞争,通过 CAS 的方式把总数更新情况记录在 counterCells 对应的位置上
- 如果更新 counterCells 上的某个位置出现了多次失败,则会通过扩容 counterCells 的方式减少冲突
- 当 counterCells 处在扩容期间时,会尝试更新 baseCount 值
对于元素总数的统计,逻辑就非常简单了,只需要让 baseCount 加上各 counterCells 内的数据,就可以得出哈希内的元素总数,整个过程不需要借助锁。
// 记录了元素总数值,CAS 更新这个值
private transient volatile long baseCount;
// 计数器
static final class CounterCell {}
// 竞争激烈,线程会把总数更新情况存放到这个数组中
// 竞争进一步加剧,会通过扩容减少竞争
private transient volatile CounterCell[] counterCells;
ArrayList
初始容量
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
new ArrayList()
时拥有的是一个空数组,在第一次 add
的时候,才会创建一个长度为 10 的数组。
如何扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 扩容后新的数组长度为
oldCapacity + (oldCapacity >> 1)
,也就是旧容量的 1.5 倍 - 然后使用
Arrays.copyOf
静态方法将旧数组里面的内容全部拷贝到新的数组里面
放满了会发生什么
抛出 OOM 异常:
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
多线程使用
- 数组越界异常
- 元素值覆盖和为空问题
elementData[size++] = e
transient
transient Object[] elementData;
ArrayList
在序列化的时候会调用writeObject
,直接将size
和element
写入ObjectOutputStream
;反序列化时调用readObject
,从ObjectInputStream
获取size
和element
,再恢复到elementData
。
为什么不直接用elementData
来序列化,而采用上诉的方式来实现序列化呢?原因在于elementData
是一个缓存数组,它通常会预留一些容量,等容量不足时再扩充容量,那么有些空间可能就没有实际存储元素,采用上诉的方式来实现序列化时,就可以保证只序列化实际存储的那些元素,而不是整个数组,从而节省空间和时间。
fail-fast 机制
fail-fast 机制是一种对集合遍历操作时的错误检测机制,在遍历中途出现意料之外的修改时,通过 unchecked 异常暴力地反馈出来。这种机制经常出现在多线程环境下,当前线程会维护一个计数比较器,即 expectedModCount
,记录已经修改的次数。在进入遍历前, 会把实时修改次数 modCount
赋值给 expectedModCount
,如果这两个数据不相等,则抛出异常。java.util
下的所有集合类都是 fail-fast,而 concurrent 包中的集合类都是 fail-safe 。
(1) masterList
集合元素个数的增加、删除,均会导致子列表的遍历、增加、删除,进而产生 fail-fast 机制。
List masterList = new ArrayList();
masterList.add("one");
masterList.add("two");
masterList.add("three");
masterList.add("cour");
masterList.add("five");
List branchList = masterList.subList(0, 3);
// 下面三行代码,会导致 branchList 操作会出现 ConcurrentModificationException 异常
masterList.remove(O);
masterList.add("ten");
masterList.clear();
(2) foreach 遍历,产生 fail-fast 异常
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add("three");
for (String s : list) {
if ("one".equals(s)) {
list.remove(s);
}
}
CopyOnWriteArrayList
底层数据结构
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
// 内部只能通过 getArray() 访问 array
final Object[] getArray() {
return array;
}
添加元素
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
读取元素
private E get(Object[] a, int index) {
return (E) a[index];
}
public E get(int index) {
return get(getArray(), index);
}