白话数据结构系列文章目录

基本概念篇
1. 入门概述
2. 复杂度
3. 数组&链表
4. 栈&堆
5. 排序算法
6. 查找算法

编程思想篇

实际问题篇
1. 约瑟夫环

---

一、前言

本节介绍下最基础的查找算法，以及一些用于查找的数据结构，例如跳表与hash表。

---

二、前置条件

C语言基础

---

三、本文参考资料

《大话数据结构》
《数据结构与算法之美》
百度

---

四、正文部分

4.1 二分查找

4.1.1 概念

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn)

利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。
其中，low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标。

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。
每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

4.1.1.1 时间复杂度O(logn)

假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

可以看出来，这是一个等比数列。其中 n/2^k=1 时，k 的值就是总共缩小的次数。
而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。
通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

O(logn)是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。
即便 n 非常非常大，对应的 logn 也很小。比如 n 等于 2 的 32 次方，这个数很大了吧？大约是 42 亿。
也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。

用大 O 标记法表示时间复杂度的时候，会省略掉常数、系数和低阶。
对于常量级时间复杂度的算法来说，O(1) 有可能表示的是一个非常大的常量值，比如 O(1000)、O(10000)。
所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。

4.1.1.2 局限性

• 首先，二分查找依赖的是顺序表结构，简单点说就是数组。
  二分查找算法需要按照下标随机访问元素。
  数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。
  所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。

• 二分查找针对的是有序数据。
  如果数据没有序，我们需要先排序。
  排序的时间复杂度最低是 O(nlogn)。
  所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找。
  这样排序的成本可被均摊，二分查找的边际成本就会比较低。
  二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
  针对动态变化的数据集合，二分查找将不再适用。

• 数据量太小不适合二分查找。
  如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。
  只有数据量比较大的时候，二分查找的优势才会比较明显。
  不过，这里有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，我都推荐使用二分查找。
  比如，数组中存储的都是长度超过 300 的字符串，如此长的两个字符串之间比对大小，就会非常耗时。
  我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。

• 数据量太大也不适合二分查找
  二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。
  比如，我们有 1GB 大小的数据，如果希望用数组来存储，那就需要 1GB 的连续内存空间。
  注意这里的“连续”二字，也就是说，即便有 2GB 的内存空间剩余，但是如果这剩余的 2GB 内存空间都是零散的，没有连续的 1GB 大小的内存空间，那照样无法申请一个 1GB 大小的数组。
  而我们的二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。

4.1.2 简单情况

4.1.2.1 简单的非递归实现

最简单的情况就是有序数组中不存在重复元素，我们在其中用二分查找值等于给定值的数据。

