Pset6: Is it possible implement a 3D Hash table Matrix?

Question

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!

Answer 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").