哈希概念

哈希函数: Wiki链接

哈希用途

哈希, 只支持2个操作: insert插入 和 find查找, 两个功能

这里的find查找, 分为两种情况:

• 存在性判断: 判断这个(对象), 是否存在. …也可以简单称为: 替代set的哈希
• 映射性结果: 通过这个对象, 得到一个值(一般是个整数) …也可以简单称为: 替代map的哈希

存在性判断, 也可以划分为 (映射性), 即 存在返回1, 否则返回0

哈希分类

离散化

• 适用范围: 整数, 字符串, 自定义类型 (几乎是任意类型)

ST arr[ 100];
sort( arr, arr + 100);
int n = unique( arr, arr + 100) - arr; //< 去重可以省略

int find( ST _a){
	int l = 0, r = n-1;
	//* 二分代码
	return r;
}
1
2
3
4
5
6
7
8
9

• 因为有sort, ST必须要有<号的重载;
  因为有unique, ST必须有==号的重载

• 缺点: 不支持动态的插入!
  必须是, 先得到所有的对象, 然后将所有对象统一放到数组里, 然后排序.

• 每次查询的时间是: log(N)

无序容器

• 适用范围: 整数, 字符串, 自定义类型 (几乎是任意类型)

可以发现, set, map 是满足 哈希所要求的这两个功能( 插入 和 查询)
但一定要注意, unordered_set/map 的常数, 是很大的!!! 一旦超时了, 就要换其他方法来哈希

以下是将(数据) 映射到 (0, 1, 2, 3, ...)的范围内的哈希. (如果只是 存在性判断, 使用unordered_set即可)

unordered_map< ST, int> hash;

void insert( ST _a){
	if( hash.find( _a) == hash.end()){
		hash[ _a] = hash.size();
	}
}

