1

It might be too early on for me to ask questions in this problem set, as I am just getting started with load. I was looking up Hash Functions, and they look a little cryptic to me. Is it possible to pass a string to a hash table that is a 3D array (int hashtable[27][27[27]), then use a linked list for collisions on the third order (letter)? Or is a hash table actually a constant int, and therefore cannot be a simple array of values, unless I used some sort of multiplier for the first , second, and third letter that would distinguish the order in which they were applied.

So for example, could I nest hash tables so that

int hashtable[27][27][27]

would put the word "dog" at {4, 16, 7}

Or could I hash it to 7164 (or whatever number structure would be the most efficient)

Sorry if this makes no sense, I'm really struggling with understanding how to implement a hash function and what it can be used for.

UPDATE

I went with writing the following 'hash function' which has some of the features of a 3D array (it tracks the index # of columns plus rows, plus "depth"), but breaks the word down into smaller chunks of 3 letters, and then adds those chunks together to get the index for the word. It actually uses a 4D feature for the first letter, to separate the index roughly numbers into groups of 26 for words four letters or more.

unsigned long add_hash (void *key, int length)
{
    // Copy word into pointer variable.
    unsigned char *p = key;
    unsigned x = 0;
    unsigned long h = 0;

    // For words up to four letters, mark their order and add them together.
    if (length < 5)
    {
        for (int i = 0; i < length; i++)
        {
            // Account for punctuation.
            if (p[i] == '\'')
            {
                x = pow(28,  i);
                h += ((27 - 'a' + 1)* x);    
            }        
            else    
            {    
                x = pow(28,  i);
                h += ((p[i] - 'a' + 1)* x);
            }
        }    
    }

    // For longer words, recursively fold them into groups of three letter, making a new 'alphabet' with 7,000 letters.
    else
    {
        // Move backwards from the end to help distinguish similar words of different length.
        int i = length - 1;
        while (i > 0)
        {    
            for (int j = 0; j < 3; j++)
            {
                if (i == 0)
                {
                    j = 3;
                    continue;
                }
                // Account for punctuation.
                else if (p[i] == '\'')
                {
                    x = pow(28, j);
                    h += ((27 - 'a' + 1)* x);    
                }   
                else
                {    
                    x = pow(28, j);
                    h += ((p[i] - 'a' + 1) * x);
                }
                i--;
            } 
        }

        // Possible combinations are reduced according the first letter.
        h += (pow(28, 3) * (p[0] - 'a' + 1));
    }

    // Keep the index within the 'Hastable' range.
    h = h & HASHTABLE;

    // Return the word's index number.
    return h;
}

It works, I'm not sure how good it is. I'm open to improving it!

1

In an abstract kind of way, you could. A hash method consists of a hash() function, that maps keys to a set of hash values. So, you need two things:

  • a deterministic hash() function (i.e.: for a certain key it consistently produces the same hash value every time)

  • a "table" where to store those key-value pairs.

How you implement such table is up to you.

A simpler example: you could define your hash table to be a 2D array, and your hash() function to map the first two letters of every string to row/column respectively. To simplify, assume we only have 4 letters in the abecedary:

    a   b   c   d
a   1   2   3   4
b   5   6   7   8
c   9  10  11  12
d  13  14  15  16

In such case, this would happen:

hash("bat") -> 5
hash("bad") -> 5
hash("cat") -> 9

But, you could also implement the same hash table as a "longer" 1D array. as follows:

aa   1
ab   2
ac   3
ad   4
ba   5
bb   6
 ...
dc  15
dd  16

So, as you see, even though you could do it with a multidimensional array, perhaps it's a little bit too complicated.

Besides, in reality, a hash() function usually uses all the information provided in the key (i.e.: it takes every char in the string into account), makes a few operations on them (some arithmetic) and produces a single int value as output. That way you're less likely to find a collision. Being the output a single int, there's no point in defining a multidimensional array as your table.


EDIT :

One thing I am still unsure about, is how the hash table is different from an array, in terms of malloc.

It's not. Most likely, a hash table is an array of some sort. As such, you need to allocate memory for it. The size of the table, and therefore of the array, is a matter of study and discussion (not a simple answer here). It's about balancing mem allocation and reducing the probability of collisions: the bigger the table, the lower the probability of a collision and, therefore, the faster you can search through it. But, at the same time, the bigger the table, well... the more memory you're "consuming".

This quote in particular from the Wiki hash table article about separate chaining vs with list head cells

"The disadvantage is that an empty bucket takes the same space as a bucket with one entry."

Does this mean that the hash doesn't return a value in an array (ie table[0] table[1])?

It doesn't say anything about the hash() function or what it returns. It's talking about the design of your hash table.

In both Separate chaining with linked lists and Separate chaining with list head cells, the main hash table is, basically, a list of "buckets". Such thing can be implemented, simply, as an array[]. What makes them behave differently is what those arrays are "made of". Probably in both cases, though, the variable in which you store the data will be a struct (e.g.: as what was defined in CS50 lectures as "nodes").

  • Separate chaining with linked lists: the hash table itself is going to be, "simply", an array of pointers to nodes (the ones that make up linked lists). In each node, you'll store values for the node (in the Wiki example, a name and a phone number) and a pointer to the next node in the list.

  • Separate_chaining_with_list_head_cells: is pretty similar, but the difference is that the hash table (the array[]) is made up of nodes itself (which, in turn, represent the first element in every linked list).

Of course, a node takes up more space than a single pointer does, so an empty bucket with the second method takes up much more space than it would do using the first method (that's the disadvantage). The advantage, on the other side, lies in "better cache efficiency of hash table access" (whatever that means;).

Does this mean a million possible buckets have the same malloc as 100000 if there are only 20000 entries?

No, it means that for every empty bucket, you're "wasting" many times more memory than you'd waste if you used the "linked list" method:

sizeof(pointer) < sizeof(node)

and so it becomes more and more relevant to dimension the hash table properly (more "tightly").

| improve this answer | |
  • Thank you, this is a very clear and helpful response. If I understand you correctly, is that ideal hash functions might use a random number generator in the arithmetic to store each data at unique numbers to minimize collisions? Considering how little I understand it, would you recommend me trying out one of the common hash functions, like the additive hash or the XOR hash, or do you think I would be able to write one? I wanted to use the formula a((26*b)+c) as ...{a, b, c}+[rest of word] to return the int, but also code which returned int's map to unique hash, to avoid space for consonants – Erin Magner Dec 24 '14 at 0:14
  • Actually, Formula: (a*26*26(+26)+((26*b)+c)...because the other formula might repeat itself...sort of like x^3 +x^2+2x – Erin Magner Dec 24 '14 at 1:11
  • and perhaps to use that formula on the middle three letters, because that would likely produce the least collisions? Am I getting it yet? – Erin Magner Dec 24 '14 at 2:01
  • There's a nice Wiki about hash functions you should check. Underneath the jargon there's the Properties seccion which explains clearly the requirements for a good hash function. I'm not (even close to) an expert in the subject, but I do can say that "random number generators" is not the way to go. Simply because there's no way you can guarantee you'll get the same hashed value every time for the same input, which is the most important atribute of a viable hash function. – abelinux Dec 24 '14 at 2:15
  • Here's an example of a widely used hash function (Bob Jenkins' "One-at-a-Time Hash"). As you see, the implementation turns out to be "simple" (of course, the merit lies in it being fast and reliable), and there's no randomness whatsoever: the returned int is "merely" the result of adding up the value of each char in the key, and then applying several bitwise operations to the result. That way you guarantee the final value is in the range of an int. And, according the the author, bitwise operations are way faster than mod (%). – abelinux Dec 24 '14 at 2:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .