Data Structures · Hash tables and probabilistic performance
Consider a hash table T of size m = 11 that resolves collisions by chaining
Problem
Consider a hash table \(T\) of size \(m = 11\) that resolves collisions by chaining. Slots are indexed \(0\) through \(10\). The hash function is \(h(k) = k \bmod 11\). Each chain is a singly linked list; a newly inserted key is placed at the head of its chain. Starting from an empty table, insert the keys \(22, 31, 43, 15, 26, 8, 19, 53, 4\) in that order. Write the contents of every slot after all nine insertions, listing each chain from head to tail. Then execute \(\mathrm{SEARCH}(19)\) and \(\mathrm{SEARCH}(12)\). A key comparison occurs each time a stored key is compared with the query key. Report the number of key comparisons performed by each of the two searches.
Hint
Remainder modulo the table size selects a unique chain; insert-at-head only rewrites that chain’s first pointer.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.
More Data Structures practice problems
- Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…Abstract data types, representation, and invariants
- A ring buffer (circular array) of fixed capacity C≥ 1 stores a sequence of at most C…Abstract data types, representation, and invariants
- Let L be the doubly linked list with values [10, 20, 30, 40, 50], and let I be a…Arrays, linked structures, stacks, queues, and amortization
- Consider BST deletion of a node zSearch trees and balanced trees
- Let T be a BST whose nodes contain only key, left, and right fields (no parent…Search trees and balanced trees
- Throw n balls independently and uniformly into n binsHash tables and probabilistic performance
- `Bubble-Down`(A,i,n) is specified as follows on a 1-based array that is a complete…Heaps, priority queues, and disjoint sets
- The fat-node method of partial persistence stores, in each field of each node, a…Graph representations and traversals
- A duplicate minimum must sit on the min-stack, or one pop forgets the otherArrays, linked structures, stacks, queues, and amortization