6.2 哈希冲突 - Hello 算法 (hello-algo.com)

哈希表 hash_table

#include <unordered_map>
​
unordered_map<string,int> mp;
​
mp["111"] = 11;
mp["11"] = 14;
mp["1"] = 13;
mp["121"] = 12;
​
mp.erase("121");//delete
​
​
​
​
// 遍历哈希表 
​
//智能指针
for(auto i:mp){
    cout << mp.first<<" "<<mp.second<<endl;
}
//迭代器
for(auto i=mp.begin();i!=mp.end();i++){
    cout << i->first<<' '<< mp->second << endl;
}
​

哈希表实现将一个较大的哈希函数映射到较小的数据空间 通过哈希函数将值存到相应的索引位置

一般简单的哈希函数可以为

index = hash(key) % capacity

查找删除键值时通过哈希函数直接访问目标值

使用数组简单 实现hash表

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
​
struct Pair
{
    int key;
    string val;
    Pair(int key,string val){
        this->key = key;
        this->val = val;
    }
};
/// 基于数组实现的hash表
​
​
class ArrayHashMap
{
private:
    vector<Pair*> buckets;  // 水桶
    const int HashKey = 100;
public:
    ArrayHashMap(/* args */);
    ~ArrayHashMap();
    int hashFunc(int key);
    string get(int key);
​
    void put(int key,string val);
    void erase(int key);
    vector<int> getAllVal();
    vector<string> getAllKey();
    void printHashTable();
};
​
ArrayHashMap::ArrayHashMap(/* args */)
{
    buckets = vector<Pair*>(100);
}
​
ArrayHashMap::~ArrayHashMap()
{
    for(const auto &bucket:buckets){
        delete bucket;
    }
    buckets.clear();
}
​
int ArrayHashMap::hashFunc(int key)
{
    return key % HashKey;
}
​
string ArrayHashMap::get(int key)
{
    Pair *par = buckets[hashFunc(key)];
    if(par == nullptr)return "";
    return par->val;
}
​
void ArrayHashMap::put(int key, string val)
{
    Pair *pir = new Pair(key,val);
    buckets[hashFunc(key)] = pir;
}
​
void ArrayHashMap::erase(int key)
{
    int k = hashFunc(key);
    delete buckets[k];
    buckets[k] = nullptr;
}
​
vector<int> ArrayHashMap::getAllVal()
{
    vector<int> res;
    for(auto c:buckets){
        if(c!=nullptr)
            res.push_back(c->key);
    }
    return res;
}
​
vector<string> ArrayHashMap::getAllKey()
{   
    vector<string> res;
    for(auto c:buckets){
        if(c!=nullptr)
            res.push_back(c->val);
    }
    return res;
}
​
void ArrayHashMap::printHashTable()
{
    for(auto c:buckets){
        cout << c->key << "  " << c->val << endl; 
    }
}
​
int main(){
​
    ArrayHashMap c;
​
    c.put(123,"123");
    c.put(12333,"12333");
    c.put(123333,"123333");
    c.put(123444,"123444");
​
    // c.printHashTable();
​
    cout << c.get(1233) << endl; // hash冲突
​
    return 0;
}

冲突处理

存储哈希值的方法 开放寻址法 拉链法

• 开放寻址法//一个数组

• 当发生冲突时，通过一定的方法在哈希表中寻找下一个可用的位置来存储键值对

• 拉链法 // 链表

• 每个索引位置都是一个链表用于存储多个键值

  当出现冲突时候会以链表的形式连接在一起

一般%的数一般为大于目标范围最大的质数

良好的哈希表素数 (planetmath.org)

1. 1.

   列表中的每个数字都是质数

2. 2.

   每个数字的大小略小于前一个数字的两倍

3. 3.

   每个数字都尽可能远离

   最接近的二次方

普通哈希

• 拉链

const int N = 1e5;
int h[N],e[N],ne[N],idx = 0; // 拉链 h[] = {-1}
​
// 向哈希表中
void insert(int x){
    int k = (x%n+n)%n;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}
​
// 查找是否在hash表中
bool find(int x){
    int k = (x%n+n)%n;
    for(int i=h[k];~i;i = ){
        int b = e[i];
        if(e[i] == x)return true;
    }
    
    return false;
}

• 开放寻址法

int h[N*3];
​
 // 有就返回x的下表 
//没有返回插入hash的位置
int find(int x){
    int h = (x%n+n)%n;
    while(h[t]!=null&&h[t]!=x){ //null为自己设置的最大值
        t ++;
        if(t == n)t = 0;
    }
    return t;
}
​
//插入 
h[find(x)] = x;

字符串hash

• 将字符串看作p进制数（p一般为131 / 13331）冲突概率低

• 直接使用unsigned long long 存储，溢出就是取模的结果

typedef unsigned long long ULL; // 定义无符号长长整型 ULL
​
ULL h[N], p[N]; // 哈希数组 h 和权值数组 p
​
p[0] = 1; // 初始权值为 1
​
// 计算哈希数组和权值数组
for (int i = 1; i <= n; i++) {
    h[i] = h[i - 1] * P + str[i]; // 计算哈希数组
    p[i] = p[i - 1] * P; // 计算权值数组，P 进制
}
​
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1]; // 返回子串哈希值
}

矩阵hash

1402. 星空之夜 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cmath>
​
using namespace std;
​
const int N = 110;
​
char g[N][N];
pair<int,int> q[N*N];
​
double eqs = 1e-5; // 定义误差范围
int n,m;
​
int top;
​
​
double get_dist(pair<int,int> a, pair<int,int> b){
    // 计算两点之间的欧氏距离
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx*dx + dy*dy);
}
​
double get_hash(){
    // 计算哈希值
    double sum = 0;
    for (int i = 0; i < top; i++)
        for (int j = i + 1; j < top; j++)
            sum += get_dist(q[i], q[j]); // 累加两点之间的距离
    return sum;
}
​
char get_id(double key){
    // 获取哈希值对应的字符标识
    static double hash[30]; // 哈希表，存储哈希值
    static int id = 0; // 标识当前哈希表中的位置
    for(int i = 0; i < id; i++){
        if(fabs(hash[i] - key) < eqs){ // 如果当前哈希值与已有哈希值之差在误差范围内
            return i + 'a'; // 返回对应的字符标识
        }
    }
    hash[id++] = key; // 将当前哈希值加入哈希表
    return id - 1 + 'a'; // 返回对应的字符标识
}
​
void dfs(int a, int b){
    // 深度优先搜索，标记连通分量
    q[top++] = {a, b}; // 将当前点加入队列
    g[a][b] = '0'; // 标记当前点已访问
    for(int x = a - 1; x <= a + 1; x++){
        for(int y = b - 1; y <= b + 1; y++){
            if(x == a && y == b) continue;
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1'){
                dfs(x, y); // 继续搜索相邻的未访问点
            }
        }
    }
}
​
int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i++){
        cin >> g[i];
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(g[i][j] == '1'){
                top = 0;
                dfs(i, j); // 搜索连通分量
                char c = get_id(get_hash()); // 获取哈希值对应的字符标识
                for(int k = 0; k < top; k++){
                    g[q[k].first][q[k].second] = c; // 将连通分量内的所有点标记为同一字符
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        cout << g[i] << endl; // 输出标记后的地图
    }
    
    return 0;
}