Describe how to use a hash table (or a direct-address table) to solve each of th
ID: 3706854 • Letter: D
Question
Describe how to use a hash table (or a direct-address table) to solve each of the following problems. Provide as much detail as possible about the hash table (size, hash function if possible) and analyse the complexity of your solution. Then, answer the following questions: Is a hash table the best way to solve the problem? Why or why not? (a) Given an unsorted list of the names of every student in a class (with n students), determine if two of them have the same names. (b) Given an unsorted list of the names of every student in a class (with n students), return the list of names in sorted order. Does a hash table even make sense in this situation? Discuss.
Explanation / Answer
a.)
In this situation, we will consider a Hash Table of size n(Equal to the Size of class) which will store Name and count.The count value for all cells initially will be zero.Now we will try to store each student one by one also increment the count associated with the cell.
In this way, any cell with a count greater than one will be considered as duplicate hence student must have the same name.
The complexity of this procedure will be O(n)
b.)
Sorting using hash table is feasible only when we know about all the data before sorting.In particular, if know about minimum and maximum values present in the data.This type of sorting is called counting sort because we are actually counting the number the occurrence of a particular item in data and printing it according to count.
The complexity of counting sort using hash table is O(n).But it is suitable for the number only. The complexity of this kind of sorting will increase exponentially with the increase of bit in the string.
THUMBS UP IF YOU ARE SATISFIED WITH THE ANSWER OTHERWISE REPLY WITH YOUR CONCERN.