```
public int bsearch(int[] a, int n, int value)
{
	int low = 0;
	int high = n - 1;

	while (low <= high) {
		int mid = (low + high) / 2;
		if (a[mid] == value) {
			return mid;
		} else if (a[mid] < value) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}

	return -1;
}
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

易错点：

• 循环退出条件
  注意是 low<=high，而不是 low
• mid 的取值
  实际上，mid=(low+high)/2 这种写法是有问题的。
  因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。
  改进的方法是将 mid 的计算方式写成 low+(high-low)/2。
  更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。
  因为相比除法运算来说，计算机处理位运算要快得多。
• low 和 high 的更新
  low=mid+1，high=mid-1。
  注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。
  比如，当 high=3，low=3 时，如果 a[3]不等于 value，就会导致一直循环不退出。

4.1.2.2 简单的递归实现

// 二分查找的递归实现
public int bsearch(int[] a, int n, int val)
{
	return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value)
{
	if (low > high) return -1;

	int mid =  low + ((high - low) >> 1);
	if (a[mid] == value) {
		return mid;
	} else if (a[mid] < value) {
		return bsearchInternally(a, mid+1, high, value);
	} else {
		return bsearchInternally(a, low, mid-1, value);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.1.3 变体问题

#include <stdio.h>

#define DATA_SUM 10

/* 从大到小且不重复，所以代码需要逆序 */
int data_simple[DATA_SUM] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

/* 从大到小但不重复 */
int data_repeat[DATA_SUM] = {10, 10, 8, 7, 5, 5, 4, 3, 1, 1};

int binary_search_simple(int *data, int value, int len)
{
    int space, low, high, mid, found_flag;
    
    found_flag = 0;
    high = len - 1;
    low = 0;

    while (low <= high) {
        mid = (low + high) / 2;
        if (value < data[mid]) {
            low = mid + 1;  //需加1，否则会产生死循环
        } else if (value > data[mid]) {
            high = mid - 1; //需加1，否则会产生死循环
        } else if (value == data[mid]) {
            space = mid;
            found_flag = 1;
            break;
        }
    }

    if (found_flag == 1) {
        return space + 1;
    } else {
        return -1;
    }
}

int binary_search_repeat_first(int *data, int value, int len)
{
    int space, low, high, mid, found_flag;
    
    found_flag = 0;
    high = len - 1;
    low = 0;

    while (low <= high) {
        mid = (low + high) / 2;
        if (value < data[mid]) {
            low = mid + 1;  //需加1，否则会产生死循环
        } else if (value > data[mid]) {
            high = mid - 1; //需加1，否则会产生死循环
        } else if (value = data[mid]) {
            if ((mid == 0) || (data[mid - 1] != value)) {
                space = mid;
                found_flag = 1;
                break;
            } else if (data[mid - 1] == value) {
                high = mid - 1;
            }
        }
    }

    if (found_flag == 1) {
        return space + 1;
    } else {
        return -1;
    }
}

int binary_search_repeat_last(int *data, int value, int len)
{
    int space, low, high, mid, found_flag;
    
    found_flag = 0;
    high = len - 1;
    low = 0;

    while (low <= high) {
        mid = (low + high) / 2;
        if (value < data[mid]) {
            low = mid + 1;  //需加1，否则会产生死循环
        } else if (value > data[mid]) {
            high = mid - 1; //需加1，否则会产生死循环
        } else if (value = data[mid]) {
            if ((mid == len - 1) || (data[mid + 1] != value)) {
                space = mid;
                found_flag = 1;
                break;
            } else if (data[mid + 1] == value) {
                low = mid + 1;
            }
        }
    }

    if (found_flag == 1) {
        return space + 1;
    } else {
        return -1;
    }
}

int binary_search_repeat_last_large(int *data, int value, int len)
{
    int space, low, high, mid, found_flag;
    
    found_flag = 0;
    high = len - 1;
    low = 0;

    while (low <= high) {
        mid = (low + high) / 2;
        if (value > data[mid]) {
            high = mid - 1;  //入参是从大到小的数组，需要逆序查找
        } else if (value <= data[mid]) {
            if ((mid == len - 1) || (value > data[mid + 1])) {
                space = mid;
                found_flag = 1;
                break;
            } else if (value <= data[mid + 1]) {
                high = mid - 1;
            }
        }
    }

    if (found_flag == 1) {
        return space + 1;
    } else {
        return -1;
    }
    
}

int binary_search_repeat_first_small(int *data, int value, int len)
{
    int space, low, high, mid, found_flag;
    
    found_flag = 0;
    high = len - 1;
    low = 0;

    while (low <= high) {
        mid = (low + high) / 2;
        if (value < data[mid]) {
            low = mid + 1;  //入参是从大到小的数组，需要逆序查找
        } else if (value >= data[mid]) {
            if ((mid == 0) || (value < data[mid - 1])) {
                space = mid;
                found_flag = 1;
                break;
            } else if (value >= data[mid - 1]) {
                high = mid - 1;
                
            }
        }
    }

    if (found_flag == 1) {
        return space + 1;
    } else {
        return -1;
    }
    
}

int main()
{
    int space, value;

    printf("input search value:");
    scanf("%d", &value);

    space = binary_search_simple(data_simple, value, DATA_SUM);
    printf("%d 的位置在 %d\n", value, space);

    space = binary_search_repeat_first(data_repeat, value, DATA_SUM);
    printf("第一个 %d 的位置是 %d\n", value, space);

    space = binary_search_repeat_last(data_repeat, value, DATA_SUM);
    printf("最后一个 %d 的位置是 %d\n", value, space);

    space = binary_search_repeat_last_large(data_repeat, value, DATA_SUM);
    printf("最后一个大于等于 %d 的位置是 %d\n", value, space);

    space = binary_search_repeat_first_small(data_repeat, value, DATA_SUM);
    printf("第一个小于等于 %d 的位置是 %d\n", value, space);

    return 0;
}

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

 

4.2 跳表

Redis 中的有序集合（Sorted Set）就是用跳表来实现的。

4.2.1 概念

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。
这样查找效率就会很低，时间复杂度会很高，是 O(n)。

那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，每两个结点提取一个结点到上一级，我们把抽出来的那一级叫做索引或索引层。
图中的 down 表示 down 指针，指向下一级结点。

如果我们现在要查找某个结点，比如 16。
我们可以先在索引层遍历，当遍历到索引层中值为 13 的结点时，我们发现下一个结点是 17，那要查找的结点 16 肯定就在这两个结点之间。
然后我们通过索引层结点的 down 指针，下降到原始链表这一层，继续遍历。
这个时候，我们只需要再遍历 2 个结点（13 / 16），就可以找到值等于 16 的这个结点了。
这样，原来如果要查找 16，需要遍历 10 个结点，现在只需要遍历 7 个结点（1 / 4 / 7 / 9 / 13 / 13 / 16）。

从这个例子里，我们看出，加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。
那如果我们再加一级索引呢？效率会不会提升更多呢？
跟前面建立第一级索引的方式相似，我们在第一级索引的基础之上，每两个结点就抽出一个结点到第二级索引。
现在我们再来查找 16，只需要遍历 6 个结点了（1 / 7 / 13 / 13 / 13 / 16），需要遍历的结点数量又减少了。

从图中我们可以看出，原来没有索引的时候，查找 62 需要遍历 62 个结点，现在只需要遍历 11 个结点，速度是不是提高了很多？
所以，当链表的长度 n 比较大时，比如 1000、10000 的时候，在构建索引之后，查找效率的提升就会非常明显。

前面讲的这种链表加多级索引的结构，就是跳表。
我通过例子给你展示了跳表是如何减少查询次数的，现在你应该比较清晰地知道，跳表确实是可以提高查询效率的。

4.2.2 时间复杂度

在一个单链表中查询某个数据的时间复杂度是 O(n)。
我把问题分解一下，先来看这样一个问题，如果链表里有 n 个结点，会有多少级索引呢？

每两个结点会抽出一个结点作为上一级索引的结点，
那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，
依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2^k)。

假设索引有 h 级，最高级的索引有 2 个结点。
通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log2n-1。
如果包含原始链表这一层，整个跳表的高度就是 log2n。
我们在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。

按照前面这种索引结构，我们每一级索引都最多只需要遍历 3 个结点，也就是说 m=3
假设我们要查找的数据是 x，在第 k 级索引中，我们遍历到 y 结点之后，发现 x 大于 y，小于后面的结点 z，
所以我们通过 y 的 down 指针，从第 k 级索引下降到第 k-1 级索引。
在第 k-1 级索引中，y 和 z 之间只有 3 个结点（包含 y 和 z），
所以，我们在 K-1 级索引中最多只需要遍历 3 个结点，依次类推，每一级索引都最多只需要遍历 3 个结点。

通过上面的分析，我们得到 m=3，所以在跳表中查询任意数据的时间复杂度就是 O(logn)。
这个查找的时间复杂度跟二分查找是一样的。

4.2.3 空间复杂度

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。
假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。
如果我们把每层索引的结点数写出来，就是一个等比数列。

这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。
所以，跳表的空间复杂度是 O(n)。
也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。

我们前面都是每两个结点抽一个结点到上级索引，如果我们每三个结点或五个结点，抽一个结点到上级索引，是不是就不用那么多索引结点了呢？
我画了一个每三个结点抽一个的示意图，你可以看下。

从图中可以看出，第一级索引需要大约 n/3 个结点，第二级索引需要大约 n/9 个结点。
每往上一级，索引结点个数都除以 3。
为了方便计算，我们假设最高一级的索引结点个数是 1。
我们把每级索引的结点个数都写下来，也是一个等比数列。

通过等比数列求和公式，总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=n/2。
尽管空间复杂度还是 O(n)，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。

实际上，在软件开发中，我们不必太在意索引占用的额外空间。
在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，
但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，

所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

4.2.4 动态插入和删除

插入、删除操作的时间复杂度也是 O(logn)。

在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是 O(1)。
但是，这里为了保证原始链表中数据的有序性，我们需要先找到要插入的位置，这个查找操作就会比较耗时。

对于跳表来说，我们讲过查找某个结点的时间复杂度是 O(logn)，所以这里查找某个数据应该插入的位置，方法也是类似的，时间复杂度也是 O(logn)。

如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。
因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。
所以在查找要删除的结点的时候，一定要获取前驱结点。

当然，如果我们用的是双向链表，就不需要考虑这个问题了。

4.2.5 跳表索引动态更新

当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。
极端情况下，跳表还会退化成单链表。

作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，
也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

跳表是通过随机函数来维护前面提到的“平衡性”。

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。

我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。

4.2.6 Redis 要用跳表来实现有序集合的原因

Redis 中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。

Redis 中的有序集合支持的核心操作主要有下面这几个：

• 插入一个数据；
• 删除一个数据；
• 查找一个数据；
• 按照区间查找数据（比如查找值在[100, 356]之间的数据）；
• 迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。
但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。

跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

我们做业务开发的时候，直接拿来用就可以了，不用费劲自己去实现一个红黑树，但是跳表并没有一个现成的实现，所以在开发中，如果你想使用跳表，必须要自己实现。

 

4.3 hash表

4.3.1 散列思想

散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

在这个例子里，参赛编号是自然数，并且与数组的下标形成一一映射，
所以利用数组支持根据下标随机访问的时候，时间复杂度是 O(1) 这一特性，就可以实现快速查找编号对应的选手信息。

用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位还是原来的编号 1 到 89。–> 1-89号人可以是任意年级班级
思路还是跟前面类似。尽管我们不能直接把编号作为数组下标，但我们可以截取参赛编号的后两位作为数组下标，来存取选手信息数据。
当通过参赛编号查询选手信息的时候，我们用同样的方法，取参赛编号的后两位，作为数组下标，来读取数组中的数据。

这就是典型的散列思想。
其中，参赛选手的编号我们叫做键（key）或者关键字。我们用它来标识一个选手。
我们把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）。

通过这个例子，我们可以总结出这样的规律：

• 散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。
• 我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。
• 当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

4.3.2 散列函数

散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
那第一个例子中，编号就是数组下标，所以 hash(key) 就等于 key。改造后的例子，写成散列函数稍微有点复杂。我用伪代码将它写成函数就是下面这样：

int hash(String key) {
	// 获取后两位字符
	string lastTwoChars = key.substr(length-2, length);
	// 将后两位字符转换为整数
	int hashValue = convert lastTwoChas to int-type;
	return hashValue;
}
1
2
3
4
5
6
7

但是，如果参赛选手的编号是随机生成的 6 位数字，又或者用的是 a 到 z 之间的字符串，该如何构造散列函数呢？
我总结了三点散列函数设计的基本要求：

• 散列函数计算得到的散列值是一个非负整数； --> 因为是下标，故不能为负数
• 如果 key1 = key2，那 hash(key1) == hash(key2)；
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

第三点这个要求看起来合情合理，但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。（即不同的key对应了相同的hash值）
即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。
而且，因为数组的存储空间有限，也会加大散列冲突的概率。

所以我们几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，我们需要通过其他途径来解决。

4.3.3 散列冲突

4.3.3.1 开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。
那如何重新探测新的位置呢？

1. 线性探测（Linear Probing）
   当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
   这里面黄色的色块表示空闲位置，橙色的色块表示已经存储了数据。
   

   从图中可以看出，散列表的大小为 10，在元素 x 插入散列表之前，已经 6 个元素插入到散列表中。
   x 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。
   于是我们就顺序地往后一个一个找，看有没有空闲的位置，遍历到尾部都没有找到空闲的位置，于是我们再从表头开始找，直到找到空闲位置 2，于是将其插入到这个位置。

   在散列表中查找元素的过程有点儿类似插入过程。
   我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。（先查散列值，再对比key是否相同）
   如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。
   如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
   
   对于使用线性探测法解决冲突的散列表，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。
   如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。（查找到的位置被删除后置空，则会被认为是不存在该hash值）
   我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
   

   当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。
   极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。
   同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。

2. 二次探测
   二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……
   而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……

3. 双重散列
   不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……
   我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。
为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。（不能因为空闲位置太少而导致效率降低）
我们用装载因子（load factor）来表示空位的多少。
装载因子的计算公式是：

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
1

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

4.3.3.2 链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。
在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。
当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
实际上，这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。

对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

4.3.4 如何设计一个hash表

4.3.4.1 查询效率

散列表的查询效率并不能笼统地说成是 O(1)
它跟散列函数、装载因子、散列冲突等都有关系。
如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。
所有的数据经过散列函数之后，都散列到同一个槽里。那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。
如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。
这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。
这也就是散列表碰撞攻击的基本原理。

4.3.4.2 如何设计散列函数？

散列函数设计的好坏，决定了散列表冲突的概率大小，也直接决定了散列表的性能。

• 散列函数的设计不能太复杂。
  过于复杂的散列函数，势必会消耗很多计算时间，也就间接地影响到散列表的性能。
• 散列函数生成的值要尽可能随机并且均匀分布
  这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。

4.3.4.3 装载因子过大了怎么办？

装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。
不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

对于动态散列表来说，数据集合是频繁变动的，我们事先无法预估将要加入的数据个数，所以我们也无法事先申请一个足够大的散列表。
随着数据慢慢加入，装载因子就会慢慢变大。当装载因子大到一定程度之后，散列冲突就会变得不可接受。

针对散列表，当装载因子过大时，我们也可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中。
假设每次扩容我们都申请一个原来散列表大小两倍的空间。
如果原来散列表的装载因子是 0.8，那经过扩容之后，新散列表的装载因子就下降为原来的一半，变成了 0.4。

在原来的散列表中，21 这个元素原来存储在下标为 0 的位置，搬移到新的散列表中，存储在下标为 7 的位置。

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。
最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。
用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。
扩容搬运原数据的时间复杂度是O(n)，扩容之后的第一次插入还是O(1)，但是扩完容之后到需要扩容之前的插入都为O(1)，所以均摊下来还是O(1)

实际上，对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。
如果我们对空间消耗非常敏感，我们可以在装载因子小于某个值之后，启动动态缩容。
当然，如果我们更加在意执行效率，能够容忍多消耗一点内存空间，那就可以不用费劲来缩容了。

如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

装载因子阈值的设置要权衡时间、空间复杂度。
如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；
相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。

4.3.4.3 如何避免低效的扩容？

如果散列表当前大小为 1GB，要想扩容为原来的两倍大小，那就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表，听起来就很耗时
如果我们的业务代码直接服务于用户，尽管大部分情况下，插入一个数据的操作都很快，但是，极个别非常慢的插入操作，也会让用户崩溃。
这个时候，“一次性”扩容的机制就不合适了。

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。
当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。

当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。
每次插入一个数据到散列表，我们都重复上面的过程。
经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。
这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。
通过这样均摊的方法，将一次性扩容的代价，均摊到多次插入操作中，就避免了一次性扩容耗时过多的情况。
这种实现方式，任何情况下，插入一个数据的时间复杂度都是 O(1)。

4.3.4.3 如何选择冲突解决方法？

• 开放寻址法

1. 优点：
   开放寻址法不像链表法，需要拉很多链表。
   散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。
   而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。
2. 缺点：
   用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。
   而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。
   所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
3. 总结：
   当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

• 链表法

1. 优点：
   链表法对内存的利用率比开放寻址法要高。
   因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。
   对大装载因子的容忍度更高。
   开放寻址法只能适用装载因子小于 1 的情况。
   接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。
   但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

2. 缺点：
   链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。
   而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响。
   如果我们存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4 个字节或者 8 个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。

3. 优化：
   实际上，我们对链表法稍加改造，可以实现一个更加高效的散列表。
   那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。
   这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。
   这样也就有效避免了前面讲到的散列碰撞攻击。
   

4. 总结：
   基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表

4.3.5 hash算法

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

MD5 的哈希值是 128 位的 Bit 长度，为了方便表示，我把它们转化成了 16 进制编码

设计一个优秀的哈希算法的要求：

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
• 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

 

---

五、总结

 

---