数据结构与算法笔记（二）
数据结构与算法笔记（二）
跳表
前面的数据结构笔记中分析过链表，如图所示：
由于它的内存空间非连续，因此查找某个元素时只能从头到尾遍历，时间复杂度为 O(n)。那么能不能提高链表的查找效率呢？
我们可以对链表进行改造，在链表上建立一级“索引”，如图：
这样，在查找的时候就可以先在索引层查找，然后再根据索引去查数据（有点类似数据库的索引）。
为了进一步提高查找效率，还可以建立二级索引，如图：
以此类推，还可以建立更多层级的索引：
这种数据结构称为跳表（Skip List）。这样做查找速度更快了，但同时也会耗费更多的存储空间，它的思想其实就是空间换时间。
应用场景：Redis 的有序集合。
散列表
散列表（Hash table），又称“哈希表”或“Hash 表”。利用的是数组支持按照下标访问数据（时间复杂度为 O(1)）的特性，是数组的一种扩展。示意图：
其中的 key 为可理解为要存入的数据的键（键-值对形式）；hash() 是「散列函数」，它根据 key 计算得到一个非负整数，是哈希表实现的一个关键点；table 为存放数据的数组。
散列表存入数据的大概流程是：将 key 经过散列函数计算得到一个值（保证在数组长度范围内）作为数组的下标，然后将 key 的值保存在数组下标对应的位置。
散列函数
散列函数设计的基本要求：
1. 散列函数计算得到的散列值是一个非负整数（数组下标从 0 开始的）；
2. 如果 key1 = key2，那么 hash(key1) = hash(key2)；
3. 如果 key1 ≠ key2，那么 hash(key1) ≠ hash(key2)。
此外，散列函数的设计不能太复杂（会消耗很多计算时间），而且生成的值要尽可能随机并且均匀分布（尽量最小化散列冲突）。
例如，JDK 1.8 中 HashMap 的散列函数设计如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}注： 真实情况下，不同 key 对应的散列值都不一样的散列函数几乎是不存在的。业界著名的 MD5、SHA、CRC 等哈希算法也无法避免这种散列冲突。
因此，需要其他途径来解决散列冲突的问题。
散列冲突
解决散列冲突常用的有两种方法：开放寻址法（open addressing）和链表法（chaining）。
1. 开放寻址法
核心思想：如果出现了散列冲突，就重新探测一个空闲位置将其插入。常用的探测方法有三种：
1.1 线性探测（Linear Probing）
往散列表中插入数据时，若某个数据经散列函数散列之后，存储位置已经被占用，就从当前位置开始依次往后查找，直到找到空闲位置插入。示意图：
缺点：散列表中的数据越来越多时，空闲位置越来越少，散列冲突的可能性会越来越大，线性探测的时间会越来越久。
1.2 二次探测（Quadratic Probing）
线性探测每次探测的步长是 1，二次探测的步长则为“二次方”。
1.3 双重散列（Double hashing）
使用一组散列函数，当 hash1(key) 冲突时再用 hash2(key)……直至找到空闲的位置。
装载因子计算公式：
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
2. 链表法
该方法更为常用。在散列表中，每个“桶（bucket）”或“槽（slot）”会对应一条链表，所有散列值相同的元素都会放到相同槽位对应的链表中，如图所示：
二者对比
1. 当数据量比较小、装载因子小的时候，适合采用开放寻址法（例如 Java 中的 ThreadLocalMap）。
2. 链表法比较适合存储大对象、大数据量的散列表；而且比开放寻址法更灵活、支持更多的优化策略（比如用红黑树替代链表，JDK 1.8 中 HashMap 的实现）。
PS: 由于链表要存储指针，当存储比较小的对象时内存消耗可能会翻倍；而存储大对象，即存储对象的大小远大于一个指针的大小（4 或 8 个字节）时，链表中指针的内存消耗可以忽略了。
小结
1. 跳表
跳表是在链表的基础上增加索引层来提高查找效率，但同时也增加了存储空间开销，利用“空间换时间”的思想。
常见应用场景：Redis 中的有序集合。
2. 散列表
两个核心问题：散列函数设计和散列冲突解决。
散列冲突常用的解决方法有两种：开放寻址法和链表法。
散列函数设计的好坏决定了散列冲突的概率，也决定了散列表的性能。
相关文章：
Stay hungry, stay foolish.