Netherspite

为链表加多级的索引结构就是跳表（Skip List），它是一种动态数据结构。散列表也称哈希表，用的是数组支持按下标随机访问数据的特性。

跳表

跳表的复杂度计算

  1. 时间复杂度

    假设链表中每两个结点抽出一个结点作为上一级的索引结点，那么第一级索引的结点个数大约是$n/2$，第二级索引的结点个数约是$n/4$，以此类推，直到最上级（假设为h级）的2个结点。第h级的结点有个数是$n/2^k$，可得$n/2^k=2$，求得$h=log_2n-1$。跳表的整体高度就是$log_2n$。跳表在查询过程中每一层只要最多遍历3个结点，查找的时间复杂度为$O(n)=O(3logn)=O(logn)$。

  2. 空间复杂度

    原始链表大小为$n$，第一级索引有$n/2$个结点，第k个有$n/2^k$个结点，顶层有2个结点，等比数列求和结果为$n-2$，因此空间复杂度为$O(n)$。

散列表

散列函数设计要求

  1. 计算得到的散列值是非负整数
  2. 若key1 = key2，则hash(key1) = hash(key2)
  3. 若key1 ≠ key2，则hash(key1) ≠ hash(key2)

散列函数生成的值要尽可能随机并且均匀分布。

散列冲突解决方法

开放寻址法

核心思想：如果出现散列冲突，重新探测一个空闲位置，将其插入。

线性探测法：

  • 插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
  • 查找数据：我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等，若相等，则说明就是我们要查找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。
  • 删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为deleted，当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。
  • 结论：最坏时间复杂度为$O(n)$

二次探测与线性探测法相比增加了步长。双重散列使用一组散列函数，直到找到空闲位置。

链表法

  • 插入数据：当插入的时候，我们需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以插入的时间复杂度为$O(1)$。
  • 查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数$k=n/m$，其中n表示散列表中数据的个数，m表示散列表中槽的个数，所以是时间复杂度为$O(k)$。

链表法与开放寻址发的比较

开放寻址法的数据都存储在数组中，可以有效利用CPU缓存加快查询速度，其序列化也简单，而链表法包含指针，序列化就比较困难。但是开放寻址方法的删除数据比较麻烦，需要标记已经删除的数据。同时它的冲突代价更高，装载因子的上线不能太大，导致比链表法更浪费内存空间。

数据量比较小、装载因子小的时候，适合用开放寻址法。大对象、大数据量的散列表更适合用链表法。同时，比起开放寻址法，更加灵活，支持更多的优化策略，比如用红黑树代替链表。

Java中的HashMap

HashMap 默认的初始大小是 16，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数。最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

HashMap 底层采用链表法来解决冲突。当链表长度太长（默认超过 8）时，链表就转换为红黑树。使用的散列函数如下：

int hash(Object key) { 
  int h = key.hashCode();
  return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}
//string的hashcode
public int hashCode() { 
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0) { 
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) { 
      var1 = 31 * var1 + var2[var3];
    } 
    this.hash = var1;
  } 
  return var1;
}

散列表虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率会很低。为了解决这个问题，我们将散列表和链表（或者跳表）结合在一起使用。

参考文章

  1. 数据结构与算法之美

 上一页

JavaScript

 评论