int find( ST _a){
	if( hash.find( _a) == hash.end()){
		return -1;
	}
	return hash[ _a];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 支持 动态插入和查询, 时间是logN, 但容器的常数较大!

P进制

• 适用范围: 字符串

具体参见 链接

Trie树

ToDo

取模法

适用范围: LL所能表示的 整数

假设数据范围 (所有不同的整数个数)为N, 取Mod_为 大于N的某个质数.
取模法, 会讲一个整数c, 进行取模pos = (c % Mod_ + Mod_) % Mod_, 最终得到在[0, Mod_)范围的结果
这个pos值, 就是 其所对应的哈希值. … 原理还是挺简单的, 就是简单的取模知识

可以发现, 对于a + k * Mod_这些数, 他们的pos 都是一样的, 但这些数是不同的. 也就是, 发生了: 哈希冲突

为了解决(哈希冲突), 取模法 分为两种具体实现方式: (拉链法chain) (开放寻址法open address)

拉链法

既然有多个不同的对象, 会同时对应到pos 这一个位置上, 那就让这个pos位置, 对应一个链表
让所有的这些产生(冲突)的值, 都放到 这个链表里.
查询时, 就遍历这个链表.

可以想象成: 是有Mod_个单链表

此时, Mod_取 > N的 最小的质数 (不是最小也可以, 反正必须要 大于N)
注意, N是不同数的个数, 不一定是数据规模! 可能数据规模是1e7, 但不同的数的个数只有2e5个

LITERAL_ int Mod_ = 200003; //> N为2e5
int Head[ Mod_], Nex[ Mod_], Ver[ Mod_], Index;
void Hash_init(){
    memset( Head, -1, sizeof( Head));
    Index = 0;
}
int Hash_index( int _cur){
    return (_cur % Mod_ + Mod_) % Mod_;
}
bool Hash_find( int _cur){
    int pos = Hash_index( _cur);
    for( int j, i = Head[ pos]; ~i; i = Nex[ i]){
        j = Ver[ i];
        if( j == _cur){
            return true;
        }
    }
    return false;
}
void Hash_insert( int _cur){
    if( Hash_find( _cur)){ //< 不要忘记这里!  相同的元素不再插入多次!!!
        return;
    }
    //> @Pos_0
    int pos = Hash_index( _cur);
    Ver[ Index] = _cur;
    Nex[ Index] = Head[ pos];
    Head[ pos] = Index ++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

代码还是挺简单的, 核心就是链表操作. 但, 虽然简单, 但比unordered_set/map要快很多!!!

以上是 存在性判断的哈希 (即替代set的哈希) 的代码, 如果是 映射性哈希, 即替代map的哈希, 做法是:
… 比如要映射到[0, Mod_)范围内, 这个pos肯定不能作为哈希结果, 因为他会冲突.
… 在全局记录一个hashed_count = -1;, 每当insert( _a)的一个新的数时(也就是上面代码中的@Pos_0处)
… 1, ++ hashed_count , 表示, 这个_a数 他的哈希映射值为: hashed_count
… 2, 肯定还需要记录下来这种映射关系, 因为到时候Find时, 还要用到他.
… 将int Ver[] 改为: pair Ver[], 每一个Ver点, 存储: { _a, hashed_count}, (顶点值 即原值, 和, 其对应的映射值)
… 3, 当int find( _a)时, 也是以上代码, 找到节点后, 返回: ver.second

支持 动态的查询和插入.

拉链法 不如 开放寻址法常用, 因为:

• 需要Mod_ * 3倍的空间, (如果是map映射, 则需要Mod_ * 4的空间)
• 开放寻址法, 可以在一维的hash表进行, 比较简单. 而拉链法, 需要二维的链存储

开放寻址法

所有的数, 都可以不冲突的 放到[0, Mod_)范围里. 因为, Mod_ > N

比如_a 他的pos位置, 已经有人_a + k*Mod_被占据了;
那么, 就在pos+1, pos+2, pos+3, ...里找一个 没有被占据的位置!
比如, 是pos + c位置, 还没有人占据. 那么, _a就选在pos + c的位置上!
… 这种做法, 称为: 线性探测法, 下面会讲到探测法.
… (所谓探测: 本来是当前这个位置pos, 但他已经被占据了(发生了冲突), 但我们知道, 空位置肯定是够的)
… (因此, 需要进行 探测, 也就是: 从pos 去 找一个没有被占据的位置)

这也是挺简单暴力的做法.

这当然是正确的, 但是, 如果产生冲突, 就会一直 一步步的往后移动
为了使这个移动的次数, 尽量的少, 一般让Mod_大点! Mod_变大, 必然会让整体分布更分散些, 一般选择2/3 * N左右的质数.

LITERAL_ int Mod_ = 500009, Invalid_ = 0x3F3F3F3F;
int Sett[ Mod_]; //< N=2e5
void Hash_init(){
    memset( Sett, 0x3F, sizeof( Sett));
    Index = 0;
}
int Hash_index( int _cur){
    int index = ( _cur % Mod_ + Mod_) % Mod_;
    while( ( Sett[ index] != Invalid_) && ( Sett[ index] != _cur)){
        ++ index;
        if( index == Mod_){
            index = 0;
        }
    }
    //* 此时, 要么[index]为空 没有人占据, 要么[index]就是自己
    return index;
}
void Hash_insert( int _cur){
    Sett[ Hash_index( _cur)] = _cur;
}
bool Hash_find( int _cur){
    return Sett[ Hash_index( _cur)] == _cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

以上是 存在性判断的哈希 (即替代set的哈希) 的代码, 如果是 映射性哈希, 即替代map的哈希, 做法是:
… 以Hash_index( _cur) 作为 _cur的 哈希映射值, 这不会产生冲突
… 这比 拉链法的处理, 简单多了.

• 这个Invalid_ 和 对Sett的Init初始化, 很重要. 他的初始值, 也就表示 (没有人占据)
  必须是一个, 不在数据范围内的数. 比如数据范围是[-1e9, 1e9], 那么选取0x3F3F3F3F 自然是可以的

探测法

所谓探测: 本来是当前这个位置pos, 但他已经被占据了(发生了冲突), 但我们知道, 空位置肯定是够的
因此, 需要进行 探测, 也就是: 从pos 去 找一个没有被占据的位置, 一定存在没有被占据的位置

---

pos, pos+1, pos+2, ..., Mod_-1, 0, 1, ... 这样依次的 一个位置一个位置的找, 称为: 线性探测法
… 但这种方法, 容易导致: 扎堆. 因为他是连续的一个区间.
… 如果c的最终的位置是p, 则说明: [c%Mod_, p-1]区间, 都是被占据了的. 他需要一个个的移动到p

为了防止这种扎堆的情况, 引入 平方探测法Quadratic probing (with positive increments only)
当前要插入的数是: cur, pos = cur % Mod_
在: pos + 0*0, pos + 1*1, pos + 2*2, ..., pos + i*i 这些位置里, 找第一个没有被占据的位置.
这样整体就比较分散, 避免了扎堆

但要注意:

• i的取值是: [0, Mod_-1], 因为: pos + i*i == pos + (i+Mod_)*(i+Mod_)
  证明: (i+Mod_)*(i+Mod_) == i*i ,,,在%Mod_下
  因此, 直接for循环i = [0, Mod_-1]范围

• 平方探测, 可能会出现: 无解. 也就是, 有空位, 但是 探测找不到; 而这在线性探测中, 是不存在的
  比如, Mod_ = 5, 0*0 = 0, 1*1 = 1, 2*2 = 4, 3*3 = 4, 即一共是: 0, 1, 4 共3个增量.
  假如当前cur = 15, 则pos = 0, 他会探测的位置是: 0, 1, 4
  而假如, 0, 1, 4都已经占用. 但2, 3没有占用.
  此时就是无解, 平方探测认为所有位置都占用了, 但实际上是有的!