散列可以按照您的选择进行。假设字符串是 ABC。您可以使用散列作为 A=1, B=2, C=3, Hash = 1+2+3/(length = 3) = 2。但是,这是非常原始的。
数组的大小将取决于您部署的散列算法,但最好选择为每个字符串返回确定长度散列的算法。例如,如果您选择使用 SHA1,您可以安全地为每个哈希分配 40 个字节。请参阅在 MySQL 中存储 SHA1 哈希值阅读算法http://en.wikipedia.org/wiki/SHA-1。我相信它可以安全地使用。
另一方面,如果只是为了简单的练习,也可以使用 MD5 散列。我不建议在实际用途中使用它,因为它的彩虹表很容易获得:)
- - - - -编辑 - - - -
您可以尝试像这样实现::
#include <iostream>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#define MAX_LEN 30
using namespace std;
typedef struct
{
string name; // for the filename
... change this to your specification
}hashd;
hashd hashArray[MAX_LEN]; // tentative
int returnHash(string s)
{
// A simple hashing, no collision handled
int sum=0,index=0;
for(string::size_type i=0; i < s.length(); i++)
{
sum += s[i];
}
index = sum % MAX_LEN;
return index;
}
int main()
{
string fileName;
int index;
cout << "Enter filename ::\t" ;
cin >> fileName;
cout << "Enter filename is ::\t" + fileName << "\n";
index = returnHash(fileName);
cout << "Generated index is ::\t" << index << "\n";
hashArray[index].name = fileName;
cout << "Filename in array ::\t" <<hashArray[index].name ;
return 0;
}
然后,要实现 O(1),只要您想获取文件名的内容,只需运行 returnHash(filename) 函数。它将直接返回数组的索引:)