Struct HashTable 

pub struct HashTable<K, V> { /* private fields */ }

Zanjirlash (separate chaining) usulidagi xesh-jadval.

G’oya: kalitni xesh funksiyasi orqali songa aylantiramiz, uni chelaklar soniga qoldiqli bo’lamiz va o’sha chelakka yozamiz. Ikki kalit bitta chelakka tushsa (“to’qnashuv”), ular bitta ro’yxatda yonma-yon yashaydi.

 "olma" ─hash─> 1743 ─% 8─> chelak 7 ─> [("olma", 5)]
 "anor" ─hash─>  911 ─% 8─> chelak 7 ─> [("olma", 5), ("anor", 3)]  ← to'qnashuv

Yuklama koeffitsienti (load factor) 0.75 dan oshsa, chelaklar soni ikki barobar oshiriladi va hamma element qayta joylashtiriladi (rehash).

Amal	O’rtacha	Eng yomon
insert / get / remove	O(1)	O(n) (hamma kalit bitta chelakda)

Amalda std::collections::HashMap dan foydalaning — u DoS hujumlaridan himoyalangan (SipHash) va ancha optimallashtirilgan.

Misol

use rust_algorithms::data_structures::HashTable;

let mut m = HashTable::new();
m.insert("olma", 5);
m.insert("anor", 3);
assert_eq!(m.get(&"olma"), Some(&5));

m.insert("olma", 10); // ustiga yozadi
assert_eq!(m.get(&"olma"), Some(&10));
assert_eq!(m.len(), 2);

assert_eq!(m.remove(&"anor"), Some(3));
assert_eq!(m.get(&"anor"), None);

Implementations

impl<K: Hash + Eq, V> HashTable<K, V>

pub fn new() -> Self

Bo’sh jadval yaratadi.

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Kalit-qiymat qo’shadi. Kalit avval bo’lgan bo’lsa, eski qiymat qaytadi.

pub fn get(&self, key: &K) -> Option<&V>

Kalit bo’yicha qiymatni oladi.

pub fn get_mut(&mut self, key: &K) -> Option<&mut V>

Qiymatni o’zgartirish uchun havola.

pub fn contains_key(&self, key: &K) -> bool

Kalit mavjudmi?

pub fn remove(&mut self, key: &K) -> Option<V>

Kalitni o’chiradi va qiymatini qaytaradi.

pub fn len(&self) -> usize

Juftliklar soni.

pub fn is_empty(&self) -> bool

Bo’shmi?

pub fn iter(&self) -> impl Iterator<Item = (&K, &V)>

Barcha juftliklar bo’ylab iterator (tartib kafolatlanmaydi).

Trait Implementations

impl<K: Clone, V: Clone> Clone for HashTable<K, V>

fn clone(&self) -> HashTable<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for HashTable<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: Hash + Eq, V> Default for HashTable<K, V>

fn default() -> Self

Returns the “default value” for a type.