💻 工作数据结构与算法Hash
算法
Source
Edit
History

散列

文章目录
  1. 1. 概念
  2. 2. 特点
  3. 3. 解决冲突
    1. 3.1. 开放寻址法（OPEN ADDRESSING）
    2. 3.2. 链表法
  4. 4. 更多

我们已经知道数组可以通过下标 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

链表法

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

更多