ArrayList：
transient Object[] elementData;
- 动态扩容,扩容最大到 Integer.MaxValue 2的31次方，默认初始化容量为10，以2的幂扩容，
- modCount记录修改版本 乐观锁的设计,被修改一次modCount会加1，iterate时，比较modCount 快速失败，抛出ConcurrentModificationExceptions，以此方式来尽快告知程序可能会有并发问题
- 使用System.arraycopy将旧数组内容拷贝到新数组
LinkedList：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
利用链表实现的;
- 实现了接口 Queue，即拥有队列：队尾添加新元素，队尾删除元素；
- Deque，双端队列的属性，可以在队头尾添加删除元素，并且可供用户选择是抛异常和不抛异常型的数据修改操作,
- modCount记录修改版本 乐观锁的设计,被修改一次modCount会加1，iterate时，比较modCount 快速失败，抛出ConcurrentModificationExceptions，以此方式来尽快告知程序可能会有并发问题
HashMap
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
- 对象数组，数组中存放的是Node节点或者TreeNode数节点，即常听人说的 数组+链表结构，在冲突比较严重的情况下（解决冲突的链表长度达到8时），会将链表树化 (treeify or untreeify) 成红黑树
-
AVL树和红黑树之间有什么区别
红黑树 vs AVL数 -
AVL树和红黑树的应用场景
应用场景
LinkedHashMap
数据结构
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
static class HashMap.Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
static class LinkedHashMap.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);
}
}
static final class HashMap.TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
-
本质上，LinkedHashMap = HashMap + 双向链表，它是一个将所有Entry节点链入一个双向链表的HashMap。在LinkedHashMapMap中，所有put进来的Entry都保存在如下面第一个图所示的哈希表中，但由于它又额外定义了一个以head为头结点的双向链表(如下面第二个图所示)，因此对于每次put进来Entry，除了将其保存到哈希表中对应的位置上之外，还会将其插入到双向链表的尾部。
LinkedHashMap.Entry解读 - 操作代码
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
- 实现LRU (Least recently used，最近最少使用)算法
使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾：get方法通过调用afterNodeAccess方法来实现；put方法在覆盖已有key的情况下，也是通过调用afterNodeAccess方法来实现，在插入新的Entry时，则是通过createEntry中的addBefore方法来实现。这样，我们便把最近使用的Entry放入到了双向链表的后面。多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除最前面的Entry(head后面的那个Entry)即可，因为它就是最近最少使用的Entry（前提是覆写了removeEldestEntry()方法返回true）。
TreeMap
private transient Entry<K,V> root;
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
利用二叉树结构对KV的Node进行存取 遍历，时间复杂度为log(n)
应用：treeMap实现了 SortedMap，拥有tailMap的能力，可以查找比当前key大，与它最接近的一个kv串，进行返回，因此，可以利用这个特性来实现 一致性哈希算法，存储hash环数据
