散列

文章目录

我们已经知道数组可以通过下标 O(1) 访问,但是删除一个中间元素却要移动其他元素的位置,时间复杂度为 O(n)。 而循环双端链表可以在知道一个节点的情况下迅速删除它,但是查找复杂度又变成了 O(n)。
难道就没有一种可以快速定位和删除元素的方法吗?似乎想要快速找到一个元素除了知道下标之外别无他法,于是乎聪明的计算机科学家又想到了一种方法。 能不能给每个元素一种“逻辑下标”,然后直接找到它呢?散列表就是这种实现。它通过一个哈希函数来计算一个元素应该放在数组哪个位置,当然对于一个特定的元素,哈希函数每次计算的下标必须要一样才可以,而且范围不能超过给定的数组长度。

概念

散列(Hashing)是电脑科学中一种对数据的处理方法,通过某种特定的函数/算法(称为散列函数/算法)将要检索的项与用来检索的索引(称为散列,或者散列值)关联起来,生成一种便于搜索的数据结构(称为散列表)。旧译哈希(误以为是人名而采用了音译)。它也常用作一种信息安全的实现方法,由一串数据中经过散列算法(Hashing algorithms)计算出来的数据指纹(data fingerprint),经常用来识别文件与数据是否有被篡改,以保证文件与数据确实是由原创者所提供。

如今,散列算法也被用来加密存在数据库中的密码(password)字符串,由于散列算法所计算出来的散列值(Hash Value)具有不可逆(无法逆向演算回原本的数值)的性质,因此可有效的保护密码。

特点

  • 若关键字为 k,则其值存放在 f(k) 的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数,按这个思想建立的表为散列表。
  • 对不同的关键字可能得到同一散列地址,即 k1≠k2,而 f(k1) = f(k2) ,这种现象称为冲突。
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

解决冲突

开放寻址法(OPEN ADDRESSING)

开放寻址法中,所有的元素都存放在散列表里,当产生哈希冲突时,通过一个探测函数计算出下一个候选位置,如果下一个获选位置还是有冲突,那么不断通过探测函数往下找,直到找个一个空槽来存放待插入元素。
函数定义:

其中,hash(key) 是哈希函数,di 是增量序列,i 为已冲突的次数。

  • 线性探测法(linear probing):
    h(k,i)=(h′(k)+i)%m,i=0,1,…,m−1
    di= i ,或者其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,然后放置在该单元。
  • 平方探测法(quadratic probing):
    平方探测法
    当一个槽被占用,以二次方作为偏移量。 h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,…,m−1
  • 双重散列(double hashing): 重新计算 hash 结果。 h(k,i)=(h1(k)+ih2(k))%m

链表法

另一种解决冲突的办法。散列到同一位置的元素,不是继续往下探测,而是这个位置是一个链表,这些元素则都放到该链表上。

更多