ACM|哈希表 hash|字符串|#

哈希表哈希表定义哈希表是又称散列表，一种以 "key-value" 形式存储数据的数据结构。所谓以 "key-value"形式存储数据，是指任意的key 都唯一对应到内存中的某个位置。只需要输入查找的值 key，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。
哈希函数要让 key 对应到内存中的位置，就要为 key 计算索引，也就是计算这个数据应该放到哪里。这个根据 key 计算索引的函数就叫做哈希函数，也称散列函数。
举个例子，比如 key 是一个人的身份证号码，哈希函数就可以是号码的后四位，当然也可以是号码的前四位。生活中常用的**“手机尾号”**也是一种哈希函数。
应用中，key 可能是更复杂的东西，比如浮点数、字符串、结构体等，这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。
在ACM中，最常见的情况是key为整数的时候，当key的范围比较小的时候，就可以直接把key作为数组下标，但当key的范围比较大的时候( 1 0 9 10^9 109)，就需要用到哈希表了，一般我们取一个大质数M，将key模M之后作为索引，也就是 h a s h ( x ) = xm o dM hash(x) = x\ mod\ M hash(x)=x mod M作为h哈希函数。
还有一种情况也就是之后要介绍的字符串哈希在 A C M / O I ACM/OI ACM/OI中特别常见，我们一般不直接把字符串作为 k e y key key，而是先计算出字符串的哈希值，再把其哈希值作为 k e y key key插入到哈希表中。
能为k e y key key 计算索引之后，我们就可以知道每个v a l u e value value 应该放在哪里了。假设我们用数组a n s ans ans 存放数据，哈希函数是h a s h hash hash，那键值对( k e y , v a l u e ) (key,value) (key,value) 就应该放在a n s [ h a s h ( k e y ) ] ans[hash(key)] ans[hash(key)]上。不论k e y key key 是什么类型，范围有多大， h a s h ( k e y ) hash(key) hash(key) 都是在可接受范围内的整数，可以作为数组的下标。
如何处理冲突如果对于任意的k e y key key，哈希函数计算出来的索引都不相同，那只用根据索引把( k e y , v a l u e ) (key,value) (key,value)放到对应的位置就行了。但实际上，常常会出现两个不同的 k e y key key，他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。在A C M / O I ACM/OI ACM/OI 中，最常用的方法是拉链法。
拉链法拉链法也称开散列法（ o p e n h a s h i n g open hashing openhashing）。
拉链法是在每个存放数据的地方开一个链表，如果有多个 $key $索引到同一个地方，只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其 $key $与查询的 $key是否一致。如果索引的范围是是否一致。如果索引的范围是是否一致。如果索引的范围是[1,M)$，哈希表的大小为N N N，那么一次插入/查询需要进行期望 O ( N M ) O(\frac{N}{M}) O(MN?)次比较。
另外还有闭散列法处理冲突（基本不用）。
代码实现拉链法

const int SIZE = 1000000; const int M = 999997; struct HashTable { struct Node { int next, value, key; } data[SIZE]; int head[M], size; int hash(int key) { return (key % M + M) % M; } int get(int key) { int hs = hash(key); for (int p = head[hs]; p; p = data[p].next) { if (data[p].key == key) { return data[p].value; } } return -1; } int modify(int key, int value) { int hs = hash(key); for (int p = head[hs]; p; p = data[p].next) { if (data[p].key == key) { return data[p].value = https://www.it610.com/article/value; } } } int add(int key, int value) { if (get(key) != -1) { return -1; } data[++size] = (Node){head[hash(key)], value, key}; head[hash(key)] = size; return value; } };

【ACM|哈希表】下面我白嫖的wzy?学长封装的 h a s h _ m a p hash\_map hash_map:

typedef long long ll; struct hash_table { ll hash_mod = 590027; ll state[600000], ans[600000], up; ll tot, first[600000], nxt[600000], w[600000]; void init() { memset(first, 0, sizeof(first)); tot = 0; up = 0; } ll ins(ll sta, ll val) { ll key = sta%hash_mod; for(ll i = first[key]; i; i = nxt[i]) { if(state[w[i]] == sta) return ans[w[i]] += val; } state[++up] = sta; ans[up] = val; nxt[++tot] = first[key]; w[tot] = up; first[key] = tot; return val; } };