【Java集合容器类笔记】

【Java集合/容器类笔记】

【Map专题】

HashMap 

分散Hash值：   (h ^ (h >>> 16)) & HASH_BITS  （二进制全为1的32位最大值）

计算hash值在数组中的下标位置  ： idx = (table.length - 1) & hash ;  

链表大于多少时扩展为红黑树？    

TREEIFY_THRESHOLD = 8      链表长度 >= 7 (TREEIFY_THRESHOLD - 1) 时转为树

树何时退化为链表 ？

（root.right == null  ||  (rl = root.left) == null || rl.left == null） 退为链表：first.untreeify(map) 

以为判断对应最大节点数为 6，也就是树节点 <= 6 时，退化为链表

HashMap底层数组 扩容条件，缩容条件

允许Null key，hashcode = 0；允许null value

HashMap红黑树实现：

HashMap 删除后调整：java.util.HashMap.TreeNode#balanceDeletion

HashMap  插入后调整：java.util.HashMap.TreeNode#balanceInsertion

linkedHashMap

实现了LRU

TreeMap   (key 存放为排序的树)

TreeMap 中红黑树与 HashMap中红黑树是否同一实现？ 不是

TreeMap 与TreeSet 中的 tailMap( fromKey ) 从红黑树中查找比fromKey大的值的集合 ，用于实现一致性Hash

ConcurrentHashMap  （并发迁移源码需要进一步学习）

该map读写锁的实现特性

扩容时，是否加全局锁    REP： 扩容创建新数组 ，替换老数组

jdk1.8 放弃 Segment 

维护AQS 队列需要更多的资源

synchronized  已经做过偏向锁优化

扩容核心方法：    java.util.concurrent.ConcurrentHashMap#transfer 

扩容阈值计算：sizeCtl = 0.75*n;   jdk代码优化：sizeCtl = (n << 1) - (n >>> 1); 

容量为2的幂次方的目的：

1）计算下标值       

2）方便数据扩容迁移 (ex: 1 放在 1的位置 或者 是 1 + length的位置)   

如何判断放在高位还是低位？ REP ：比如默认的len=16 ； 迁移hash = 20 ， runbit = 20 & 16 （10000）去后四位的意思，IF （runbit == 0 ）THEN 低位数组 ELSE 新扩容出的高位数组 ；

其他问题：

读不加锁的原因？

REP：数组 volatile修饰、Node volatile修饰

IdentityHashMap

允许空值且相互不覆盖，空值key 转换为 new Object()

hashCode实现 ：System.identityHashCode 生成对象唯一的hashCode 

关键区别：类似对象地址作为对象hashCode保证唯一性，

EX: str1 = new String("abc") 作为key ，new出的每次都不一样，

但用 get("abc") 也能获取，存在不确定性，应该用 get( str1 )

【Collection专题】

---

【List】

ArrayList

扩容因子、条件 ：大于扩容因子时（一般是0.75），扩容为原来的两倍

缩容条件 ：减少到1/4时，缩容为1/2

linkedList

是否双向链表？REP：双向链表，Node包含pre、next指针

CopyOnWriteList

  源码设计中的疑问 ，为什么 方法内用final引入成员变量

REP：1、防止在内部类中成员变量的值被改变  

实现：每次写入一个元素时，直接拷贝整个数组扩容，赋值到最后一个元素

优点：适合并发场景，读多，写极少的情况，读无锁高性能

缺点：写一个，扩容一个元素拷贝整个数组，写频繁的场景性能影响大

【Set】

无序集合：HashSet 、linkedHashSet

HashSet

底层为HashMap，只存key，固定一个相同的value （new Object）

linkedHashSet

基于HashSet 、主要区别是 spliterator方法的实现，用于区分是否要按add 迭代顺序输出

有序集合：：TreeSet implements SortedSet

TreeSet 也有tailMap方法

【Queue】

阻塞队列：BlockingQueue（Dqueue 双端队列）： linkedBlockingQueue、ArrayBlockingQueue

一般用于线程池任务队列

优先队列：PriorityQueue

延迟队列：DelayQueue

底层基于PriorityQueue按自定义的delay时间排序，delay时间<=0时才能被取出

队列中存放的都Delayed对象，实现getDelay(TimeUnit)方法、compareTo方法

【延伸】

StringBuffer （同步锁） 、StringBuilder （不安全）

append的实现：str.getChars(0, len, value, count);     读取到value原始数组，空间不足时，扩展value