栈

关键点：

1. 后进先出（last in, first out）
2. 插入操作称为Push（压入），删除操作称为Pop（弹出）
3. 数组实现栈：top指针指向栈顶元素

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   private int[] stack = new int[9]; int top = -1; // top指针 boolean stackEmpty(){ if(top == -1){ return true; } return false; } void push(int x){ top++; stack[top] = x; } int pop(){ int value = stack[top]; top--; return value; }

队列

关键点：

1. 先进先出（first in, first out）
2. 插件操作称为Enqueue（入队），删除操作称为Dequeue（出队）
3. 数组实现队列：
   1. 充分利用数组，实现循环
   2. 两个指针：head，tail
      1. head指向队尾元素
      2. tail指向队尾的下一个元素 – 目的是为了判断队满与队空
   3. 队空判断：head == tail
   4. 队满判断：tail + 1 = head

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

      private int[] queue = new int[8]; private head, tail = 0; // 入队 void enqueue(int x){ // 判断队满 if((tail + 1) == head) { return ; } queue[tail] = x; tail = (tail+1)%queue.length; } // 出队 Integer dequeue(){ // 判断队空 if(tail == head) { return null; } int value = queue[head]; head = (head+1)%queue.length; return value; }

散列表（hash table）

关键点：

1. 实现字典操作的一种数据结构
2. 思想：数组的推广使用，利用数组下标的快速寻址，同时控制数组的大小
3. 平均时间复杂度O(1)，最坏时间复杂度O(n)
4. 寻址：通过散列函数（hash function）计算其散列值
   1. 除法散列法：h(k)=k mod m（m为槽数，即数组长度）— m最好是素数，不应为2的幂
   2. 乘法散列法： m 乘以 kA 的小数部分（m为槽数，即数组长度）— 对m没有取值要求，一般为2的幂
5. 冲突：链表法
   1. 数组+链表实现
   2. 装载因子（load factor）的定义：能存放n个元素的、具有m个槽位的散列表T，T的装载因子（load factor）a = n/m，即一个链的平均存储元素数

Java的HashMap：

1. HashMap非线程安全，Collections.synchronizedMap()使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
2. 冲突：使用链地址法解决
3. 存储结构：数组+链表+红黑树（JDK1.8增加了红黑树部分），链表长度大于8时转换为红黑树，复杂度从O(n)降到O(logn)
4. 寻址：
   1. 取key的hashCode值，h = key.hashCode()；
   2. 高位参与运算，h ^ (h >>> 16)； —- 由于模运算比较耗时，减少参与模运行的位数
   3. 取模运算，h & (length-1) — 由于length总是2的n次方，h & (length-1)运算等价于对length取模
5. 扩容时机：
   1. 数组length默认值为16
   2. load factor(装载因子)默认为0.75
      1. 默认的负载因子0.75是对空间和时间效率的一个平衡选择
      2. 内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1
   3. 当前的扩容阀值：threshold = length * load factor，即在length和load factor固定的情况下，最大的存储链值对
6. 扩容：数组的length扩大2倍，目的是不用重新计算hashcode，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置
7. 其他点：
   1. 在HashMap中，数组的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计。— HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
      1. 常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）
   2. 这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。
8. 使用注意点：
   1. 扩容是一个特别耗性能的操作，所以使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
   2. HashMap是线程不安全的，在并发的环境中建议使用ConcurrentHashMap

树的遍历方式

通过key的输出位置命名遍历方法：

1. 先序遍历：
   1. print key
   2. print left.key
   3. print right.key
2. 中序遍历：
   1. print left.key
   2. print key
   3. print right.key
3. 后序遍历：
   1. print left.key
   2. print right.key
   3. print key

二叉搜索树

关键点：

1. 定义：所有的结点都满足left.key <= key <= right.key
2. 顺序输出：中序遍历顺序输出
3. 后继和前驱：
   1. 概念：中序遍历的下一个元素和上一个元素
   2. key的后继为key的右子树中的最左结点
   3. key的前驱为key的左子树中的最右结点
