Chinaunix

标题: 请教一个关于Hash算法中除留余数的问题 [打印本页]

作者: bluetune 时间: 2006-10-17 11:39
标题: 请教一个关于Hash算法中除留余数的问题
昨天在用代码实现一个hash算法的时候，突然想到，为什么除留余数法中除数要用质数？虽然各种教科书上都说质数可以减少地址冲突，但为什么会这样？我写了一小段代码，测试了一下，结果是除数是不是质数都没关系。为简单，桶数和除数是一样的。很困惑，请高手指点。
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef vector<int> vInt;

int main()
{
int BucketNum = 10;
int tmpBucketNum;
vector<vInt *> vBuckets;
vInt *pvInt, *ptvInt;
vector<int>::iterator iterInt;

for (int i=0; i<BucketNum; i++)
{
pvInt = new vInt;
vBuckets.push_back(pvInt);
}

for (int i=0; i<100; i++)
{
tmpBucketNum = i%BucketNum;
ptvInt = vBuckets[tmpBucketNum];
(*ptvInt).push_back(i);
}

for (int i=0; i<BucketNum; i++)
{
cout << endl << "*******Bucket:" << i << endl;
ptvInt = vBuckets[i];

for (iterInt=(*ptvInt).begin(); iterInt < (*ptvInt).end(); iterInt ++)
{
cout << *iterInt << "\t";
}
}

return 0;
}

作者: bluetune 时间: 2006-10-17 15:43
标题: 自己顶--测试结果
*******Bucket:0
0    10    20    30    40    50    60    70    80    90
*******Bucket:1
1    11    21    31    41    51    61    71    81    91
*******Bucket:2
2    12    22    32    42    52    62    72    82    92
*******Bucket:3
3    13    23    33    43    53    63    73    83    93
*******Bucket:4
4    14    24    34    44    54    64    74    84    94
*******Bucket:5
5    15    25    35    45    55    65    75    85    95
*******Bucket:6
6    16    26    36    46    56    66    76    86    96
*******Bucket:7
7    17    27    37    47    57    67    77    87    97
*******Bucket:8
8    18    28    38    48    58    68    78    88    98
*******Bucket:9
9    19    29    39    49    59    69    79    89    99

作者: bluetune 时间: 2006-10-17 17:52
标题: 自己顶--从测试结果看，不是质数也可以使数据分布得很均匀
不明白为什么教科书里要求用质数

作者: bluetune 时间: 2006-10-18 08:46
标题: 自己顶--真的没人知道吗?
??

作者: bluetune 时间: 2006-10-18 11:49
标题: 自己顶--找到结果了
http://jpkc.ncwu.edu.cn/sjjg/new/content/ch8/ch8-03-05.htm
其实比较关键的是处理的数据，我本来以为示例代码的数据够散了，但实际应用中的数据是多种多样的，很有可能有大量包含同因子的数据，因此选择质数是必要的。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)