Scribd
Upload
6 views2 pages

Hash Table Operations and Efficiency Analysis

The document contains sample questions related to hash tables, including tasks on inserting elements, analyzing hash functions, and comparing complexities of ordered vs unordered linked lists. It also includes coding questions focused on operations such as calculating average list length, finding maximum values, checking for duplicates, and comparing hash tables. The content emphasizes understanding hash table mechanics and efficiency issues in collision resolution.

Uploaded by

Nour H
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views2 pages

Hash Table Operations and Efficiency Analysis

The document contains sample questions related to hash tables, including tasks on inserting elements, analyzing hash functions, and comparing complexities of ordered vs unordered linked lists. It also includes coding questions focused on operations such as calculating average list length, finding maximum values, checking for duplicates, and comparing hash tables. The content emphasizes understanding hash table mechanics and efficiency issues in collision resolution.

Uploaded by

Nour H
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Sample Questions: HASH

General Questions
Q1) Assume that you have a hash table with size 6 and the following hashing function: h (key) =
key % table_size.
(a) Draw the hash table after inserting the following sequence of elements in order. Assume
that we are using separate chaining (lists) for resolving collisions and that the elements
are inserted at the tail of each list.
< 8, 5, 1, 7, 13, 12>
(b) Suggest a hash table size that will result in no collisions for the above sequence of
insertions. The hashing function remains the same. Briefly justify your choice.

Q2) Consider the following hash function


implementation: h(key) = key*2 % size
a) Assume that we create a hash table with array Answer of (a) below:
size 4. Draw (next to the above code) the table
and its contents after we insert the following
values in order: 1, 4, 5, 6, 3, 15, 10, 11. Note
that the hash function that we are using here is
different from the one that we used in class
b) Did you observe any efficiency problem in the
above hash example? If yes, explain the problem
and suggest a solution. If no, explain why it is
efficient.
Yes, there is efficiency problem; half of the
hash array cells are not used and the collision
among data is sort of high. This is happening
because of the hash function distributing the
data such that even numbers go to first list
(index 0) and odd numbers go to the third list (index 2). And this happens from (val
*2). A suggested solution is to change hash function to spread data more evenly
across the hash lists, example will be val % [Link] solution would be to
increase the hash size.

Q3) Suppose that we consider using an ordered DLL in each hash bucket instead of an
unordered DLL. Compare the asymptotic complexities of the operations shown in the table
below for each of these two implementations (ordered DLL vs unordered DLL). Assume that the
number of elements in the hash table is N, the number of buckets is M and that each bucket has
exactly λ elements (λ= N/M)

Insert Search GetMax


Chaining With Ordered DLLs O(λ) O(λ) O(M)
Chaining With Unordered DLLS O(1) O(λ) O(N+M)
Sample Questions: HASH

Coding Questions
Q1) Write the implementation of the function AverageListLength, which computes and returns
the average length of the non-empty lists in the hash table, that is, it computes the total number
of elements in the hash table and divides it by the number of non-empty lists. You are allowed to
use only the DLL and DLLNode operations given in the above code.

Q2) Return the tuple with max value

Q3) Checks if any key appears in the hash table more than once.

Q4) Removes all the duplicates from the hash table.

Q5) Checks if any chain in the table is longer than twice the average chain length in the table.

Q6) Checks if the hash table is equal to the other hash table. Two hash tables are equal if they
both contain exactly the same keys regardless of how they are distributed in the tables. For
simplicity, assume that the keys in both tables are distinct

You might also like