C++中用于字符串的哈希表

Question

C++中用于字符串的哈希表

5

我之前做过一个有关哈希表的小练习，但用户输入的是数组大小，数据结构如下所示（所以每次用户输入的是一个数字和一个单词）。

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

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

对用户给我的键进行哈希
在数组中找到array[hashed(key)]的位置
如果它是空的，我就把数据放在那里
如果不是空的，我就把它放在下一个可用的位置。

但现在我要制作倒排索引，我正在研究如何为其创建哈希表。所以这些单词将从大约30个txt文件中收集起来，数量很多。

在这种情况下，数组应该有多长？我如何对单词进行哈希？我应该使用开放地址哈希还是链式哈希？练习说如果我们在网上找到了哈希表，我们可以直接使用它。但我更喜欢理解并自己创建它。任何线索都会有帮助：）

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

struct posting
{
    string word;
    posting *next
}

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

- captain monk

请查看聊天菜单 :) - Binayaka Chakraborty

2个回答

1

哈希表可以实现为简单的二维数组。问题是如何计算要存储的每个项的唯一键。有些东西已经内置了键，对于其他东西，您需要计算一个键：如上所建议的MD5可能非常适合您的需求。

下一个问题需要解决的是如何布局或调整哈希表的大小。这是通过一些测试最终需要根据自己的需求进行调整的。您可以通过设置数组的第一个维度为255个条目来开始-每个MD5哈希的前两个数字的组合中的一个。每当发生冲突时，您都会在该第一个维度索引处添加第二个维度的另一个条目。这意味着您将静态定义一个一维数组，同时根据需要动态分配第二维度条目。希望这让您感到像我一样清晰明了。

在查找时，您可以立即使用MD5哈希的前两个数字找到正确的第一个维度索引。然后，沿着第二个维度进行相对较短的线性搜索将迅速带您到所需的项。

你可能会通过实验发现，如果你的数据集足够大，使用更大的第一维（使用MD5哈希的前三个数字）更有效率。根据所涉及的文本大小和其对词汇表的使用分布，你的结果很可能会决定一些架构。

另一方面，你可能只是从小处开始，并建立一些智能来自动调整和布局你的表格。如果你的表格在任何一个方向上变得太长，性能将会受到影响。

- alpartis

谢谢您，这确实有点启发性。您建议使用带链式解决冲突的散列表。我不明白的是例如MD5HASH（“凯撒”）返回b712916d8bfc1718a431c7b4fa280ae6，所以它返回的前2个字符是b7，对吗？这意味着我将转到array [b7]的位置吗？如果我问得太蠢了，请原谅，但我仍然对b712916d8bfc1718a431c7b4fa280ae6感到困惑，因为在我的其他练习中，它只返回小于数组大小的数字，所以我只需要转到array[number]。 - captain monk

1

是的，我建议使用链式哈希表。可以将哈希数组中的每个条目视为一个桶，其中包含与给定哈希计算冲突/绑定的动态增长项目集合。回答您的问题：是的，在您的示例中，您会将“caesar”的条目放入“bucket”哈希数组[b7]中。 - alpartis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Binayaka Chakraborty · Accepted Answer

哈希可以按照您选择的任何方式进行。假设字符串是ABC。您可以将A = 1，B = 2，C = 3作为哈希算法，哈希值=1 + 2 + 3 /（长度= 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)函数。它会直接返回数组的索引 :)