BKDR字符串哈希

bkdrhash冲突的可能性非常小，但是由于\(hash\)值非常大不能映射到哈希数组地址上，所以可以通过取余，用余数作为索引地址。但这样做造成了可能的地址冲突。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

const int maxn = 10005;

char s[maxn];

unsigned int hash(const char *key) {

	char *str = const_cast<char*>(key);

	unsigned int seed = 131; // 31 131 1313 13131 131313 etc..

	unsigned res = 0;

	while (*str) {

		res = res * seed + (*str++);

	}

	return res;

}

int main() {

	int n;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {

		scanf("%s", s);

		unsigned int res = hash(s);

		printf("%u\n", res);

	}

	return 0;

}

巴特西

BKDR字符串哈希

BKDR字符串哈希

bkdrhash冲突的可能性非常小，但是由于\(hash\)值非常大不能映射到哈希数组地址上，所以可以通过取余，用余数作为索引地址。但这样做造成了可能的地址冲突。

最新文章

热门文章