002-数据结构与算法-散列表

什么是散列表

散列表是一种特殊数组,基于数据可以按照下标随机访问元素的特点。

保存在散列表中的数据都需要有一个key,在保存之前通过散列函数,计算key对应的hash值,然后根据hash值快速定位数据在散列表中的位置。

散列函数

散列函数的设计思路

散列函数是散列表的核心,在设计散列函数时应遵循以下要求:

  1. 计算结果大于等于0。因为要根据结果确定对应的数组下标。
  2. 如果key1=key2,那么hash(key1)=hash(key2)。
  3. 如果key1$\not=$key2,那么hash(key1)$\not=$hash(key2)。
  4. 函数执行时间要短。
  5. 计算结果尽可能随机并且均匀分布。

其中第3条是理论情况,实际上不存在完全满足第3条的散列函数,不管什么样的散列函数,都会存在 key1$\not=$key2,但是hash(key1)$=hash(key2)的情况,这种情况被称为散列冲突

如何减少散列冲突

开放寻址法

开放寻址法的基本思路是,一旦发生冲突,就寻找还未保存数据的地址,将新值放进去。

例如下图,橙色方块表示已有数据,黄色方块表示空闲。

数据x经过散列运算后,本来应该放到下表为0的位置,但是由于这个位置已经有数据了,所以就顺序向下找,一直找到空闲的位置为止,最后放到下标2的位置上。

查找数据时,先到0的位置上查找,如果对应不上,则顺序向下找,一直到找到为止。

开放寻址法的逻辑比较简单,但是增加了数据插入和查找的时间。

链表法

链表的基本思路是,数据中的每一个下标,都对应一个链表,当放生散列冲突时,将冲突的元素添加到链表中。例如下图所示。

相比与开放寻址法,链表法插入和查找数据的时间更短,但是实现逻辑更复杂。

同时,查找的时间也受到链表长度的影响,如果链表很长,实际上查找效率也不高。

在此基础上还可以进一步做优化,当链表过长时,将链表变成红黑树。Java的HashMap就是基于这种思路实现的。

扩容与装载因子

什么是装载因子

无论采用哪种方法避免散列冲突,当散列表中空闲位置很少的时候,散列冲突的概率都会大大增加,此时对散列表进行扩容,增加空闲位置是一种经常采用的方法。

装载因子表示散列表中已填入元素的比例。

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

扩容步骤

在设计散列表时,都会确定装载因子的上限,例如Java HashMap的装载因子上限是0.75。

当达到上限时,就会触发散列表的扩容操作,如果扩容两倍,那么大致的步骤如下:

  1. 申请一个原散列表两倍大小的新散列表。
  2. 将原表中的数据迁移到新表,由于原表大小放生了变化,数据需要通过哈希函数重新计算在新表中的位置。

如何更高效的扩容

当散列表中的数据量很大时,第2步需要执行很长的时间,此时如果对散列表进行数据插入操作,要么等待很长时间之后再操作,要么强行操作但是导致并发问题。

为了解决写问题,可以不用触发扩容时就同步搬迁所有数据,而是异步一点点的搬迁,例如每次插入新数据时只搬迁一部分,将扩容需要的时间分散在多次操作中完成。

上篇002-数据结构与算法-常见排序算法
下篇002-数据结构与算法-线性表