数据结构与算法-散列表

Posted on | Edited on | In ,

散列表的原理

底层基于数组实现，数据通过hash函数计算出数组下标写入到数组中，查找通过hash函数找到数据。理论上删除、查找的效率O(1)。

散列表解决hash冲突

当key1不等于key2，但是hash(key1)==hash(key2)出现散列的冲突，一般有如下的方式解决。散列冲突可以用loadFactor表示：

1
2

locafactor = 元素个数/数组长度

链表

将散列的hash方法的结果对应成一个bucket或者slot，每个bucket是一个链表。

  • 写入：当hash冲突后在链表后面追加一个元素。时间复杂度O(1)
  • 读取：hash找到bucket，遍历链表，时间复杂度O(1)
  • 删除：hash找到bucket，遍历链表，删除，时间复杂度O(1)

比较理想的情况下是元素个数=槽数，如果hash冲突比较大会退化成链表

优点：对内存要求低，只有写入数据才会在链表中加1；hash冲突代价小，增删改几本上是O(1)
缺点：不是连续空间无法很好利用cpu缓存；链表包含下一个数据的指针序列化成本高
场景：数据量大，负载因子高，频繁修改的场景。HashMap

开放寻址

  • 写入：比如key1和key2冲突，key2写入时候发现这个数组下标对应的元素有key1了这时候继续想后遍历知道有一个为空的字段，写入
  • 读取：找到下标元素后比对如果不相等向后遍历直到找到相等的元素或者第一个为空的元素为止

  • 删除：由于上面说的查找需要遍历到为空的元素，所以需要用到标记删除法。

    优点：内存是连续地址很好的用到cpu的缓存；不包含指针序列化成本低
    缺点：内存要求高；hash冲突成本高，查找、删除、修改可能要遍历数组
    场景：数据量小，负载因子不高的场景。ThreadLocalMap

构建一个hash散列应该注意的问题

hash算法高效

  • 自身算法效率要高，否则资源会大量浪费在hashkey的计算上。
  • 算法要均匀尽量避免hash冲突，防止退化成链表

具体算法有：直接寻址法、平方取中法、折叠法、随机数法

如何避免装载因子多大

由于装载因子都大会导致hash冲突几率变高，链表过长，这时候如果是动态的散列表我们要进行”动态扩容“。

  • 一般会设定一个负载因子的阈值打到阈值后开始扩容，扩容到原来的两倍，负载因子值会下降一半。动态扩容的事件复杂度是O(n)
  • 如果系统对于内存的使用不敏感，对于响应敏感，为了防止hash冲突可以把负载因子值调低
  • 如果系统对于内存的使用敏感，对于响应速度不敏感，可以将这个负载因子阈值调高，甚至可以大于1。

如何避免低效扩容

在散列表很大时候扩容有可能阻塞正常的读写操作，比如：1G的数据扩容到2G。这时候我们可以采用如下方案：

  • 在额外申请一块2G的空间，新的写入操作往新的散列表写，同时将一个老的数据写过来，几次之后老的数据就会完成迁移
  • 读的时候先从新的里面读取如果没有值在从老的数据里面读取

hash表和其他数据结构共用的案例

实现高效的lru算法

如果实现LRU算法用双向链表，访问、更新一个元素需要遍历链表，时间复杂度是O(n),如果想提高效率需要用到散列表配合

散列表+双向链表

1
2
3
4
5
6
7

type LRUNode struct {
  Prev *LRUNode //Lru双向链表
  Next *LRUNode //Lru双向链表
  Data interface{}
  Hnext *LRUNode  //散列值
}

访问：其中prev+next是双向链表用来实现LRU功能，每次访问节点先从hashTable中获取数据，然后将数据移到链表尾部。时间复杂度O(1)
写入：插入到散列中Hnext是用来维护散列的拉链，这里用的是链表来解决hash冲突，同时插入链表的尾部。时间复杂度O(1)
删除：找到数据从散列中删除，然后在从链表中删除。时间复杂度O(1)

java的LinkedHashMap也是用这个思想实现的。

redis的sortset

用跳表来实现，用score查找、排序、按照sorce范围查找。
用散列来实现，用key查找、删除、插入。