首页 > 其他分享 >哈希表

哈希表

时间:2023-11-27 17:22:36浏览次数:30  
标签:哈希 int linker value 键值 key

哈希表

引入

oi-wiki.org/ds/images/hashtable.svg

哈希表又称散列表,一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据,是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值,就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数,浮点数,字符串甚至结构体。

哈希函数

要让键值对应到内存中的位置,就要为键值计算索引,也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数,也称散列函数。举个例子,如果键值是一个人的身份证号码,哈希函数就可以是号码的后四位,当然也可以是号码的前四位。生活中常用的「手机尾号」也是一种哈希函数。在实际的应用中,键值可能是更复杂的东西,比如浮点数、字符串、结构体等,这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算,并且尽量使计算出来的索引均匀分布。

能为 key 计算索引之后,我们就可以知道每个键值对应的值 value 应该放在哪里了。假设我们用数组 a 存放数据,哈希函数是 f,那键值对 (key, value) 就应该放在 a[f(key)] 上。不论键值是什么类型,范围有多大,f(key) 都是在可接受范围内的整数,可以作为数组的下标。

在 OI 中,最常见的情况应该是键值为整数的情况。当键值的范围比较小的时候,可以直接把键值作为数组的下标,但当键值的范围比较大,比如以 10^9 范围内的整数作为键值的时候,就需要用到哈希表。一般把键值模一个较大的质数作为索引,也就是取 f(x)=x \bmod M 作为哈希函数。

另一种比较常见的情况是 key 为字符串的情况,由于不支持以字符串作为数组下标,并且将字符串转化成数字存储也可以避免多次进行字符串比较。所以在 OI 中,一般不直接把字符串作为键值,而是先算出字符串的哈希值,再把其哈希值作为键值插入到哈希表里。关于字符串的哈希值,我们一般采用进制的思想,将字符串想象成一个 127 进制的数。那么,对于每一个长度为 n 的字符串 s,就有:

\(X = s_0\cdot 127^0 + s_1\cdot 127^1 + s_2\cdot 127^2 + \dots + s_n \cdot 127^n\)

我们可以将得到的 \(x\) 对 \(2^{64}\)(即 unsigned long long 的最大值)取模。这样 unsigned long long 的自然溢出就等价于取模操作了。可以使操作更加方便。

这种方法虽然简单,但并不是完美的。可以构造数据使这种方法发生冲突(即两个字符串的 \(x\)x 对 \(2^{64}\) 取模后的结果相同)。

我们可以使用双哈希的方法:选取两个大质数 \(a,b\)。当且仅当两个字符串的哈希值对 \(a\) 和对 \(b\) 取模都相等时,我们才认为这两个字符串相等。这样可以大大降低哈希冲突的概率。

冲突

如果对于任意的键值,哈希函数计算出来的索引都不相同,那只用根据索引把 (key, value) 放到对应的位置就行了。但实际上,常常会出现两个不同的键值,他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。在 OI 中,最常用的方法是拉链法。

拉链法

拉链法也称开散列法(open hashing)。

拉链法是在每个存放数据的地方开一个链表,如果有多个键值索引到同一个地方,只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍,对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 \(1\ldots M\),哈希表的大小为 \(N\),那么一次插入/查询需要进行期望 \(O(\frac{N}{M})\) 次比较。

实现

vector 实现(对于字符串hash)

vector <string> linker[mod + 2];
void insert()
{
    int hash = 1;
    for (int i = 0; s[i]; i++)
    {
		hash = (hash * 1ll * base + s[i]) % mod;
    }
    string t = s;
    for (int i = 0; i < linker[hash].size(); i++)
    {
        if (linker[hash][i] == t)
        {
            return ;
		}
        else
        {
            linker[hash].push_back(t);
            ans++;
        }
    }
}

链式前向星实现

const int SIZE = 1000000;
const int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];

  int head[M], size;

  int f(int key) { return (key % M + M) % M; }

  int get(int key) {
    	for (int p = head[f(key)]; p; p = data[p].next)
      		if (data[p].key == key) return data[p].value;
    	return -1;
  }

  int modify(int key, int value) {
    	for (int p = head[f(key)]; p; p = data[p].next)
      		if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    	if (get(key) != -1) return -1;
    	data[++size] = (Node){head[f(key)], value, key};
    	head[f(key)] = size;
    	return value;
  }
};

这里再提供一个封装过的模板,可以像 map 一样用,并且较短

struct hash_map {  // 哈希表模板

  struct data {
        long long u;
        int v, nex;
  };  // 前向星结构

  data e[SZ << 1];  // SZ 是 const int 表示大小
  int h[SZ], cnt;

  int hash(long long u) { return (u % SZ + SZ) % SZ; }

  // 这里使用 (u % SZ + SZ) % SZ 而非 u % SZ 的原因是
  // C++ 中的 % 运算无法将负数转为正数

  int& operator[](long long u) {
        int hu = hash(u);  // 获取头指针
        for (int i = h[hu]; i; i = e[i].nex)
          if (e[i].u == u) return e[i].v;
        return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
        cnt = 0;
        memset(h, 0, sizeof(h));
  }
};

在这里,hash 函数是针对键值的类型设计的,并且返回一个链表头指针用于查询。在这个模板中我们写了一个键值对类型为 (long long, int) 的 hash 表,并且在查询不存在的键值时返回 \(-1\)。函数 hash_map() 用于在定义时初始化。

闭散列法

闭散列方法把所有记录直接存储在散列表中,如果发生冲突则根据某种方式继续进行探查。

比如线性探查法:如果在 d 处发生冲突,就依次检查 d + 1d + 2……

