Insert the numbers 10, 23, 52, 29, 8, 33, 27, 4, 17 and 6 into a hash table of s
ID: 3680974 • Letter: I
Question
Insert the numbers 10, 23, 52, 29, 8, 33, 27, 4, 17 and 6 into a hash table of size 11. Assume that the table is initially empty and uses chaining to resolve collisions. Use a simple division-based hash function. Draw the resulting hash table. (b) Search for the numbers 35, 41 and 18 in this hash table. For each number, how many hash table elements did you have to examine? (c) In an unsuccessful search in a hash table of this size (11) with this many elements (10), what is the minimum, maximum and average number of elements that need to be examined? (For the average, assume that the elements are hashed uniformly.) (d) Search for the numbers 52, 27 and 6 in this hash table. For each number, how many hash table elements did you have to examine? (e) In a successful search in a hash table of this size (11) with this many elements (10), what is the minimum, maximum and average number of elements that need to be examined? (For the average, assume that the elements are hashed uniformly.)
Explanation / Answer
a)
b)
for 35) 1 element
for 41) 6 elements
for 18) 7 elements
d)
for 52) 1 element
for 27) 1 element
for 6) 1 element
23 6 4 27 17 29 52 8 10 33