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 nth term.
Example: S[0]*xn + 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"