const int N = 360007;  // N 是最大可以存储的元素数量

class Hash {
	private:
      int keys[N];
      int values[N];

 	public:
  		Hash() { memset(values, 0, sizeof(values)); }

  	int& operator[](int n) {
    // 返回一个指向对应 Hash[Key] 的引用
    // 修改成不为 0 的值 0 时候视为空
        int idx = (n % N + N) % N, cnt = 1;
        while (keys[idx] != n && values[idx] != 0) {
          idx = (idx + cnt * cnt) % N;
          cnt += 1;
    	}
        keys[idx] = n;
        return values[idx];
  	}
};

例题

P3405 USACO16DEC Cities and States S

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>

#define mod 233333

int n;
char a[12], b[12];
long long ans;
std::vector<std::pair<int, int>> linker[mod + 2];

inline int getHash(char a[], char b[])
{
	return a[0] - 'A' + (a[1] - 'A') * 26 + (b[0] - 'A') * 26 * 26 + (b[1] - 'A') * 26 * 26 * 26;
}

inline void insert(int x)
{
	for (int i = 0; i < linker[x % mod].size(); i++)
	{
		if (linker[x % mod][i].first == x)
		{
			linker[x % mod][i].second++;
			break;
		}
	}
	linker[x % mod].push_back({x, 1});
}

inline int find(int x)
{
	for (int i = 0; i < linker[x % mod].size(); i++)
	{
		if (linker[x % mod][i].first == x)
		{
			return linker[x % mod][i].second;
		}
	}
	return 0;
}

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n;
	for (int i = 1; i <= n; i++)
	{
		std::cin >> a >> b;
		a[2] = 0;
		if (a[0] != b[0] || a[1] != b[1])
		{
			ans += find(getHash(b, a));
		}
		insert(getHash(a, b));
	}
	std::cout << ans;
	return 0;
}

标签:哈希,int,linker,value,键值,key
From: https://www.cnblogs.com/kdlyh/p/17859849.html

相关文章

  • P3370 【模板】字符串哈希(普及−) 题解
    题目链接题目大意如题,给定\(N\)个字符串(第\(i\)个字符串长度为\(M_i\),字符串内包含数字、大小写字母,大小写敏感),请求出\(N\)个字符串中共有多少个不同的字符串。不知道大家知不知道一个字符串函数,叫\(insert\)他是\(STL\)库中的一个函数,作用是将两个字符串拼接起来,我......
  • 字符串哈希
    字符串哈希字符串哈希就是将一个字符串映射为P进制的整数.将一个字符串映射成一个P进制整数对于一个长度为n的字符串s,这样定义一个Hash函数:\(h(s)=\sum_{i=1}^{n}s[i]\timesp^{n-i}(modM)\)例如,字符串,abc,其哈希值为\(ap^2+bp^1+c\)如果两个字符串不一样,哈希值......
  • 浅谈字符串哈希 入门
    基本介绍字符串哈希的主要思路是这样的:首先选定一个进制\(P\),对于一个长度为\(N\)的字符串\(S\)的所有\(i(1\leqi\leqn)\)的\(S_1,S_2,...,S_i\)子串表示成\(P\)进制的值预处理记录下来。这样判断\(S_i,S_{i+1},...,S_{i+m-1}\)和\(T_1,T_2,...,T_m\)是否相等......
  • ASP.NET MD5与哈希加密
    ......
  • day7 | 哈希表(2)
    题目链接:454.四数相加II-力扣(LeetCode)题目描述:给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i,j,k,l) 能满足:0<=i,j,k,l<nnums1[i]+nums2[j]+nums3[k]+nums4[l]==0解题思路:参考代码随想录(program......
  • 代码随想录算法训练营第六天 |● 哈希表理论基础 ● 242.有效的字母异位词 ● 349.
    今日学习的文章链接和视频链接https://programmercarl.com/哈希表理论基础.html242.有效的字母异位词varisAnagram=function(s,t){if(s.length!==t.length)returnfalseletmap=newMap();for(letcharofs){if(!map.get(char)){......
  • 字符串哈希算法
    一、字符串哈希:将一串字符串映射成一个整数,并用它来代替字符串进行比较。这样俩个字符串的比较就变成俩个整数的比较,可以将时间复杂度减少至O(1)二、哈希函数:为了将字符串转化为整数,需要一个哈希函数hash,使得以下条件成立:如果字符串s==t那么hash(s)==hash(t)。一般情况下采......
  • 第六章 消息认证和哈希函数 —— 现代密码学(杨波)课后题答案解析
    第五章作业参考答案1.6.1.3节的数据认证算法是由CBC模式的DES定义的,其中初始向量取为0,试说明使用CFB模式也可获得相同的结果。解:设需认证的数据分为64比特长的分组,D1,D2,…,DN,其中DN不够64比特则右边补0,由题设,数据认证算法相当于在CBC模式中初始向量取为0,并按如下关系进行:   ......
  • 算法刷题记录-哈希表
    算法刷题记录-哈希表有效的字母异位词给定两个字符串*s*和*t*,编写一个函数来判断*t*是否是*s*的字母异位词。注意:若*s*和*t*中每个字符出现的次数都相同,则称*s*和*t*互为字母异位词。示例1:输入:s="anagram",t="nagaram"输出:true示例2:输入:s......
  • 【golang】Golang 哈希码 hashcode 输入一个字符串,得到一个唯一标识码
    如何输入一个字符串,得到一个唯一的hashcode?例子如下:packagemainimport("fmt""hash/crc32")//Stringhashesastringtoauniquehashcode.////crc32returnsauint32,butforouruseweneed//andnonnegativeinteger.Herewec......