Hashmap
JDK 1.8中的 HashMap 有哪些优化
- 扩容前长度为 16，用于计算 (n-1) & hash 的二进制 n-1 为 0000 1111，扩容为 32 后的二进制就高位多 了 1，为 0001 1111。
- 采用数组+链表/红黑树的模型
- 链表采用尾插法
JDK 1.8中的 ConcurrentHashMap 有哪些优化
- 使用CAS+synchronized替换segemnt+ReentrantLock
- 将bucket视为segement，锁的粒度为一个bucket
JDK 1.7 HashMap高并发死循环问题
- 核心原因是头插法反转了链表
- LinkedHashmap和LRU的实现原理
Skiplist
- 跳表是一种能替代平衡树/红黑树的数据结构
- 跳表实现简单, 锁粒度可以做到很细, 适用于内存但不适用磁盘(随机io次数比较多)
- LSM-Tree中的MemTable使用跳表
Redis ZSET为什么用跳表而不用平衡树？
- 范围查找更简单
- 算法更容易实现
- 插入和删除更简单
- 多线程友好
Tree
MySQL索引为什么不用跳表，Redis为什么不用B+树
- skiplist层级会更多，这在内存中不是问题但是面对磁盘就是问题
- 非完全二叉树需先补齐成完全二叉树才能按数组存储
- 二叉树中序排列会得到有序的序列
用数组表示二叉树
- 前序的话数组第一个元素则为root
- 后序的话数组最后一个元素则为root
前序和后序序列数组无法确定唯一的二叉树
- 例如前序: [1, 2, 3]和后序：[3, 2, 1]可对应对称的两个二叉树
- 二叉树的先序遍历（非递归版）
- 二叉树的中序遍历（非递归版）
- 二叉树的后序遍历（非递归版）
- 从上往下打印二叉树
- 二叉树的构建
- 二叉树的镜像
- 二叉树的子结构
- 二叉搜索树的后序遍历序列
- 重建二叉树
Linkedlist
- 将搜索二叉树转换成双向链表
- 删除单链表的第 K 个节点
- 删除单链表的中间节点
- 如何优雅着反转单链表
- 环形单链表约瑟夫问题
- 三种方法带你优雅判断回文链表
- 将单向链表按某值划分成左边小，中间相等,右边大的形式
- 复制含有随机指针节点的链表
- 将单链表的每 K 个节点之间逆序