c ++中字符串的哈希表

Question

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

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

所以它非常简单,因为我知道数组大小,并且用户也说他将提供多少项作为输入.我这样做的方式是

• 哈希用户给我的钥匙
• 在数组中找到位置数组[hashed(key)]
• 如果它是空的我会把数据放在那里
• 如果不是我会把它放在下一个自由位置,我会发现.

但现在我必须制作倒排索引,我正在重新研究,所以我可以为它制作哈希表.因此,这些单词将从大约30个字节收集,并且它们将是如此之多.那么在这种情况下阵列需要多长时间？我怎么哈希的话？我应该使用开放地址或链接的哈希.练习sais我们可以使用哈希表,如果我们在网上找到它.但我更喜欢自己理解并创造它.任何线索都会帮助我:)

在这个exerice(使用哈希表的反向索引)中,结构看起来像这样.data type是我将创建的哈希表的类型.

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 个字节。请参阅在 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) 函数即可。它将直接返回数组的索引:)