4. 插入：先找到插入点

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   class Node{ public int key; public Node p; public Node left; public Node right; } Node tree_insert(Node root, Node z){ Node x = root; Node y = null; while(x != null){ y = x; x = (z.key >= x.key) ? x.right : x.left; } // root为null if(y == null) { return z; } else if(z.key >= y.key){ y.right = z; } else { y.left = z; } return root; }

5. 删除：三种情况
   1. 待删除结点z，没有左右结点，直接删除
   2. 待删除结点z，有且只有一个结点，直接替换就行
   3. 待删除结点z，有两个结点，使用z的后继y来替换，y的右结点替换y的位置

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

      class Node{ public int key; public Node p; public Node left; public Node right; } Node tree_delete(Node root, int key){ // 先查找到对应的节点z Node z = tree_search(root, key); // 没有左结点，直接替换 if(z.left == null){ transplant(root, z, z.right); } else if(z.right == null){ // 没有右结点，直接替换 transplant(root, z, z.left); } else { // 左右结点都有 // z.right的最小元素，就是z的后继 z_succeed = tree_mininum(z.right); // z_succeed有两种情况 if(z.right != z_succeed){ // 后继是z.right的最小结点 // 先把 z_succeed.right 接上 z_succeed.p transplant(root, z_succeed, z_succeed.right); z_succeed.right = z.right; z_succeed.right.p = z; } transplant(root, z, z_succeed); z_succeed.left = z.left; z_succeed.left.p = z_succeed; } }

6. 时间复杂度：O(h), h是二叉搜索做的高度
   1. 最坏查找性能：O(n) — 单链
   2. 最好查找性能：O(lgn) — 刚好是完全二叉树
7. 二叉搜索树的优化思路：平衡二叉搜索树

红黑树

关键点：

1. 意义：是一棵二叉搜索做，保证最坏情况的时间复杂度为O(lgn)
2. 实现思路：红黑树是一棵二叉搜索做，它在每个结点上增加一个存储位来表示结点的颜色，可以是Red或Back。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而返似于平衡的。
3. 定义：满足如下红黑性质的二叉搜索做
   1. 每个节点要么是红色，要么是黑色。
   2. 根节点必须是黑色
   3. 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
   4. 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
4. 操作：
   1. 旋转：左旋，右旋，都能保持二叉搜索树的特性
   2. 插入：
      1. 按二叉搜索树插入z，并把z标记为RED
      2. 保持红黑树性质：通过着色与旋转恢复红黑树的特性，有如下几种情况：
         1. Case1：当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
            1. 将“父节点”设为黑色。
            2. 将“叔叔节点”设为黑色。
            3. 将“祖父节点”设为“红色”。
            4. 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
         2. Case2：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
            1. 将“父节点”作为“新的当前节点”。
            2. 以“新的当前节点”为支点进行左旋。
         3. Case3：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
            1. 将“父节点”设为“黑色”。
            2. 将“祖父节点”设为“红色”。
            3. 以“祖父节点”为支点进行右旋。
   3. 删除：
      1. 先找到需删除的元素
      2. 按二叉搜索树的方式删除元素
      3. 保持红黑树性质：着色与旋转（只有删除点是BLACK的时候，才会触发调整函数）
         1. 略，请查看参考里的文章
5. 时间复杂度：插入，删除，查询的时间复杂度都是O(lgn)
6. 问题：
   1. 插件时，为什么要默认设置为Red？ — 如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，为了满足定义，那就要调整其他路径上的黑节点数量
   2. 删除时，为什么只只有删除点是BLACK的时候，才会触发调整函数？ — 因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4

Java里的TreeMap是通过红黑树实现：可以顺序输出所有的元素，所有操作的时间复杂度为O(lgn)

参考

1. 算法导论
2. Java8的HashMap详解（存储结构，功能实现，扩容优化，线程安全，遍历方法）
3. 史上最清晰的红黑树讲解（上）
4. 史上最清晰的红黑树讲解（下）