高级数据结构

2023-12-03 12:47:10

1、跳表 Skip List

链表加多级索引的结构，称为跳表。

在原始链表的基础上，对链表建立一级“索引”，down指针，指向下一级结点。在多级索引的条件下，会极大提高查找效率。

时间复杂度为 O(logn)
空间复杂度为 O(n)：需要维护多层索引

其作为一种动态数据结构，在插入和删除操作中，需要维护索引和原始链表之间的平衡。跳表是通过随机函数生成值k，那么就将这个结点添加到第一级到第k级，这k级索引中。

2、散列表 Hash Table

1、散列思想

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

2、散列函数

基本要求：

散列函数计算得到的散列值是一个非负整数
如果 Key1 = Key2，那 hash(Key1) == hash(Key2)

如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)，很难找到一个不同key对应的散列值不同的，无法避免散列冲突。

3、散列冲突

1、开放寻址法

如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

寻找空闲位置的方法：

线性探测 Linear Probing

插入数据时，如果某个数据经过散列函数散列后，存储位置已经被占用，那么就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

查找数据时，通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。

删除操作时，为了避免通过线性探测的查找操作查找到空闲位置即停止，这里的删除，不能真正删除，可以特殊标记为 deleted。

二次探测 Quadratic Probing

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

双重散列

当对目标值执行散列函数后得到的值，该值的存储位置已经被占用，则使用第二个散列函数，依次类推，直到找到空闲的存储位置。

优点：

其数据都存储在数组中，可以有效利用CPU缓存加快查询速度，序列化更加简单。

缺点：

删除数据时，需要特殊标记已删除的数据。

因为数据都在一个数组中，冲突的代价更高。

2、链表法

是一种更常用的散列冲突解决办法，在散列表中，每个“桶”或“槽”对应一条链表，所有散列值相同的元素，放到相同槽位对应的链表中。

插入操作：通过散列函数计算对应散列槽位，将其插入到对应链表中，时间复杂度为O(1)
查找和删除操作：O(k)，k为链表长度

优点：

内存利用率相对较高，对大装载因子的容忍度更高

缺点：

要额外存储指针，比较消耗内存

链表节点为零散分布，对CPU缓存不友好，影响执行效率

4、装载因子 Load Factor

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

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

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

这里也要避免低效的扩容，当散列表很大时，一次性扩容是非常耗时的。

可以将扩容操作穿插在插入操作的过程中，分批完成。当有新数据插入时，将新数据插入到散列表中，并从老的散列表中拿出一个数据放到新散列表，以此类推。通过均摊的方法，使时间复杂度为O(1)。

5、工业级的散列表，java HashMap为例

1、初始大小

默认大小是16，如果可以预估数据量大小，通过修改该值，可以减少动态扩容次数，提高性能。

2、装载因子和动态扩容

最大装载因子默认是0.75，当元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

3、散列冲突解决办法

链表法

在JDK 1.8中，当链表长度太长（默认超过8）时，链表转换为红黑树。

4、散列函数

其设计并不复杂，最求简单高效、分布均匀。

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}

hashCode() 返回的是 Java 对象的 hash code

码农公寓