如果我要存储100000个11位的数字应该用什么哈希函数
时间: 2024-02-22 13:55:14 浏览: 19
哈希函数的好坏直接影响哈希表的性能,因此需要选择一个合适的哈希函数。对于要存储100000个11位的数字的情况,可以考虑以下这个简单的哈希函数:
1. 直接取模法:将11位数字转换成整数,然后对一个较大的质数取模,得到的结果就是哈希表的下标。具体实现如下:
```
int hash_func(long long key) {
int prime = 99991; // 取一个较大的质数作为模数
return key % prime;
}
```
这个哈希函数的思想很简单,就是将数字对一个较大的质数进行取模,使得哈希值的范围在0到prime-1之间。这种方法比较简单,而且实际效果也很不错。但是需要注意的是,质数的选取需要尽可能地大,这样可以使得哈希值的分布更加均匀。
2. 乘法哈希法:乘法哈希法是一种常用的哈希函数,它将关键字乘以一个小数k,然后取整得到哈希值。具体实现如下:
```
int hash_func(long long key) {
double k = 0.618; // 取一个介于0到1之间的小数作为乘数
int m = 100000; // 哈希表的大小
return (int)(m * fmod(key * k, 1.0));
}
```
这个哈希函数的思想是将关键字乘以一个小数k,然后取整得到哈希值。小数k的选取需要遵循一定的规则,一般取一个介于0到1之间的值,比如0.618。同时,哈希表的大小也需要事先确定,这里假设哈希表的大小为100000。这种方法相对于直接取模法来说,具有更好的随机性和更均匀的哈希分布。
综上所述,对于要存储100000个11位的数字的情况,可以考虑使用直接取模法或者乘法哈希法。需要注意的是,哈希函数的选取需要根据实际情况进行调整,以达到更好的哈希性能。