c++ hash算法

以下是C++中常用的两种哈希算法：

1.除留余数法

除留余数法是一种简单的哈希算法，它的实现方式是将关键字除以某个不大于哈希表长度的数，然后取余数作为哈希地址。具体实现如下：

int hash(int key, int size) {
    return key % size;
}

2.字符串哈希算法

字符串哈希算法是将字符串转换为一个整数，然后再进行哈希。常用的字符串哈希算法有BKDR Hash、AP Hash、DJB Hash等。以下是BKDR Hash的实现代码：

size_t BKDRHash(const char* str) {
    size_t seed = 131; // 31 131 1313 13131 131313 etc..
    size_t hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return hash;
}

相关问题

c++ 实现Geohash算法

Geohash是一种将地理位置编码为字符串的方法，它可以将一个点的经纬度坐标编码为一串字符串。以下是C++实现Geohash算法的示例代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;

char base32[] = "0123456789bcdefghjkmnpqrstuvwxyz";
map<char, int> mp;

void init() {
    for (int i = 0; i < 32; i++) mp[base32[i]] = i;
}

string Encode(double lat, double lng, int len) {
    double lat_left = -90, lat_right = 90, lng_left = -180, lng_right = 180;
    string res;
    while (len--) {
        int tmp = 0;
        for (int i = 0; i < 5; i++) {
            double mid_lat = (lat_left + lat_right) / 2;
            double mid_lng = (lng_left + lng_right) / 2;
            if (lng > mid_lng) {
                tmp = tmp * 2 + 1;
                lng_left = mid_lng;
            } else {
                tmp = tmp * 2;
                lng_right = mid_lng;
            }
            if (lat > mid_lat) {
                tmp = tmp * 2 + 1;
                lat_left = mid_lat;
            } else {
                tmp = tmp * 2;
                lat_right = mid_lat;
            }
        }
        res += base32[tmp];
    }
    return res;
}

int main() {
    init();
    double lat, lng;
    int len;
    scanf("%lf %lf %d", &lat, &lng, &len);
    printf("%s\n", Encode(lat, lng, len).c_str());
    return 0;
}

其中，函数`Encode`接受一个经度坐标`lat`和一个纬度坐标`lng`，以及指定的编码长度`len`，返回一个字符串表示的Geohash编码。

具体实现过程如下：

1. 初始化`base32`字符数组和`mp`映射表，用于字符转数字和数字转字符。

2. 初始化`lat_left`、`lat_right`、`lng_left`、`lng_right`四个变量，分别表示纬度和经度的范围，初始值为全球范围。

3. 循环`len`次，每次取前5位进行编码。对于每一位，将经度和纬度的范围二分，根据经度和纬度的大小关系，决定当前位的值。将这5位的值转换为对应的字符，拼接到结果字符串中。

4. 返回结果字符串。

示例：

输入：

39.9087 116.3975 6

输出：

wx4g0j

该输出表示经度为116.3975，纬度为39.9087的点的Geohash编码为"wx4g0j"，编码长度为6。

c++使用hash算法实现字符串匹配

C++中使用hash算法实现字符串匹配，可以采用Rabin-Karp算法。

该算法的基本思想是：将模式串和文本串都看作是一个进制为d的数，通过哈希函数将它们映射为一个整数。由于哈希函数的映射是唯一的，因此只要哈希值相等，就说明模式串和文本串可能相等。因此在比较之前，先比较它们的哈希值，若相等则说明它们可能相等，再逐个比较字符。

具体实现如下：

#include <iostream>
#include <string>

using namespace std;

const int BASE = 131; // 哈希函数的基数
const int MOD = 1e9 + 7; // 哈希函数的模数

int Hash(string s) // 哈希函数
{
    int res = 0;
    for (int i = 0; i < s.length(); i++) {
        res = ((long long)res * BASE + s[i]) % MOD;
    }
    return res;
}

int main()
{
    string text, pattern;
    cin >> text >> pattern;

    int patternHash = Hash(pattern); // 计算模式串的哈希值

    int textHash = 0;
    int t = 1;
    for (int i = 0; i < pattern.length(); i++) {
        textHash = ((long long)textHash * BASE + text[i]) % MOD; // 计算初始文本串的哈希值
        t = ((long long)t * BASE) % MOD;
    }

    for (int i = 0; i + pattern.length() <= text.length(); i++) {
        if (textHash == patternHash && text.substr(i, pattern.length()) == pattern) {
            cout << "Pattern found at index " << i << endl;
        }
        if (i + pattern.length() < text.length()) {
            textHash = ((long long)textHash * BASE - (long long)text[i] * t % MOD + MOD) % MOD; // 更新文本串的哈希值
            textHash = ((long long)textHash + text[i + pattern.length()]) % MOD;
        }
    }

    return 0;
}

该算法的时间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度。