散列

作者: 简子逍 | 来源:发表于2019-07-12 23:29 被阅读0次

散列的定义与整数散列

问题提出:给出 N 个正整数,再给出 M 个正整数,问这 M 个数中的每个数分别是否在 N 个数中出现过,其中 N ,M ≤ 10^5,且所有正整数均不超过 10^5。

直观的思路是:对每个欲查询的正整数 x ,遍历所有 N 个数,看是否有一个数与 x 相等。这种做法的时间复杂度为 O(NM),当 N 和 M 都很大(10^5 级别)时,显然是无法接受的。

用空间换时间的做法:设定一个 bool 型数组hashTable[100010],其中hashTable[x] == true表示正整数 x 在 N 个正整数中出现过,而hashTable[x] == false表示正整数 x 在 N 个正整数中没有出现过。这样就可以在一开始读入 N 个正整数时就进行预处理,即当读入的数为 x 时,就令 hashTable[x] = true。于是对 M 个欲查询的数,就能直接通过hashTable数组判断出每个数是否出现过。显然这种做法的时间复杂度为 O(N + M)

直接把输入的数作为数组的下标来对这个数的性质进行统计。这是一个很好的用空间换时间的策略,因为它将查询的复杂度降到了 O(1) 级别。但是该策略存在一个局限性,出现数的大小不会超过 10^5。如果输入可能是 10^9 大小,或者甚至是一个字符串,就不能将它们直接作为数组下标。

散列的存在,就是将元素通过一个函数转换为整数,使得该整数可以尽量唯一地代表这个元素。其中把这个转换函数称为散列函数 H,也就是说,如果元素在转换前为 key,那么转换后就是一个整数 H(key)。

常用散列函数

  • 直接定址法。恒等变换,H(key) = key;线性变换,H(key) = a * key + b
  • 平方取中法。取 key 的平方的中间若干位作为 hash 值(很少用)。
  • 除留余数法。把 key 除以一个数 mod 得到的余数作为 hash 值,H(key) = key % mod较常用)

有时候使用散列函数,可能会发生冲突,即两个不同的数 key1 和 key2,它们的 hash 值 H(key1) 与 H(key2) 是相同的。

解决冲突

  • 线性探查法
    当得到 key 的 hash 值 H(key),但是表中下标为 H(key) 的位置已经被其他某个其他元素使用了,那么久检查下一个位置 H(key) + 1 是否被占,如果没有,就使用这个位置;否则就继续检查下一个位置(H(key) + 2)。如果检查位置超过了表长,就回到表首继续循环,直到找到一个可以使用的位置,或者发现表中所有位置都已被占用。
    缺点:容易扎堆,即表中连续若干位置都被使用。
  • 平方探查法
    为了尽可能避免扎堆现象,当表中下标为 H(key) 的位置被占时,将按下面的顺序检查表中的位置:H(key) + 1^2、H(key) - 1^2、H(key) + 2^2、H(key) - 2^2、H(key) + 3^2...。如果 H(key) + k^2 超过了表长 TSize ,就把 H(key) + k^2 对表长 TSize 取模;如果 H(key) - k^2 < 0,就计算 ((H(key) - k^2) % TSize + TSize) % Tsize,等价于将 H(key) - k^2 不断加上 TSize 直到出现第一个非负数。
  • 链地址法
    链地址法不计算 hash 值,而是把所有 H(key) 相同的 key 连接成一条单链表。这样可以设定一个数组 Link ,范围是 Link[0] ~ Link[mod - 1] ,其中 Link[h] 存放 H(key) = h 的一条单链表,于是当多个关键字 key 的 hash 值都是 h 时,就可以把这些冲突的 key 直接用单链表连接起来。最后可以直接遍历这条单链表来寻找所有 H(key) = h 的 key。

二维整数

如何将一个二维整点 P 的坐标映射为一个整数,使得该整点 P 可以由该整数惟一地代表?
假设一个整点 P 的坐标是 (x, y),其中 0 ≤ x,y ≤ Range,那么可以令 hash 函数为 HP = x * Range + y 。这样对数据范围内任意两个整点 P1 和 P2 ,H(P1) 都不会等于 H(P2) ,可以用 H(P) 来唯一地代表点 P,接着可以使用整数 hash 的方法进一步映射到较小的范围。

字符串 hash 初步

字符串 hash 是指将一个字符串 S 映射为一个整数,使得该整数可以尽可能唯一地代表字符串 S

假设字符串均由大写字母 A ~ Z 组成,那么把 A ~ Z 视为 0 ~ 25,这样就把 26 个大写字母对应到了二十六进制中。接着将二十六进制转换为十进制,得到的结果肯定是惟一的,由此便实现了将字符串映射为整数的需求。
同理,如果有小写字母,就把 a ~ z 视为 26 ~ 51,这样就变成了五十二进制转换为十进制的问题。
如果出现了数字,可以增大进制数至六十二

给出 N 个字符串(均由三位大写字母组成),再给出 M 个查询字符串,问每个查询字符串分别在 N 个字符串中出现的次数。

#include <iostream>
using namespace std;

const int maxn = 100;
char S[maxn][5], temp[5];
int hashTable[26 * 26 * 26 + 10];

int hashFunc(char S[], int len){  //hash函数,将字符串转换为整数 
    int id = 0;
    for(int i=0; i < len; i++){
        id = id * 26 + (S[i] - 'A');
    }
    return id;
}

int main(int argc, char** argv) {
    
    int n, m;
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        cin>>S[i];
        int id = hashFunc(S[i], 3);  //将字符串 S[i] 转换为整数 
        hashTable[id]++;  //该字符串的出现次数加 1 
    }
    
    for(int i=0; i<m; i++){
        cin >> temp;
        int id = hashFunc(temp, 3);  //将字符串 temp 转换为整数 
        cout<<hashTable[id];  //输出该字符串的出现次数 
    }
    
    return 0;
}
// 测试结果
6 3                      //输入 n,m 值
WER ABC OJK ABC RET POD  //输入 n 个字符串
WEU ABC POD              //输入 m 个字符串
021                      //输出 m 个字符串分别在 n 个字符串中出现的次数

相关文章

  • 散列 & 线性散列

    Hashing 散列 原理: use key value to compute page address of t...

  • python数据结构教程 Day10

    本节重点: 散列 散列函数 完美散列函数 hashlib 散列函数设计 冲突解决方案 一、散列 能够使得查找的次数...

  • 散列

    散列值与相等性 等值对象的散列值必须相等。散列相等未必等值。 散列表算法 其他说明 key必须是可散列的。可散列需...

  • 散列

  • 散列

    定义 散列是一种常见的数据存储技术,散列后的数据可以快速插入或者取用。散列使用的数据解构叫做散列表。在散列中插入、...

  • 散列

    HashMap HashMap也是我们使用非常多的Collection,它是基于哈希表的 Map 接口的实现,以k...

  • 散列

    哈希码是一个散列值,通过单向函数求得,范围是int,数量有限,所以会发生散列值冲突。HashMap、Hashtab...

  • 散列

    散列的定义与整数散列 问题提出:给出 N 个正整数,再给出 M 个正整数,问这 M 个数中的每个数分别是否在 N ...

  • 散列

    散列函数:把查找表中的关键字映射成该关键字对应的地址。Hash(key)=Addr这里的地址可以是数组下标,索引或...

  • 散列

    前面我们讲过字典,虽然我们说过通过使用查找方法来提高处理效率,但是这样的效果其实并不是很好,因此我们还需要使用一种...

网友评论

      本文标题:散列

      本文链接:https://www.haomeiwen.com/subject/vahukctx.html