## Description

**Problem Set 9**

**Hash Table**

- You are given the following keys to be hashed into a hash table of size 11:

96,Â 43,Â 72,Â 68,Â 63,Â 28 Assume the following hash function is used Â Â Â Â Â H(key) = key mod 11

and chaining (array of linked lists) is used to resolve collisions.

- Show the hash table that results after all the keys are inserted.
- Compute the average number of comparisons for successful search.

- Using chaining to resolve collisions, give the worst-case running time (big O) for inserting
*n*keys into an initially empty hash table table for each of the following kinds of chains: - Using the following class definitions:

class Node {Â Â Â Â Â Â Â Â Â Â int key;Â Â Â Â Â Â Â Â Â Â String value;

Node next;

}

class Hashtable {Â Â Â Â Â Â Â Â Â Â Node[] entries;Â Â Â Â Â Â Â Â Â Â int numvalues;Â Â Â Â Â Â Â Â Â Â float max_load_factor;

public Hashtable(float max_load_factor) { … } // constructorÂ Â Â Â Â Â }

Complete the following methods of the Hashtable class, using the hash function h(key) = key **mod** table_size.

public void insert(int key, String value) {

// COMPLETE THIS METHOD

}

private void rehash() {Â Â Â Â Â Â Â Â Â // COMPLETE THIS METHODÂ Â Â Â Â Â }

Note: When expanding the hash table, double its size.

*****Suppose you are asked to write a program to count the frequency of occurrence of each word in a document. Desrcibe how you would implement your program using:- A hash table to store words and their frequencies.
- An AVL tree to store words and their frequencies.

For each of these implementations:

- What would be the worst case time to populate the data structure with all the words and their frequencies?
- What would be the worst case time to look up the frequency of a word?
- What would be the worst case time to print all words and their frequencies, in alphabetical order of the words?

Assume there are *n* distinct words in the document, and a total of *m* words, and *m* is much greater than *n*.