Chapter 11: Hash Tables

11.1.1. For finding the maximum element in the table you have to scan each slot once and update your maximum element accordingly.The worst case complexity would be O(m).

11.1.2. Initialize a bit vector of length |U| to all  0s. When storing key k set the kth bit and when deleting the unset the kth bit.

11.1.3. Each element in the table should be a pointer to the head of a linked list containing the satellite data. I though doubt for searching to be O(1).

11.1.4. Let us denote the huge array by T, we will also have a structure implemented as an array, S.

                        struct node{

                                    int key;

                                    int value;

} S;

The size of S equals the number of keys actually stored in T, so that S should be allocated at the dictionary’s maximum size. We can also use a linked list data structure so that we need not allocated space initially.

The idea of this scheme is that entries of T and S validate each other. If key k is actually stored in T , then T [k] contains the index, say j , of a valid entry in S, and S[ j ] contains the value k. So, we will have a following validation cycle:

S[T [k]].key = k, and T [S[ j ].key] = j

So, it means the stack S will not really be a stack since we are able to access any index not only the top element. So, for the namesake we can call it a simple array.

Implementing the following operations:

            SEARCH: Just check if for a given input key, the validating cycle is satisfied, if yes return the value.

            INSERT: Increment top[S] to point to the next index. Now make T[k] = top[S] and S[top[S]].key = new_key and S[top[S]].value = new_value_for_the_key.

            DELETE: To delete object x with key k, assuming that this object is in the dictionary, we need to break the validating cycle. The trick is to also ensure that we don’t leave a hole.in the stack, and we solve this problem by moving the top entry of the stack into the position that we are vacating and then fixing up that entry’s validating cycle. Try to come up with a step to implement this.

11.2.1.

11.2.3. Only insertion will be affected by this modification with complexity becoming O(n/m) from O(1).

11.2.4. Initialize all the values to a singly linked free list (flag set to false) with a head and tail pointer. On insert, use the memory pointed to by the head pointer and set the flag to true for the new element and increment the head pointer by one. On delete, set the flag to false and insert the newly freed memory at the tail of the linked list.

11.2.5. This is an application of pigeon-hole principle.

11.3.1. While searching for a key k, we’ll first check if the hash value matches if yes then only we’ll check if the keys actually match or not.

11.3.2. One easy approach would adding the values of each character to get a sum and then take a modulo 128. Another way would be using n-degree equation with each character value acting as a co-efficient for the n^th term.

Example: S[0]*xⁿ + S[1]*x^(n-1)+ …. + S[n-1], for better result substitute x = 33 or 37 or 39. This is the famous Horner’s method for finding a hash value.

11.4.2.

HASH-DELETE(T, k)

i ← 0

repeat j ← h(k, i)

if T[j] = k

then T[j] ← -1

return j

else i ← i + 1

until i = m or T[j] = NIL

error "element doesn’t exist"

           

HASH-INSERT(T, k)

i ← 0

repeat j ← h(k, i)

if T[j] = NIL or T[j] = -1

then T[j] ← k

return j

else i ← i + 1

until i = m

error "element doesn’t exist"