哈希表

哈希表的概念

• 是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
• 哈希表本质上来说，哈希表就是数组的一种扩展。底层依赖数组支持按下标快速访问元素的特性。
• 将元素的键值转化为数组下标的映射方法称为哈希函数。
• 哈希表利用数组按下标访问元素的时间复杂度是O(1)这一特性。通过哈希函数把元素的键值映射为下标，然后将对应的数据存储在数组中对应下标的位置。当查询元素时，我们使用同样的哈希函数，将元素的键值转化为数组下标，从数组中这个下标对应的位置取出数据。

哈希函数

• 哈希函数首先时一个函数。我们可以把它定义为hash(key)，key表示的是元素的键值，而hash(key)的值表示经过哈希函数计算后得到的哈希值。
• 哈希函数设计时的3个基本要求
  1. 哈希函数计算得到的哈希值是一个非负整数。（因为数组下标是从0开始的）
  2. 如果key1 = key2，则hash(key1) = hash(key2)。（相同的key经过哈希函数得到的哈希值应该时相同的）
  3. 如果key1!=key2，则hash(key1) != hash(key2)。（要求key不同，经过哈希函数得到的哈希值也应该时不同的。但这几乎时不可能的，这种情况的发生被称为哈希冲突。）

哈希冲突

再好的哈希函数也无法避免哈希冲突。解决哈希冲突一般有两种方式。

• 开放寻址法

  1.线性探测法

  当向哈希表中插入数据时，如果某个数据经过哈希函数计算之后得到的哈希值，对应的存储位置已经被占用了，我们就从这个位置开始，在数组中依次向后查找，直到找到空闲位置。

  当在哈希表中查询数据时，则通过哈希函数计算得到哈希值。取出对应哈希值的数组下标的元素进行比较，如果相同则说明这就是要查询的数据，如果不同，则需要从这个下标处开始顺序往后依次查找，直到找到相等的数据，或者遍历到数组的空闲位置还没有找到，说明要查询的数据不在哈希表中。

  当在哈希表中进行数据的删除时，如果使用的是线性探测的方式解决哈希冲突，则删除操作不能简单的直接删除元素，需要对删除元素的存储空间标记为deleted的状态。这是为了避免由于删除操作，导致存储空间为null，线性探测查询数据的操作中途停止的情况发生。

  2.二次探测法

  线性探测法步长为1。向后+1依次探测。二次探测法其实就是将步长变为原来的二次方。探测下标+（探测次数的二次方）进行探测。

  3.双重哈希法

  就是使用多个哈希函数。当第一个哈希函数计算得到的存储位置已经被占用的时候，再用第二个哈希函数重新计算存储位置，直到找到空闲的存储位置。

• 链表法

  链表法是一种更常用的解决哈希冲突的方法。其实就是数组下表中存放的数据是对应的是一个链表。

  当插入数据时，我们通过哈希函数计算出哈希值，找到对应的数组下标位置，将元素插入到对应的链表中。

  查询数据和删除数据，则是通过哈希函数计算出哈希值，找到对应的数组下标位置，取出存放数据的链表，对链表进行遍历，找到对应的数据，去完成查询的比较或者删除的操作。

如何去设计一个合理的哈希表

• 几个方面

  1.找到一个合适的哈希函数。

  2.设置合理的装载因子的阈值，并设计动态扩容策略。

  3.选择合适的哈希冲突解决方法。

• 设计哈希函数

  设计哈希函数的标准

  1.哈希函数的设计不能太复杂，过于复杂的哈希函数，会消耗太多的计算时间。

  2.哈希函数生成的值要尽可能的随机且平均分布，这样才能尽量的去避免哈希冲突。

  3.哈希函数的设计方法还有很多。比如直接寻址法，平方取中法，折叠法，随机数法等。

• 解决装载因子过大的问题

  装载因子=哈希表中的元素个数/哈希表的长度

  可以理解为数组中每个下标都对应的是一个存放数据的链表，而装载因子就是这个链表中所存储的数据个数。

  装载因子应该要设置一个阈值，当达到这个阈值时，需要对哈希表进行扩容操作。

• 避免低效扩容

  当装载因子达到阈值时，我们就进行动态扩容，创建一个存储空间是原来两倍大的一个哈希表。然后将旧的哈希表中的数据搬移到新的哈希表中。

  但是哈希表搬移数据的操作并不像数组一样简单的搬移。他需要对旧数据重新计算哈希值，再将数据放到新的哈希表中。这样的操作就很耗时。

  为了避免扩充时搬移数据耗时过多的情况发生。我们可以不全部搬移数据到新哈希表中。当有新数据要插入的时候，我们将新数据插入到新的哈希表中，同时在旧的哈希表中取出一条旧数据搬移到新哈希表中。这样我们就将搬移工作分解成了多次。均摊了耗时。但由在搬移完全部数据之前，旧的哈希表是一直存在的，同样也会占用一部分内存，同时在进行查询和删除操作的时候，需要在新旧两个哈希表中都进行。

• 选择合适的冲突解决方法

  1.开放寻址法

  当数据量比较小，装载因子小的时候，适合开放寻址法。

  优点：数据存储再数组中，可以有效的利用CPU的缓存，加速查询速度。不涉及链表和指针，方便序列化。

  缺点：装载因子必须小于1，会占用更多的存储空间。

  2.链表法

  其实也可以将链表改造成红黑树，可以设置一个装载因子的阈值，在链表结构和红黑树结构之间进行切换。

  优点：链表的节点可以在用到时再创建，对内存的利用率比较高。对大装载因子的容忍度更高。

  缺点：链表存储数据时，还需要存储next指针，因此会消耗额外的内存空间。链表的节点在内存中零散分布的，不是连续的，对CPU的缓存不友好。

LRU缓存淘汰算法的应用

• 核心思路

  使用哈希表和有序双向链表搭配。有序双向链表用于存储缓存数据，哈希表作为索引，存储着指向有序链表节点的指针。通过哈希表可以快速查找到需要操作的数据的节点，对其进行插入，移动或者删除操作。

• 实现原理

  一个缓存系统，主要包括向缓存中添加一个数据，从缓存中删除一个数据，在缓存中查找一个数据。这3个操作都涉及到了在链表中查找数据的操作。在链表中进行遍历查找时间复杂度为O(n)。

  我们构建一个哈希表作为索引。哈希表中存储着一个指向有序链表节点的指针。我们可以通过哈希表，快速查找到需要操作的数据的有序链表的节点。

  当我们在缓存中查找一个数据时，可以通过哈希表，直接找到这个数据的节点，直接在有序链表中找到这个数据，将它移动到链表的头部。

  当我们往缓存中添加数据时，我们需要先进行查找操作，借助哈希表去查找，如果没找到，则直接将数据插入到链表头部，如果找到了，则将该数据移动到链表头部。

  当我们从缓存中删除数据时，我们同样借助哈希表，直接找到要删除的数据再有序链表中的节点。双向有序链表可直接删除节点，时间复杂度为O(1)

• 总结

  哈希表支持高效的数据插入，删除和查找的操作。但哈希表中的数据是经过哈希函数打乱后无规则存储的，所以不支持顺序遍历并输出数据。

  有序双向链表支持按照某种顺序遍历并输出数据。但查找的时间复杂度为O(n)。

  哈希表和有序双向链表结合起来，就既可以实现快速的插入，删除和查找的操作。又能支持O(n)时间复杂度的按顺序遍历并输出数据。