Hashing - Advanced Topics in Java: Core Concepts in Data Structures - page 301

eXerCISeS 10

1. integers are inserted into a hash table H[1..11] using the primary hash function

h1(k) = 1 + k mod 11 . show the state of the array after inserting the keys 10 , 22 , 31 , 4 , 15 ,
28 , 17 , 88 , and 58 using (a) linear probing, (b) quadratic probing with probe function i + i2 ,
and (c) double hashing with h2(k) = 1 + k mod 9 .

2. integers are inserted in an integer hash table list[1] to list[n] using linear probe with

double hashing. assume that the function h1 produces the initial hash location and the
function h2 produces the increment. an available location has the value Empty , and a deleted
location has the value Deleted .

Write a function to search for a given value key . if found, the function returns the location
containing key . if not found, the function inserts key in the first deleted location encountered
(if any) in searching for key , or an Empty location, and returns the location in which key was
inserted. You may assume that list contains room for a new integer.

3. in a hashing application, the key consists of a string of letters. Write a hash function that,

given a key and an integer max , returns a hash location between 1 and max , inclusive. Your
function must use all of the key and should not deliberately return the same value for keys
consisting of the same letters.

4. a hash table of size n contains two fields—an integer data field and an integer link

field—called data and next , say. the next field is used to link data items in the hash table in
ascending order. a value of - 1 indicates the end of the list. the variable top (initially set to -1)
indicates the location of the smallest data item. integers are inserted in the hash table using
hash function h1 and linear probing. the data field of an available location has the value
Empty , and no item is ever deleted from the table. Write programming code to search for
a given value key . if found, do nothing. if not found, insert key in the table and link it in its
ordered position . You may assume that the table contains room for a new integer.

5. in a certain application, keys that hash to the same location are held on a linked list. the

hash table location contains a pointer to the first item on the list, and a new key is placed at
the end of the list. each item in the linked list consists of an integer key , an integer count ,
and a pointer to the next element in the list. storage for a linked list item is allocated as
needed. assume that the hash table is of size n and the call H(key) returns a location from 1
to n , inclusive.

Write programming code to initialize the hash table.

Write a function that, given the key nkey , searches for it if not found, adds nkey in its
appropriate position, and sets count to 0 . if found, add 1 to count ; if count reaches 10 , delete
the node from its current position, place it at the head of its list, and set count to 0 .

6. Write a program to read and store a thesaurus as follows:

Data for the program consists of lines of input. each line contains a (variable) number of
distinct words, all of which are synonyms. You may assume that words consist of letters
only and are separated by one or more blanks. Words may be spelled using any combination
of uppercase and lowercase letters. all words are to be stored in a hash table using open