Geek asks and answers

Hash table for strings in C ++

In the past, I did a little exercise about the hash table, but the user specified the size of the array, and the structure was like that (so the user each time entered a number and a word as input)

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

So, it was pretty simple, since I knew the size of the array, and also the user said how many items he would give as input. The way I did it was

  • Storing the keys that the user gave me
  • find the array of position [hashed (key)] in the array
  • If it were empty, I would put the data there
  • If this were not so, I would put him in the next free position that I would find.

But now I need to make an inverted index, and I'm doing a search, so I can make a hash table. Thus, words will be collected from approximately 30 txts, and there will be so many. So in this case, how long should the array be? How can I hash words? Should I use hasing with an open address or chaining. In the exercise, we can use the hash table as if we were to find it on the Internet. but I prefer to understand and create it myself. Any hints will help me :)

In this exerice (inverted index using a hash table), the structures are as follows. the data type is the type of hash table that I will create.

struct posting
{
    string word;
    posting *next
}

struct data
{
    string word;
    posting *ptrpostings;
    data *next
};
+5
source share
2 answers

. , ABC. A = 1, B = 2, C = 3, Hash = 1 + 2 + 3/(length = 3) = 2. .

, , , . , SHA1, 40 . . - SHA1 MySQL. http://en.wikipedia.org/wiki/SHA-1. , .

, , MD5. , :)

--------- EDIT -------

:

#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). :)

+3

- . , , . , , : MD5, , , .

, , - -. , . 1- 255 - MD5. , , 1- . , 1- 2- . , , .

1- , 1- 2- MD5. , .

, 1- ( 3- MD5), . , , .

, - , . , .

+1

More articles:


All Articles