数据类型.数.map详细总结

树： alt

满二叉树：每个非叶子节点有两个节点

完全二叉树：设一棵二叉树深度为h。除了第h层外，其它各层的结点数都达到最大个数，且第h层（最下面一层）的所有结点都连续集中在最左边。

平衡二叉树：左右两个子树的高度差不超过1，且左右子树都是平衡二叉树

二叉搜索树，所有左节点小于右节点

AVL树自平衡二叉查找树增加和删除需要一次或多次旋转来重新平衡

红黑树，root和叶子都是黑色，从root到叶子经过黑色节点数量一致，不严格的高度平衡

B+树，与B+树的区别：叶子节点只存储索引，叶子节点有双向链表。

B树

关于一些树的概念：树的出度=入度哈夫曼树：最优树

树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 哈夫曼树：带权路径长度达到最小的二叉树，也叫做最优二叉树。

注意到这里，哈夫曼树只是一棵最优二叉树，不一定是完全二叉树，也不一定是平衡二叉树、满二叉树。完全是八竿子打不着的事情，人家哈夫曼树不关注树的结构，只关注带权路径长度好吗。。

alt

map：hashmap Treemap hashTable concurrentHashmap hashmap获得hash值：通过高16位与低16位的异或处理来获得

TreeSet HashSet

concurrentHashmap :synchorinized+CAS+volatile 在put过程中使用cas进行操作（先CAS再S synchornized）

concurrentHashMap加锁时上锁的地方是TreeBin（包装TreeNode，hashmap直接用TreeNode），而不是树的根节点，因为红黑树可能会左旋右旋而改变根节点，从而导致其他线程在获得锁，导致错误。

扩容问题：数组下标如何再分配 table扩容为2N+1，默认为11

hashmap 扩容为2N 默认为16

concurrentHashMap用一个CounterCell数组来记录元素个数（通过分片的方式来应对并发）

LastRun节点 alt LastRun节点在扩容中的用法记住

如何判断当前concurrenthashmap正在扩容？ 当前槽hash为-1

（1.7之前直接重新计算，1.8优化迁移） 链表迁移（锁住node在迁移）扩容时先判断节点高低位（hashcode&原数组长度）（注意这个原数组长度，他保证了扩容后hash位置的正确性），（用高低位拼接新链表时用头插法）高位去n+i，低位还是i

红黑树迁移（锁住Bin再迁移）以遍历的方式通过高低位组件新链表，高位去（n+i），低位不动，变短了不够红黑树了就用链表

https://blog.csdn.net/zzu_seu/article/details/106698150（更多高质量关于此的面试题，尤其扩容过程中的put、get等）

扩容时的get、put方法

get：正在扩容时，不影响查询，迁移完成时，协助扩容

put/remove 正在扩容时，阻塞，迁移完成时，协助扩容

put方法总结（concurrenthashmap） ①先传入一个k和v的键值对，不可为空（HashMap是可以为空的），如果为空就直接报错。 ②接着去判断table是否为空，如果为空就进入初始化阶段。 ③如果判断数组中某个指定的桶是空的，那就直接把键值对插入到这个桶中作为头节点，而且这个操作不用加锁。

④如果这个要插入的桶中的hash值为-1，也就是MOVED状态（也就是这个节点是forwordingNode），那就是说明有线程正在进行扩容操作，那么当前线程就进入协助扩容阶段。

⑤需要把数据插入到链表或者树中，如果这个节点是一个链表节点，那么就遍历这个链表，如果发现有相同的key值就更新value值，如果遍历完了都没有发现相同的key值，就需要在链表的尾部插入该数据。插入结束之后判断该链表节点个数是否大于8，如果大于就需要把链表转化为红黑树存储。（应首先看看map长度是否大于64，若不大于，先进行map扩容）

⑥如果这个节点是一个红黑树节点，那就需要按照树的插入规则进行插入。 ⑦put结束之后，需要给map已存储的数量+1，在addCount方法中判断是否需要扩容

数组扩容方法：system.arraycopy()或者Arrays.copyOf()

CopyOnwriteArrayList 实现读写分离；写时读不堵塞，只对写操作加锁

非阻塞队列ConcurrentLinkedQueue 性能较高主要是用CAS

阻塞队列BlockingQueue 三种实现ArrayBlockingQueue、LinkedBlockingQueue 、PriorityBlockingQueue