| 方法 | 描述 | | :---: | :---: | | UF(int N) | 构造一个大小为 N 的并查集 | | void union(int p, int q) | 连接 p 和 q 节点 | | int find(int p) | 查找 p 所在的连通分量 | | boolean connected(int p, int q) | 判断 p 和 q 节点是否连通 | ```java public abstract class UF { protected int[] id; public UF(int N) { id = new int[N]; for (int i = 0; i < N; i++) id[i] = i; } public boolean connected(int p, int q) { return find(p) == find(q); } public abstract int find(int p); public abstract void union(int p, int q); } ``` ## quick-find 可以快速进行 find 操作，即可以快速判断两个节点是否连通。 同一连通分量的所有节点的 id 值相等。 但是 union 操作代价却很高，需要将其中一个连通分量中的所有节点 id 值都修改为另一个节点的 id 值。
```java public class QuickFindUF extends UF { public QuickFindUF(int N) { super(N); } @Override public int find(int p) { return id[p]; } @Override public void union(int p, int q) { int pID = find(p); int qID = find(q); if (pID == qID) return; for (int i = 0; i < id.length; i++) if (id[i] == pID) id[i] = qID; } } ``` ## quick-union 可以快速进行 union 操作，只需要修改一个节点的 id 值即可。 但是 find 操作开销很大，因为同一个连通分量的节点 id 值不同，id 值只是用来指向另一个节点。因此需要一直向上查找操作，直到找到最上层的节点。
```java public class QuickUnionUF extends UF { public QuickUnionUF(int N) { super(N); } @Override public int find(int p) { while (p != id[p]) p = id[p]; return p; } @Override public void union(int p, int q) { int pRoot = find(p); int qRoot = find(q); if (pRoot != qRoot) id[pRoot] = qRoot; } } ``` 这种方法可以快速进行 union 操作，但是 find 操作和树高成正比，最坏的情况下树的高度为触点的数目。
## 加权 quick-union 为了解决 quick-union 的树通常会很高的问题，加权 quick-union 在 union 操作时会让较小的树连接较大的树上面。 理论研究证明，加权 quick-union 算法构造的树深度最多不超过 logN。
```java public class WeightedQuickUnionUF extends UF { // 保存节点的数量信息 private int[] sz; public WeightedQuickUnionUF(int N) { super(N); this.sz = new int[N]; for (int i = 0; i < N; i++) this.sz[i] = 1; } @Override public int find(int p) { while (p != id[p]) p = id[p]; return p; } @Override public void union(int p, int q) { int i = find(p); int j = find(q); if (i == j) return; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; } } } ``` ## 路径压缩的加权 quick-union 在检查节点的同时将它们直接链接到根节点，只需要在 find 中添加一个循环即可。 ## 各种 union-find 算法的比较 | 算法 | union | find | | :---: | :---: | :---: | | quick-find | N | 1 | | quick-union | 树高 | 树高 | | 加权 quick-union | logN | logN | | 路径压缩的加权 quick-union | 非常接近 1 | 非常接近 1 | # 五、排序 待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。 研究排序算法的成本模型时，计算的是比较和交换的次数。 使用辅助函数 less() 和 swap() 来进行比较和交换的操作，使得代码的可读性和可移植性更好。 ```java private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void swap(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } ``` ## 选择排序 选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
```java public class Selection { public static void sort(Comparable[] a) { int N = a.length; for (int i = 0; i < N; i++) { int min = i; for (int j = i + 1; j < N; j++) if (less(a[j], a[min])) min = j; swap(a, i, min); } } } ``` 选择排序需要 \~N2/2 次比较和 \~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。 ## 冒泡排序 通过从左到右不断交换相邻逆序的相邻元素，在一轮的交换之后，可以让未排序的元素上浮到最右侧，是的右侧是已排序的。 在一轮交换中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。 ```java public class Bubble { public static void sort(Comparable[] a) { int N = a.length; boolean hasSorted = false; for (int i = 0; i < N && !hasSorted; i++) { hasSorted = true; for (int j = 0; j < N - i - 1; j++) { if (less(a[j + 1], a[j])) { hasSorted = false; swap(a, j, j + 1); } } } } } ``` ## 插入排序 插入排序从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左部数组依然有序。 第 j 元素是通过不断向左比较并交换来实现插入过程：当第 j 元素小于第 j - 1 元素，就将它们的位置交换，然后令 j 指针向左移动一个位置，不断进行以上操作。
```java public class Insertion { public static void sort(Comparable[] a) { int N = a.length; for (int i = 1; i < N; i++) for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) swap(a, j, j - 1); } } ``` 对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。 插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。 - 平均情况下插入排序需要 \~N2/4 比较以及 \~N2/4 次交换； - 最坏的情况下需要 \~N2/2 比较以及 \~N2/2 次交换，最坏的情况是数组是倒序的； - 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。 ## 希尔排序 对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。 希尔排序的出现就是为了改进插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。 希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
```java public class Shell { public static void sort(Comparable[] a) { int N = a.length; int h = 1; while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, ... while (h >= 1) { for (int i = h; i < N; i++) for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) swap(a, j, j - h); h = h / 3; } } } ``` 希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。 ## 归并排序 归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
### 1. 归并方法 归并方法将数组中两个已经排序的部分归并成一个。 ```java public class MergeSort { private static Comparable[] aux; private static void merge(Comparable[] a, int l, int m, int h) { int i = l, j = m + 1; for (int k = l; k <= h; k++) aux[k] = a[k]; // 将数据复制到辅助数组 for (int k = l; k <= h; k++) { if (i > m) a[k] = aux[j++]; else if (j > h) a[k] = aux[i++]; else if (aux[i].compareTo(a[j]) <= 0) a[k] = aux[i++]; // 先进行这一步，保证稳定性 else a[k] = aux[j++]; } } } ``` ### 2. 自顶向下归并排序
```java public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int l, int h) { if (h <= l) return; int mid = l + (h - l) / 2; sort(a, l, mid); sort(a, mid + 1, h); merge(a, l, mid, h); } ``` 因为每次都将问题对半分成两个子问题，而这种对半分的算法复杂度一般为 O(NlogN)，因此该归并排序方法的时间复杂度也为 O(NlogN)。 ### 3. 自底向上归并排序 先归并那些微型数组，然后成对归并得到的微型数组。 ```java public static void sort(Comparable[] a) { int N = a.length; aux = new Comparable[N]; for (int sz = 1; sz < N; sz += sz) { for (int lo = 0; lo < N - sz; lo += sz + sz) { merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1)); } } } ``` ## 快速排序 ### 1. 基本算法 - 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序； - 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
```java public class QuickSort { public static void sort(Comparable[] a) { shuffle(a); sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int l, int h) { if (h <= l) return; int j = partition(a, l, h); sort(a, l, j - 1); sort(a, j + 1, h); } private static void shuffle(Comparable[] array) { List
```java private static int partition(Comparable[] a, int l, int h) { int i = l, j = h + 1; Comparable v = a[l]; while (true) { while (less(a[++i], v) && i != h) ; while (less(v, a[--j]) && j != l) ; if (i >= j) break; swap(a, i, j); } swap(a, l, j); return j; } ``` ### 3. 性能分析 快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。 快速排序最好的情况下是每次都正好能将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。 最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。 ### 4. 算法改进 （一）切换到插入排序 因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。 （二）三数取中 最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。人们发现取 3 个元素并将大小居中的元素作为切分元素的效果最好。 （三）三向切分 对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。 三向切分快速排序对于只有若干不同主键的随机数组可以在线性时间内完成排序。 ```java public class Quick3Way { public static void sort(Comparable[] a) { sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int l, int h) { if (h <= l) return; int lt = l, i = l + 1, gt = h; Comparable v = a[l]; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) swap(a, lt++, i++); else if (cmp > 0) swap(a, i, gt--); else i++; } sort(a, l, lt - 1); sort(a, gt + 1, h); } } ``` ### 5. 基于切分的快速选择算法 快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。 可以利用这个特性找出数组的第 k 个元素。 ```java public static Comparable select(Comparable[] a, int k) { int l = 0, h = a.length - 1; while (h > l) { int j = partition(a, l, h); if (j == k) return a[k]; else if (j > k) h = j - 1; else l = j + 1; } return a[k]; } ``` 该算法是线性级别的，因为每次正好将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。 ## 堆排序 ### 1. 堆 堆的某个节点的值总是大于等于子节点的值，并且堆是一颗完全二叉树。 堆可以用数组来表示，因为堆是一种完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。
```java public class Heap { private Comparable[] heap; private int N = 0; public Heap(int maxN) { heap = new Comparable[maxN + 1]; N = maxN; } public boolean isEmpty() { return N == 0; } public int size() { return N; } private boolean less(int i, int j) { return heap[i].compareTo(heap[j]) < 0; } private void swap(int i, int j) { Comparable t = heap[i]; heap[i] = heap[j]; heap[j] = t; } } ``` ### 2. 上浮和下沉 在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。
```java private void swim(int k) { while (k > 1 && less(k / 2, k)) { swap(k / 2, k); k = k / 2; } } ``` 类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点有两个子节点，应当与两个子节点中最大那么节点进行交换。
```java private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) j++; if (!less(k, j)) break; swap(k, j); k = j; } } ``` ### 3. 插入元素 将新元素放到数组末尾，然后上浮到合适的位置。 ```java public void insert(Comparable v) { heap[++N] = v; swim(N); } ``` ### 4. 删除最大元素 从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。 ```java public Comparable delMax() { Comparable max = heap[1]; swap(1, N--); heap[N + 1] = null; sink(1); return max; } ``` ### 5. 堆排序 由于堆可以很容易得到最大的元素并删除它，不断地进行这种操作可以得到一个递减序列。如果把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列。因此很容易使用堆来进行排序，并且堆排序是原地排序，不占用额外空间。 （一）构建堆 无序数组建立堆最直接的方法是从左到右遍历数组，然后进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，因此可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。
（二）交换堆顶元素与最后一个元素 交换之后需要进行下沉操作维持堆的有序状态。
```java public class HeapSort { public static void sort(Comparable[] a) { // 数组第 0 个位置不能有元素 int N = a.length - 1; for (int k = N / 2; k >= 0; k--) sink(a, k, N); while (N > 1) { swap(a, 1, N--); sink(a, 1, N); } } private static void sink(Comparable[] a, int k, int N) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(a, j, j + 1)) j++; if (!less(a, k, j)) break; swap(a, k, j); k = j; } } } ``` ### 6. 分析 一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。 对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。 堆排序时一种原地排序，没有利用额外的空间。 现代操作系统很少使用堆排序，因为它无法利用缓存，也就是数组元素很少和相邻的元素进行比较。 ## 桶排序 ## 基数排序 ## 外部排序 ## 排序算法的比较 | 算法 | 稳定 | 原地排序 | 时间复杂度 | 空间复杂度 | 备注 | | :---: | :---: | :---: | :---: | :---: | :---: | | 选择排序 | no | yes | N2 | 1 | | | 插入排序 | yes | yes | N \~ N2 | 1 | 时间复杂度和初始顺序有关 | | 希尔排序 | no | yes | N 的若干倍乘于递增序列的长度 | 1 | | | 快速排序 | no | yes | NlogN | logN | | | 三向切分快速排序 | no | yes | N \~ NlogN | logN | 适用于有大量重复主键| | 归并排序 | yes | no | NlogN | N | | | 堆排序 | no | yes | NlogN | 1 | | | 快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 \~cNlogN，这里的 c 比其他线性对数级别的排序算法都要小。使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。 ## Java 的排序算法实现 Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。 # 六、查找 符号表是一种存储键值对的数据结构，主要支持两种操作：插入一个新的键值对、根据给定键得到值。 符号表分为有序和无序两种，有序符号表主要指支持 min()、max() 等根据键的大小关系来实现的操作。 有序符号表的键需要实现 Comparable 接口。 ## 二分查找实现有序符号表 使用一对平行数组，一个存储键一个存储值。 rank() 方法至关重要，当键在表中时，它能够知道该键的位置；当键不在表中时，它也能知道在何处插入新键。 复杂度：二分查找最多需要 logN+1 次比较，使用二分查找实现的符号表的查找操作所需要的时间最多是对数级别的。但是插入操作需要移动数组元素，是线性级别的。 ```java public class BinarySearchST
**二叉查找树** （BST）是一颗二叉树，并且每个节点的值都大于等于其左子树中的所有节点的值而小于等于右子树的所有节点的值。
BST 有一个重要性质，就是它的中序遍历结果递增排序。
基本数据结构： ```java public class BST
```java public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); if (cmp == 0) x.val = val; else if (cmp < 0) x.left = put(x.left, key, val); else x.right = put(x.right, key, val); x.N = size(x.left) + size(x.right) + 1; return x; } ``` ### 3. 分析 二叉查找树的算法运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。最好的情况下树是完全平衡的，每条空链接和根节点的距离都为 logN。
在最坏的情况下，树的高度为 N。
### 4. floor() floor(key)：小于等于键的最大键 - 如果键小于根节点的键，那么 floor(key) 一定在左子树中； - 如果键大于根节点的键，需要先判断右子树中是否存在 floor(key)，如果存在就找到，否则根节点就是 floor(key)。 ```java public Key floor(Key key) { Node x = floor(root, key); if (x == null) return null; return x.key; } private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp < 0) return floor(x.left, key); Node t = floor(x.right, key); if (t != null) { return t; } else { return x; } } ``` ### 5. rank() rank(key) 返回 key 的排名。 - 如果键和根节点的键相等，返回左子树的节点数； - 如果小于，递归计算在左子树中的排名； - 如果大于，递归计算在右子树中的排名，并加上左子树的节点数，再加上 1（根节点）。 ```java public int rank(Key key) { return rank(key, root); } private int rank(Key key, Node x) { if (x == null) return 0; int cmp = key.compareTo(x.key); if (cmp == 0) return size(x.left); else if (cmp < 0) return rank(key, x.left); else return 1 + size(x.left) + rank(key, x.right); } ``` ### 6. min() ```java private Node min(Node x) { if (x == null) return null; if (x.left == null) return x; return min(x.left); } ``` ### 7. deleteMin() 令指向最小节点的链接指向最小节点的右子树。
```java public void deleteMin() { root = deleteMin(root); } public Node deleteMin(Node x) { if (x.left == null) return x.right; x.left = deleteMin(x.left); x.N = size(x.left) + size(x.right) + 1; return x; } ``` ### 8. delete() - 如果待删除的节点只有一个子树，那么只需要让指向待删除节点的链接指向唯一的子树即可； - 否则，让右子树的最小节点替换该节点。
```java public void delete(Key key) { root = delete(root, key); } private Node delete(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) x.left = delete(x.left, key); else if (cmp > 0) x.right = delete(x.right, key); else { if (x.right == null) return x.left; if (x.left == null) return x.right; Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; } ``` ### 9. keys() 利用二叉查找树中序遍历的结果为递增的特点。 ```java public Iterable
2-3 查找树引入了 2- 节点和 3- 节点，目的是为了让树平衡。一颗完美平衡的 2-3 查找树的所有空链接到根节点的距离应该是相同的。 ### 1. 插入操作 插入操作和 BST 的插入操作有很大区别，BST 的插入操作是先进行一次未命中的查找，然后再将节点插入到对应的空链接上。但是 2-3 查找树如果也这么做的话，那么就会破坏了平衡性。它是将新节点插入到叶子节点上。 根据叶子节点的类型不同，有不同的处理方式。 插入到 2- 节点上，那么直接将新节点和原来的节点组成 3- 节点即可。
如果是插入到 3- 节点上，就会产生一个临时 4- 节点时，需要将 4- 节点分裂成 3 个 2- 节点，并将中间的 2- 节点移到上层节点中。如果上移操作继续产生临时 4- 节点则一直进行分裂上移，直到不存在临时 4- 节点。
### 2. 性质 2-3 查找树插入操作的变换都是局部的，除了相关的节点和链接之外不必修改或者检查树的其它部分，而这些局部变换不会影响树的全局有序性和平衡性。 2-3 查找树的查找和插入操作复杂度和插入顺序无关，在最坏的情况下查找和插入操作访问的节点必然不超过 logN 个，含有 10 亿个节点的 2-3 查找树最多只需要访问 30 个节点就能进行任意的查找和插入操作。 ## 红黑二叉查找树 2-3 查找树需要用到 2- 节点和 3- 节点，红黑树使用红链接来实现 3- 节点。指向一个节点的链接颜色如果为红色，那么这个节点和上层节点表示的是一个 3- 节点，而黑色则是普通链接。
红黑树具有以下性质： 1. 红链接都为左链接； 2. 完美黑色平衡，即任意空链接到根节点的路径上的黑链接数量相同。 画红黑树时可以将红链接画平。
```java public class RedBlackBST
```java public Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; } ``` ### 2. 右旋转 进行右旋转是为了转换两个连续的左红链接，这会在之后的插入过程中探讨。
```java public Node rotateRight(Node h) { Node x = h.left; h.left = x.right; x.color = h.color; h.color = RED; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; } ``` ### 3. 颜色转换 一个 4- 节点在红黑树中表现为一个节点的左右子节点都是红色的。分裂 4- 节点除了需要将子节点的颜色由红变黑之外，同时需要将父节点的颜色由黑变红，从 2-3 树的角度看就是将中间节点移到上层节点。
```java void flipColors(Node h){ h.color = RED; h.left.color = BLACK; h.right.color = BLACK; } ``` ### 4. 插入 先将一个节点按二叉查找树的方法插入到正确位置，然后再进行如下颜色操作： - 如果右子节点是红色的而左子节点是黑色的，进行左旋转； - 如果左子节点是红色的，而且左子节点的左子节点也是红色的，进行右旋转； - 如果左右子节点均为红色的，进行颜色转换。
```java public void put(Key key, Value val) { root = put(root, key, val); root.color = BLACK; } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val, 1, RED); int cmp = key.compareTo(x.key); if (cmp == 0) x.val = val; else if (cmp < 0) x.left = put(x.left, key, val); else x.right = put(x.right, key, val); if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x); if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x); if (isRed(x.left) && isRed(x.right)) flipColors(x); x.N = size(x.left) + size(x.right) + 1; return x; } ``` 可以看到该插入操作和二叉查找树的插入操作类似，只是在最后加入了旋转和颜色变换操作即可。 根节点一定为黑色，因为根节点没有上层节点，也就没有上层节点的左链接指向根节点。flipColors() 有可能会使得根节点的颜色变为红色，每当根节点由红色变成黑色时树的黑链接高度加 1. ### 5. 分析 一颗大小为 N 的红黑树的高度不会超过 2logN。最坏的情况下是它所对应的 2-3 树，构成最左边的路径节点全部都是 3- 节点而其余都是 2- 节点。 红黑树大多数的操作所需要的时间都是对数级别的。 ## 散列表 散列表类似于数组，可以把散列表的散列值看成数组的索引值。访问散列表和访问数组元素一样快速，它可以在常数时间内实现查找和插入操作。 由于无法通过散列值知道键的大小关系，因此散列表无法实现有序性操作。 ### 1. 散列函数 对于一个大小为 M 的散列表，散列函数能够把任意键转换为 [0, M-1] 内的正整数，该正整数即为 hash 值。 散列表有冲突的存在，也就是两个不同的键可能有相同的 hash 值。 散列函数应该满足以下三个条件： 1. 一致性：相等的键应当有相等的 hash 值，两个键相等表示调用 equals() 返回的值相等。 2. 高效性：计算应当简便，有必要的话可以把 hash 值缓存起来，在调用 hash 函数时直接返回。 3. 均匀性：所有键的 hash 值应当均匀地分布到 [0, M-1] 之间，这个条件至关重要，直接影响到散列表的性能。 除留余数法可以将整数散列到 [0, M-1] 之间，例如一个正整数 k，计算 k%M 既可得到一个 [0, M-1] 之间的 hash 值。注意 M 必须是一个素数，否则无法利用键包含的所有信息。例如 M 为 10k，那么只能利用键的后 k 位。 对于其它数，可以将其转换成整数的形式，然后利用除留余数法。例如对于浮点数，可以将其表示成二进制形式，然后使用二进制形式的整数值进行除留余数法。 对于有多部分组合的键，每部分都需要计算 hash 值，并且最后合并时需要让每部分 hash 值都具有同等重要的地位。可以将该键看成 R 进制的整数，键中每部分都具有不同的权值。 例如，字符串的散列函数实现如下 ```java int hash = 0; for(int i = 0; i < s.length(); i++) hash = (R * hash + s.charAt(i)) % M; ``` 再比如，拥有多个成员的自定义类的哈希函数如下： ```java int hash = (((day * R + month) % M) * R + year) % M; ``` R 通常取 31。 Java 中的 hashCode() 实现了 hash 函数，但是默认使用对象的内存地址值。在使用 hashCode() 函数时，应当结合除留余数法来使用。因为内存地址是 32 位整数，我们只需要 31 位的非负整数，因此应当屏蔽符号位之后再使用除留余数法。 ```java int hash = (x.hashCode() & 0x7fffffff) % M; ``` 使用 Java 自带的 HashMap 等自带的哈希表实现时，只需要去实现 Key 类型的 hashCode() 函数即可。Java 规定 hashCode() 能够将键均匀分布于所有的 32 位整数，Java 中的 String、Integer 等对象的 hashCode() 都能实现这一点。以下展示了自定义类型如何实现 hashCode()。 ```java public class Transaction{ private final String who; private final Date when; private final double amount; public int hashCode(){ int hash = 17; hash = 31 * hash + who.hashCode(); hash = 31 * hash + when.hashCode(); hash = 31 * hash + ((Double) amount).hashCode(); return hash; } } ``` ### 2. 基于拉链法的散列表 拉链法使用链表来存储 hash 值相同的键，从而解决冲突。此时查找需要分两步，首先查找 Key 所在的链表，然后在链表中顺序查找。
对于 N 个键，M 条链表 (N>M)，如果哈希函数能够满足均匀性的条件，每条链表的大小趋向于 N/M，因此未命中的查找和插入操作所需要的比较次数为 \~N/M。 ### 3. 基于线性探测法的散列表 线性探测法使用空位来解决冲突，当冲突发生时，向前探测一个空位来存储冲突的键。使用线性探测法，数组的大小 M 应当大于键的个数 N（M>N)。
```java public class LinearProbingHashST
α = N/M，把 α 称为利用率。理论证明，当 α 小于 1/2 时探测的预计次数只在 1.5 到 2.5 之间。 为了保证散列表的性能，应当调整数组的大小，使得 α 在 [1/4, 1/2] 之间。 ```java private void resize() { if (N >= M / 2) resize(2 * M); else if (N <= M / 8) resize(M / 2); } private void resize(int cap) { LinearProbingHashST