struct HashTable {
table: [Option<i32>; 10],
}
impl HashTable {
fn new() -> Self {
Self { table: [None; 10] }
}
fn hash(&self, key: i32) -> usize {
(key % 10) as usize
}
fn insert(&mut self, key: i32) {
let mut idx = self.hash(key);
while self.table[idx].is_some() {
idx = (idx + 1) % 10;
}
self.table[idx] = Some(key);
}
fn print(&self) {
for i in 0..10 {
match self.table[i] {
Some(k) => print!("{} -> ", k),
None => print!("null -> "),
}
}
println!("null");
}
}
fn main() {
let mut ht = HashTable::new();
let keys = [10, 22, 31, 4, 15];
for &key in keys.iter() {
ht.insert(key);
}
ht.print();
}Keys are inserted using hash = key % 10. Collisions are resolved by moving to the next empty slot.
Insert 10 at index 0.
Insert 22 at index 2.
Insert 31 at index 1 (since 1 is empty).
Insert 4 at index 4.
Insert 15 at index 5.
Slots 0:10, 1:31, 2:22, 3:null, 4:4, 5:15, rest null.
struct HashTable {
table: [Option<i32>; 7],
}
impl HashTable {
fn new() -> Self {
Self { table: [None; 7] }
}
fn hash(&self, key: i32) -> usize {
(key % 7) as usize
}
fn insert(&mut self, key: i32) {
let mut idx = self.hash(key);
while self.table[idx].is_some() {
idx = (idx + 1) % 7;
}
self.table[idx] = Some(key);
}
fn search(&self, key: i32) -> Option<usize> {
let mut idx = self.hash(key);
let start = idx;
loop {
match self.table[idx] {
Some(k) if k == key => return Some(idx),
None => return None,
_ => {
idx = (idx + 1) % 7;
if idx == start {
return None;
}
}
}
}
}
}
fn main() {
let mut ht = HashTable::new();
let keys = [14, 21, 28, 35];
for &key in keys.iter() {
ht.insert(key);
}
let result = ht.search(35);
println!("{:?}", result);
}Hash = key % 7 = 0 for all keys.
14 inserted at 0.
21 probes to 1.
28 probes to 2.
35 probes to 3.
Search for 35: start at 0 (14 ≠), 1 (21 ≠), 2 (28 ≠), 3 (35 ==), return Some(3).
fn insert(table: &mut [Option<i32>], key: i32) {
let size = table.len();
let mut idx = (key % size as i32) as usize;
while table[idx].is_some() {
idx += 1;
}
table[idx] = Some(key);
}
fn main() {
let mut table = vec![None; 5];
insert(&mut table, 1);
insert(&mut table, 6);
insert(&mut table, 11);
insert(&mut table, 16);
insert(&mut table, 21);
println!("{:?}", table);
}The index is incremented without wrapping around the table size.
When idx reaches 5 (table size), accessing table[5] causes panic.
Linear probing requires modulo operation to wrap index.
fn insert(table: &mut [Option<i32>], key: i32) {
let size = table.len();
let mut idx = (key % size as i32) as usize;
// Find empty slot
loop {
if table[idx].is_none() {
table[idx] = Some(key);
break;
}
idx = (idx + 1) % size;
}
}Option A uses a loop that checks if slot is empty, inserts key, and breaks.
It increments idx with modulo to wrap around.
Option A uses while occupied but assumes empty found after loop.
Option A uses for loop which does not probe correctly from hashed index.
Option A loops while slot is empty, which skips empty slots.
enum Slot {
Empty,
Deleted,
Occupied(i32),
}
struct HashTable {
table: [Slot; 7],
}
impl HashTable {
fn new() -> Self {
Self { table: [Slot::Empty; 7] }
}
fn hash(&self, key: i32) -> usize {
(key % 7) as usize
}
fn insert(&mut self, key: i32) {
let size = self.table.len();
let mut idx = self.hash(key);
loop {
match &self.table[idx] {
Slot::Empty | Slot::Deleted => {
self.table[idx] = Slot::Occupied(key);
break;
}
_ => {
idx = (idx + 1) % size;
}
}
}
}
fn delete(&mut self, key: i32) {
let size = self.table.len();
let mut idx = self.hash(key);
let start = idx;
loop {
match &self.table[idx] {
Slot::Occupied(k) if *k == key => {
self.table[idx] = Slot::Deleted;
break;
}
Slot::Empty => break,
_ => {
idx = (idx + 1) % size;
if idx == start {
break;
}
}
}
}
}
fn print(&self) {
for slot in self.table.iter() {
match slot {
Slot::Empty => print!("null -> "),
Slot::Deleted => print!("del -> "),
Slot::Occupied(k) => print!("{} -> ", k),
}
}
println!("null");
}
}
fn main() {
let mut ht = HashTable::new();
ht.insert(10);
ht.insert(20);
ht.insert(5);
ht.insert(15);
ht.delete(20);
ht.insert(27);
ht.print();
}Hash indices: 10%7=3 → 3:10; 20%7=6 → 6:20; 5%7=5 → 5:5; 15%7=1 → 1:15.
Delete 20: mark 6 as deleted.
Insert 27: hash=6, deleted → insert at 6:27.
Final: 0:null, 1:15, 2:null, 3:10, 4:null, 5:5, 6:27.
Printed: null -> 15 -> null -> 10 -> null -> 5 -> 27 -> null