5

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

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

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

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

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

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

struct posting
{
    string word;
    posting *next
}

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

2 回答 2

4

散列可以按照您的选择进行。假设字符串是 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) 函数。它将直接返回数组的索引:)

于 2013-04-15T13:44:20.897 回答
1

哈希表可以实现为简单的二维数组。问题是如何计算要存储的每个项目的唯一键。有些东西在数据中内置了键,而对于其他东西,您必须计算一个:上面建议的 MD5 可能正好满足您的需求。

您需要解决的下一个问题是如何布局或调整哈希表的大小。您最终需要通过一些测试来调整自己的需求。您可以从设置数组的第一个维度开始,其中包含 255 个条目——一个用于 MD5 哈希的前 2 位数字的每个组合。每当发生碰撞时,您都会在数组的第 2 维索引处的第 1 维索引处添加另一个条目。这意味着您将静态定义一维数组,同时根据需要动态分配二维条目。希望这对你和我一样有意义。

在进行查找时,您可以立即使用 MD5 哈希的第 2 位找到正确的第 1 维索引。然后沿着二维的相对短线性搜索将快速将您带到您寻找的项目。

您可能会从实验中发现,如果您的数据集足够大,使用更大的第一维(使用 MD5 哈希的前 3 位)会更有效。根据所涉及文本的大小以及它们对词典的使用分布,您的结果可能会决定您的一些架构。

另一方面,您可能只是从小处着手,并构建一些智能来自动调整表格的大小和布局。如果您的桌子在任一方向上都变得太长,性能就会受到影响。

于 2013-04-15T17:22:30.743 回答