锐客网

  1. 首页 > it技术 > >

数据结构与算法-散列表(Hash|数据结构与算法-散列表(Hash Table)

特点
散列表用的是数组支持按照下标随机访问数据的特性，是数组的一种扩展，由数组演化而来
关键词
键(key)或者关键字
散列函数(或“哈希函数”): Key转化为数组下标的映射方法
散列函数(或“哈希函数”): 散列函数计算得到的值
关键词介绍 散列函数
它是一个函数，可以把它定义成hash(key)
其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值
散列函数设计的基本要求
1.散列函数计算得到的散列值是一个非负整数；(因为数组下标是从0开始的)
2.如果key1 = key2，那hash(key1) == hash(key2)；
【数据结构与算法-散列表(Hash|数据结构与算法-散列表(Hash Table)】3.如果key1 ≠ key2，那hash(key1) ≠ hash(key2)。
散列冲突
常用的散列冲突解决方法:
1.开放寻址法(open addressing)
核心思想: 如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入
那如何重新探测新的位置?
线性探测(Linear Probing)
往散列表插入数据时，如果某个数据经过散列函数散列后，存储位置已经被占用
我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止
示例: ?色色块表示空闲位置，橙色色块表示已经存储数据，往散列表插入X如下:
数据结构与算法-散列表(Hash|数据结构与算法-散列表(Hash Table)
文章图片
线性探测 散列表中查找元素过程
通过散列函数求出要查找元素的键值对应的散列值，
然后比较数组中下标为散列值的元素和要查找的元素。
如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。
如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中
散列表中删除元素过程
不能把要删除的元素设为空(如这个空闲位置是后来删除的，导致原来查找算法失效)
我们可以将删除的元素，特殊标记为deleted。
当线性探测查找时，遇到标记为deleted的空间，并不是停下来，而是继续往下探测
缺陷
当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，
空闲位置会越来越少，线性探测的时间就会越来越久，
极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为O(n)
在删除和查找时，也会线性探测整张散列表，才能找到要查找或者删除的数据
二次探测(Quadratic probing)
线性探测每次探测的步?是1，那它探测的下标序列就是hash(key)+递增序号
二次探测探测步?为原来的“二次方”，它探测的下标序列就hash(key)+递增序号^2
双重散列(Double hashing)
不仅要使用一个散列函数
使用一组散列函数，先用第一个散列函数，如果计算得到的存储位置已经被占用，
再用第二个散列函数，依次类推，直到找到空闲的存储位置
探测方法总结
不管采用哪种探测方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高
一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位
装载因子(load factor)来表示空位的多少
散列表的装载因子=填入表中的元素个数/散列表的?度
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降
2.链表法(chaining)
一种更加常用的散列冲突解决办法
在散列表中，每个“桶(bucket)”或“槽(slot)”对应一条链表，
所有散列值相同的元素我们都放到相同槽位对应的链表中
插入只需通过散列函数计算出对应的槽位，将其插入到对应链表，时间复杂度为O(1)
查找/删除元素时通过散列函数计算出对应的槽，然后遍历链表查找或者删除
操作时间复杂度跟链表的?度k成正比，也就是O(k)
对于散列比较均匀的散列函数来说，理论上k=n/m
其中n表示散列中数据的个数，m表示散列表中“槽”的个数
链表法示意图 如何设计散列函数？
首先，散列函数的设计不能太复杂
其次，散列函数生成的值要尽可能随机并且均匀分布
其他，需要考虑因素有关键字的?度、特点、分布、还有散列表的大小等
装载因子过大了怎么办？
当散列表的装载因子超过某个阈值时，就需要进行扩容
装载因子阈值的设置要权衡时间、空间复杂度。
如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；
相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于1
如何避免低效地扩容？
为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。
当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中
通过均摊的方法，将一次性扩容的代价均摊到多次操作中，避免一次性扩容耗时过多的情况。
这种实现方式，任何情况下，插入一个数据的时间复杂度都是O(1)
如何选择冲突解决方法？
1.开放寻址法:
当数据量比较小、装载因子小的时候，适合采用开放寻址法。
这也是Java中ThreadLocalMap使用开放寻址法解决散列冲突的原因
2.链表法:
链表法对内存的利用率比开放寻址法要高(链表结点可以在需要的时候再创建)
链表法比起开放寻址法，对大装载因子的容忍度更高
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，
而且比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表
于是在JDK1.8版本中，为了对HashMap做进一步优化，引入了红黑树。
当链表?度太?(默认为8)时，链表转为红黑树，利用红黑树快速增删改查来提高性能;
当红黑树结点个数少于8时，红黑树转为链表，小数据量时红黑树要维护平衡，性能无优势
工业级的散列表应该具有哪些特性？
1.支持快速的查询、插入、删除操作；
2.内存占用合理，不能浪费过多的内存空间；
3.性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况
如何实现这样一个散列表呢？
1.设计一个合适的散列函数；
2.定义装载因子阈值，并且设计动态扩容策略；
3.选择合适的散列冲突解决方法
散列表和链表都是如何组合起来使用?
LRU缓存淘汰算法
借助链表+散列表将时间复杂度降低为O(1)
单纯链表实现LRU缓存淘汰算法步骤
维护一个按照访问时间从大到小有序排列的链表结构。
因缓存大小有限，当缓存空间不够，需要淘汰一个数据时，直接将链表头部的结点删除
当要缓存某个数据时，先在链表中查找这个数据。
如果没有找到，则直接将数据放到链表的尾部；
如果找到了，我们就把它移动到链表的尾部。
因为查找数据需要遍历链表，所以用链表实现的时间复杂度为O(n)
总结以上步骤,总共有三步,都涉及到查找,只用链表实现到时间复杂度为O(n)
往缓存中添加一个数据
从缓存中删除一个数据
在缓存中查找一个数据
链表+散列表实现LUR缓存淘汰算法步骤
双向链表存储数据，每个结点包括数据(data)、前驱指针(prev)、后继指针(next)、hnext
因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中
一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。
前驱和后继指针是将结点串在双向链表中，hnext指针是将结点串在散列表的拉链中
这整个过程涉及的查找操作都可以通过散列表来完成
其他的操作，比如删除头结点、链表尾部插入数据等，可以在O(1)的时间复杂度内完成
添加、查找、删除三个操作的时间复杂度都为O(1)
至此通过组合使用，实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型
链表+散列表实现LUR缓存淘汰算法步骤 Java LinkedHashMap
HashMap底层是通过散列表这种数据结构实现的。
而LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。
LinkedHashMap中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突

    推荐阅读


    上一篇：2018.02.15复盘

    下一篇：最好的关系，是相处不累