`算法知识` 哈希

算法 {哈希}

任意类型的动态哈希(Map)

性质

理论上 他是$\log (N)$, 但是 因为他是动态的过程, 所以 实际效率还不错 虽然会比(取模哈希)慢几个常数;

算法

模板代码

template< class _Type> class __Hash_Mapping{
public:
    unordered_map< _Type, int> Map; // `S: Map.size()`, 所有元素的哈希值为`[0, S)`;

    __Hash_Mapping(){}
    void Initialize(){ Map.clear();}
    void Add( _Type _a){ if( Map.find( _a) == Map.end()){ Map[ _a] = Map.size();}}
    int Get_hash( _Type _a) const{
        if( Map.find( _a) == Map.end()){ return -1;}  return Map.at( _a);}
}; // class __Hash_Mapping
__Hash_Mapping< ?> Hash_Mapping;
@TODO( Hash_Mapping.Initialize());
1
2
3
4
5
6
7
8
9
10
11
12

任意类型的静态哈希(离散化)

算法模板

template < class _Type> class Hash_discretization{
public:
    const int __Range_maximum;
    _Type * __Array;
    int Array_size; // 所有哈希的值 是`[0, Array_size)`;

    Hash_discretization( int _range_maximum)
            :
            __Range_maximum( _range_maximum){
        __Array = new _Type[ __Range_maximum];

        Initialize();
    }
    ~Hash_discretization(){
        delete[] __Array;
    }
    void Initialize(){
        Array_size = 0;
    }
    void Add( _Type _a){
        // ASSERT_( Array_size < __Range_maximum);
        __Array[ Array_size] = _a;
        ++ Array_size;
    }
    void Discretize(){
        sort( __Array, __Array + Array_size);
        Array_size = unique( __Array, __Array + Array_size) - __Array;
    }
    int Get_hash( _Type _tar){
        int l = 0, r = Array_size - 1, mid;
        while( l < r){
            mid = ( l + r) >> 1;
            if( __Array[ mid] < _tar){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        if( __Array[ l] == _tar){
            return l;
        }
        return -1;
    }
}; // class Hash_discretization
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

字符串哈希

定义

字符串str="abc"(a為低位) 他的哈希值為A*(Base^2) + B*Base + C(在模Mod下) 其中ABC為abc對應的Base進制數;

性质

這個哈希算法是絕對的 只與當前字符串有關 與其他背景都無關;
比如S="abcdef" 他的子字符串bcd的哈希值 你通過{1:預處理S 來獲得子串[1:3]的哈希值; 2:直接求bcd的哈希值} 兩者是一樣的! 都等於B*Base^2 + C*Base + D;

@DELI;

映射从1开始

假如是从0开始映射, 则abc 和 bc, 他们的对应的P进制是: (0) (1) (2) 和 (1) (2)

如果采用(前高位)的哈希顺序, 则他们对应的10进制值都是: (1 * P + 2), 就冲突了;

其原因在于: 两者的长度不同; 如果长度相同, 不会出现: 前导零的情况;

一般, 最好都从(1)开始映射

@DELIMITER

字符串的哈希冲突

由于字符串哈希, 不像整数哈希是有探测法(即整数哈希 不会出现哈希冲突, 探测法解决了这点)

而字符串哈希没有探测法, 因此, 字符串哈希是会发生冲突的; 假如他发生冲突, 目前是没有解决办法的!

只能去尝试更换: 字符串哈希的取模值: 将(默认的1e9+7) 改为: (1e9 + 21)

算法

代碼

namespace __HashString{
//< 哈希算法: 字符串`str="abc"`(`a`為低位) 他的哈希值為`A*(Base^2) + B*Base + C`(在模`Mod`下) 其中`ABC`為`abc`對應的`Base`進制數, 即*字符串低位 其實是高量級*!
static constexpr int __Base_ = 131;
static constexpr int __Mod_ = int(1e9) + 7;
int __Hash_char( char _c){
    if( (_c >= 'a') && (_c <= 'z')){ return _c - 'a' + 1;}
    else if( (_c >= 'A') && (_c <= 'Z')){ return 27 + _c - 'A';}
    else if( (_c >= '0') && (_c <= '9')){ return 53 + _c - '0';}
    ASSERT_( 0);
    return _c;
}
int Get_hash( const char * _str, int _length){
    int ANS = __Hash_char( _str[ 0]);
    for( int i = 1; i < _length; ++i){
        ANS = ((long long)ANS * __Base_ % __Mod_ + __Hash_char( _str[ i])) % __Mod_;
    }
    return ANS;
}

template< int _MaximumLength> class __HashSubStrings{
public:
    int __PrefixSum[ _MaximumLength];
    int Power[ _MaximumLength];
    int __Length;

    __HashSubStrings(){}
    void Initialize( const char * _str, int _length){
        __Length = _length;
        __PrefixSum[ 0] = __Hash_char( _str[ 0]), Power[ 0] = 1;
        for( int i = 1; i < __Length; ++i){
            __PrefixSum[ i] = ((long long)__PrefixSum[ i - 1] * __Base_ % __Mod_ + __Hash_char( _str[ i])) % __Mod_;
            Power[ i] = (long long)Power[ i - 1] * __Base_  % __Mod_;
        }
    }
    int Get_hash( int _left, int _right){
        ASSERT_( (_left >= 0) && (_left <= _right) && (_right < __Length));
        int ans = __PrefixSum[ _right];  if( _left != 0){ ans = ((ans - (long long)__PrefixSum[ _left - 1] * Power[ _right-_left + 1] % __Mod_) + __Mod_) % __Mod_;}
        return ans;
    }
}; // __HashSubStrings
} // __HashString
__HashString::__HashSubStrings< @TODO> HashSubStrings;
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
30
31
32
33
34
35
36
37
38
39
40
41
42

性質

如果哈希冲突了, 将1e9 + 7改为1e9 + 21;

@DELI;

這個int Mod_, 你不能把他設置成一個long long的數, 這就錯誤了, 因為會導致溢出 (兩個long long的乘積 溢出);
. 只有說 你把Mod_給去掉 改為對unsigned long long自然溢出, 此時 溢出是正確的 (因為溢出 就相當於對2^64取模);

例題

獲取字符串的前後綴拼接的哈希值

對於S: "abcdef", 獲取其(後綴+前綴)的字符串的哈希值;
比如要得到efabcd這個字符串的哈希值 令暴力算法O(N)得到的結果為H(即E*Base^n + F*... + D), 而實際上 你可以通過O(1)獲得他的哈希值: 令A:S.Get_hash(4,5); B:S.Get_hash(0,3), 即A為ef的哈希值(E*Base + F) B為abcd的哈希值(A*Base^3 + ... + D), 則efabcd的哈希值為 A * Power[4] + B == H;

例题: @LINK: https://editor.csdn.net/md/?not_checkout=1&articleId=132818193;

筆記

原理: 两个不同的P进制数, 他对应的十进制数, 是不同的;

假如P = 26, 两个P进制数: (a1) (a2) (a3) 和 (b1) (b2) (b3)
如果存在: ai != bi, 那么其对应的10进制数, 即(a1 * P^2 + a2 * P + a3)是不同的

这就像是, 假如P为熟悉的十进制, 那么(012) 和 (022)是不同的;

因此, 对于一个P进制数(也可以看做是一个P进制字符串), 他所对应的十进制数, 就称为他的(哈希值)

基于此, 假如一个字符串有P个不同的字符, 则对应一个P进制, 每个字符映射到[0, P)之中
由于其对应的十进制数, 会爆出LL, 需要使用取模操作;

取模哈希(探测法|拉链法)

性质

需求: 对unordered_map/unordered_set的效率上的优化;
换句话说, 探测法|拉链法 都可以被(STL容器)所替代, 只不过 他效率更高;
. 即, 维护一个整数集合S, 然后有一些操作{查询某个整数是否在S里, 向S里添加一个整数, …}

@DELI;

給定$N$個整數$a$(可以是負數), 選擇一個$>N$的質數$P$, 定義數組T map[ P] 初始都置為Invalid(確保所有$a\ne Invalid$), 對於a=map[b]: @IF(a!=Invalid)[a的哈希值為b], @ELSE[沒有元素的哈希值為b]; 即 任意兩個數 他倆的哈希值必須要保證是不同的;

哈希算法:
令init = (a%P+P)%P非負餘數 作為a的初始哈希值, 顯然 對於$a+k\ast P$這些數 他們的初始哈希值 都是相同的, 即出現了 哈希衝突;

哈希衝突:
1(拉鏈法): 將map變成vector< T> map[ P], 即對於衝突的元素 都放到map[ init]裡面去 來區分他們;
缺點:
. 1: 此時a的哈希值 不再是一個[0,P)的整數, 而是2個數{h1, h2} 表示a在map[ h1][ h2]這個位置, 這不好 假如我們希望他的哈希值是[0, P)範圍的;
. 2: 假如所有數都是a + k*P, 顯然此時 時間變成了$O(N)$, 超時了;
2(探測法): 為了讓a的哈希值 是一個[0, P)的整數 就不能使用上述的鏈錶, 依次的查詢x = [a/ a+(1*1)/ a+(2*2)/ a+(3*3)/ ...]的%P的非負餘數 如果map[x] = Invalid 那麼當前數的哈希值為x; 且要讓$P>2\ast N$ 即讓P比較大;
缺點: 大多數情況沒問題, 但是跟上面的2:一樣 假如所有數都是a + k*P 此時同樣是退化到$O(N)$超時;
. 解決辦法: 再哈希, 樸素做法是a + k*k 將他變成a + k*L 其中L = a%PP PP為的質數;

class __Hash_Modular{
//< 取模哈希 對整數(可以是負數)進行哈希 得到一個`>=0`的哈希, 他可以完全被`Map< Type,int>`所替代 只不過後者是$O(\log{N})$ 而取模哈希是接近$O(1)$的;
//  . 當`@LINK:@LOC_0`發生, 說明衝突次數太多了, 可以增大`__MaxDetectionCount_` 但這不是好辦法, 最好是可以考慮*再哈希* 即將探測`k*k`改為`k*L` L為`_a % 99991`;
public:
    using Type_ = @TODO; // 必須是*整數*類型;
    static constexpr int __Modular_ = @TODO; // [ 100003, 500009, 1000003, 5000011, 10000019, 50000017];
    //< `N: 要進行哈希的元素個數`, 確保`Modular_ > 2*N`;
    static constexpr Type_ __Invalid_ = INT64_0x80; // 確保所有要進行哈希的元素 都不會等於該值;
    static constexpr int __MaxDetectionCount_ = 202; // 二次檢測的最大次數 (也對應`Add/Get_hash`函數的最大時間複雜度);
    Type_ __Map[ __Modular_]; // `a=Map[b]`: @IF(a!=`Invalid`)[a的哈希值為b], @ELSE[暫時還沒有元素的哈希值為b]
   
    __Hash_Modular(){}
    void Initialize(){
        memset( __Map, 0x80, sizeof( __Map));
    }
    int Add( Type_ _a){ // 返回值為 `a`的哈希值;
        ASSERT_WEAK_( _a != __Invalid_);
        int init = _a % __Modular_;  if( init < 0){ init += __Modular_;}
        if( __Map[ init] == __Invalid_){ __Map[ init] = _a; return init;}
        else if( __Map[ init] == _a){ return init;}

        for( int k = 1; k <= __MaxDetectionCount_; ++k){
            int id = (init + k * k) % __Modular_;
            if( __Map[ id] == __Invalid_){ __Map[ id] = _a; return id;}
            else if( __Map[ id] == _a){ return id;}
        }
        ASSERT_( 0); // @MARK:@LOC_0
        return -1;
    }
    int Get_hash( Type_ _a){
    //< 返回值: @IF(`!= -1`)[表示a的哈希值 說明其之前調用過`Add`函數] @ELSE[該元素不存在];
        ASSERT_WEAK_( _a != __Invalid_);
        int init = _a % __Modular_;  if( init < 0){ init += __Modular_;}
        if( __Map[ init] == __Invalid_){ return -1;}
        else if( __Map[ init] == _a){ return init;}

        for( int k = 1; k <= __MaxDetectionCount_; ++k){
            int id = (init + k * k) % __Modular_;
            if( __Map[ id] == __Invalid_){ return -1;}
            else if( __Map[ id] == _a){ return id;}
        }
        ASSERT_( 0); // @MARK:@LOC_0
        return -1;
    }
}; // class __Hash_Modular
__Hash_Modular Hash_Modular;
@TODO( Hash_Modular.Initialize());
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

int Get_hash( int _key){
    int init = _key % Hash_size_;
    int id;
    for( int k = 0; k < 10000; ++k){
        id = (init + k * k) % Hash_size_;
        if( ( Hash_key[ id] == Hash_invalid) || (Hash_key[ id] == _key)){
            Hash_key[ id] = _key;
            return id;
        }
    }
    ASSERT_( 0);
    return id;
}
1
2
3
4
5
6
7
8
9
10
11
12
13