Given a hash function h(key), prepare a java simulation program to determine each of the subsequent quantities after 0.8*tablesize random keys have been generated. The keys should be random integers.
1. The percentage of integers between 0 and tablesize-1 that do not equal h(key) for some generated key.
2. The percentage of integers between 0 and tablesize-1 that equal h(key) for more than one generated key.
3. The maximum number of keys that hash into a single value between 0 and tablesize-1. Run the program to test the uniformity of each of the following hash functions.
A. h(key) = key%tablesize for tablesize a prime number.
B. h(key) = key%tablesize for tablesize a power of 2.
Notations and guidelines:
- tablesize is number of unique table indexes that the hash function generates. For example a function key%10 results in 10 unique numbers [0-9] for any valid integer key.
- Based on the above point you must now realize that tablesize can be determined based on the hash function.
- Remember that h(key) returns the table index.
- Use Java's inbuilt random number generator to generate keys.
- As h(key) returns table index, its return type should be of type int.
Data Structure Implementation:
- You must implement a list based hash table. (You must implement your own linked list, do not use Java's LinkedList class).
- Use Separate Chaining method for resolving hash clash.
- You can use the following node class definition towards your implementation:
Class Node {
int key;
int record;
Node nextNode;
}
- In the node class let your record member hold the value stored in key member.
- Your FIRST STEP towards creating the data structure will be to create the bucket. Bucket is an array that holds Node objects. The size of bucket will be tablesiz,e recollect that tablesize can be determined based on your hash function as described earlier.
- Remember that hash function returns the bucket index. Based on the index returned by hash function the record must be inserted accordingly.
- Note that random number generator may return same number multiple times, so you must check if a key already exists. Insert they key only if it does not exist in the hash table.