Consider a hash table using chaining with a simple hash function: hash(key) = key % 3. Insert keys 3, 6, 9, and 4 in that order. What is the state of the hash table buckets after all insertions?
struct HashTable {
buckets: Vec<Vec<i32>>,
}
impl HashTable {
fn new(size: usize) -> Self {
Self { buckets: vec![Vec::new(); size] }
}
fn hash(&self, key: i32) -> usize {
(key % 3) as usize
}
fn insert(&mut self, key: i32) {
let index = self.hash(key);
self.buckets[index].push(key);
}
}
fn main() {
let mut table = HashTable::new(3);
table.insert(3);
table.insert(6);
table.insert(9);
table.insert(4);
for (i, bucket) in table.buckets.iter().enumerate() {
print!("Bucket {}: ", i);
for key in bucket {
print!("{} -> ", key);
}
println!("null");
}
}Remember the hash function is key % 3. Group keys by their remainder when divided by 3.
Keys 3, 6, and 9 all have remainder 0 when divided by 3, so they go into bucket 0. Key 4 has remainder 1, so it goes into bucket 1. Bucket 2 remains empty.
Which of the following best explains why chaining is a good method to handle collisions in hash tables?
Think about how multiple keys can be stored in the same bucket without losing data.
Chaining stores collided keys in a linked list (or similar structure) at the same bucket, so no keys are lost and collisions are handled gracefully.
What error will this Rust code produce when inserting keys into the hash table using chaining?
struct HashTable {
buckets: Vec<Vec<i32>>,
}
impl HashTable {
fn new(size: usize) -> Self {
Self { buckets: vec![Vec::new(); size] }
}
fn hash(&self, key: i32) -> usize {
(key % 5) as usize
}
fn insert(&mut self, key: i32) {
let index = self.hash(key);
self.buckets[index].push(key);
}
}
fn main() {
let mut table = HashTable::new(3);
table.insert(8);
}Check the size of the buckets vector and the hash function output.
The hash function returns values from 0 to 4 (because of modulo 5), but the buckets vector has size 3. Accessing index 3 or 4 causes an index out of bounds panic.
Given a hash table with chaining and the hash function hash(key) = key % 4, after inserting keys 4, 8, 12, and 5, we delete key 8. What is the state of the buckets?
struct HashTable {
buckets: Vec<Vec<i32>>,
}
impl HashTable {
fn new(size: usize) -> Self {
Self { buckets: vec![Vec::new(); size] }
}
fn hash(&self, key: i32) -> usize {
(key % 4) as usize
}
fn insert(&mut self, key: i32) {
let index = self.hash(key);
self.buckets[index].push(key);
}
fn delete(&mut self, key: i32) {
let index = self.hash(key);
if let Some(pos) = self.buckets[index].iter().position(|&x| x == key) {
self.buckets[index].remove(pos);
}
}
}
fn main() {
let mut table = HashTable::new(4);
table.insert(4);
table.insert(8);
table.insert(12);
table.insert(5);
table.delete(8);
for (i, bucket) in table.buckets.iter().enumerate() {
print!("Bucket {}: ", i);
for key in bucket {
print!("{} -> ", key);
}
println!("null");
}
}Remember to remove key 8 from its bucket after insertion.
Keys 4, 8, and 12 all hash to bucket 0. After deleting 8, only 4 and 12 remain. Key 5 hashes to bucket 1. Buckets 2 and 3 remain empty.
Assuming a hash table uses chaining and the hash function distributes keys uniformly, what is the average time complexity to search for a key?
Think about how many keys are expected in each bucket on average.
With uniform hashing, keys are evenly spread. The average chain length equals the load factor. Searching requires checking one bucket's chain, so average time is O(1 + load factor).