Java核心数据结构
Map/List/ConcurrentHashMap
ArrayList数组列表,初始容量10, 扩容 JDK1.7 是1.5倍向下取整, JDK1.8是0.5倍向下取整, 根据索引访问速度快
Linked链表数组双端队列, 增删速度快, 查找慢,(需要遍历), 根据索引查找,判断索引是否存在, 索引小于Size/2, 从头遍历, 大于等于Size/2则从尾遍历
HashMap
1.初始化准备存储空间； 2.计算key的hash值(整数)，hash算法-均匀分布 3.由2的结果，即hash(key)，取模计算索引i (HashSet元素无序的原因) 4.判断HashTable[i]的元素类型，插入 ①覆盖插入(HashSet元素互异的原因) ②链表插入 ③二叉树插入 ④链表树化后插入 5.HashMap的大小自增 6.判断是否要扩容
HashMap的三大数值概念:
容量: HashMap最多能容纳的元素个数, 它与HashTable的length相等, 因为hash(key)寻索引位置
实际元素个数: size
HashMap树化使用红黑树,红黑树的优点: 查找/插入删除的算法复杂度都是O(log N)
MIN_TREEIFY_CAPACITY(64): 进行树形化, HashMap的容量必须达到64及以上, 容量小于等于32则使用扩容
TREEIFY_THRESHOLD(8): z增加元素时, HashMAp容量>=64后, HashTable位置上的链表Node节点元素总数达到8及以上, 就将单链表Node<K,V>[] 转化为红黑树TreeNode<K, V> UNTREEIFY_THRESHOLD(6): 移除元素时, 当HashMap中HashTable位置上的红黑树TreeNode节点元素总数达到6及以下, 就将红黑树节点TreeNode<K, V>转换为单链表节点Node<K, V>
LinkedHashMap
继承HashMap, 同时额外维护了双链表, 访问该双链表保证元素的顺序, 可设置根据元素访问频率, 移除最近最少访问的元素(LRU)
- LinkedHashMap 拥有与 HashMap 相同的底层哈希表结构，即数组 + 单链表 + 红黑树，也拥有相同的扩容机制。
- LinkedHashMap 相比 HashMap 的拉链式存储结构，内部额外通过 Entry 维护了一个双向链表。
- HashMap 元素的遍历顺序不一定与元素的插入顺序相同，而 LinkedHashMap 则通过遍历双向链表来获取元素，所以遍历顺序在一定条件下等于插入顺序。
- LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在元素被访问后改变其在双向链表中的位置。
LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在元素被访问后改变其在双向链表中的位置。
- 每次添加新节点的时候实际上是调用 newNode 方法生成了一个新的节点，LinkedHashMap 复写了该方法，双向链表的操作一定在linkNodeLast方法中实现：将新的节点与之前双向链表的最后一个节点（tail）建立关系，彼此拥有指向对方的引用，这么做就能确保了双向链表的元素之间的关系即为添加元素的顺序。
- LinkedHashMap 删除节点的操作，对于 afterNodeRemoval（node） HashMap 中是空实现，而该方法，正是 LinkedHashMap 删除对应节点在双向链表中的关系的操作
- LinkedHashMap 与 HashMap 添加和删除元素的不同，可以看出除了维护 Hash表中元素的关系以外，LinkedHashMap 还在添加和删除元素的时候维护着一个双向链表。
- 该方法随 LinkedHashMap 构造参数初始化，accessOrder 默认值为 false。–LinkedHashMap 通过afterNodeAccess 这个后置操作，可以在 accessOrde = true 的时候，使双向链表维护哈希表中元素的访问顺序。
- LinkedHashMap 的迭代器，由于有双向链表的存在，它相比 HashMap 遍历节点的方式更为高效–直接指向了当前节点的 after 后驱节点
ConcurrentHashMap
JDK1.7数据结构
JDK1.8数据结构
初始化Table
private final Node<K, V>[] initTable() {
Node<K, V>[] tab;
int sc;
While ((tab = this.table) == null || this.table.length == 0) {
if ((sc = this.sizeCtl) < 0) {
Thread.yeild();
} else if (U.compareAndSwapInt(this, this.SIZECTL, sc, -1) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
this.table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
容量计算
扩容图示
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
总结
- 捐赠|Donate, 实践撰文分享实属不易, 您的支持能为更多省时省事的分享提速, 谢谢!
 微信 |
 支付宝 |
 MiXin |