c++ - C++中字符串的哈希表

Question

我过去做过一个关于哈希表的小练习，但是用户给出了数组大小，而且结构也是这样的(所以用户每次都给出一个数字和一个单词作为输入)

struct data
{
   int key;
   char c[20];
};

所以这很简单，因为我知道数组大小，而且用户说他将提供多少项作为输入。我的做法是

• 散列用户给我的 key
• 在数组中找到位置array[hashed(key)]
• 如果它是空的我会把数据放在那里
• 如果不是，我会把它放在我能找到的下一个空闲位置。

但是现在我必须制作倒排索引并且我正在重新搜索以便我可以为它制作一个哈希表。所以这些词将从大约 30 个 txt 中收集，而且会很多。那么在这种情况下，数组应该有多长？我如何散列单词？我应该使用带有开放寻址的 hasing 还是带有链接。练习说如果我们在网上找到它，我们可以按原样使用哈希表。但我更喜欢自己理解和创造它。任何线索都会帮助我:)

在这个练习(使用哈希表的倒排索引)中，结构看起来像这样。数据类型是我将创建的哈希表的类型。

struct posting
{
    string word;
    posting *next
}

struct data
{
    string word;
    posting *ptrpostings;
    data *next
};

Answer 1

散列可以按照您选择的任何方式进行。假设字符串是 ABC。您可以使用散列作为 A=1、B=2、C=3、Hash = 1+2+3/(length = 3) = 2。但是，这是非常原始的。

数组的大小将取决于您部署的散列算法，但最好选择为每个字符串返回确定长度散列的算法。例如，如果您选择使用 SHA1，则可以安全地为每个哈希分配 40 个字节。引用Storing SHA1 hash values in MySQL阅读算法 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) 函数即可。它会直接返回数组的索引:)