rust_algorithms/data_structures/

hash_table.rs

//! Hash table (xesh-jadval) — kalit → qiymat, o'rtacha O(1).

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

/// 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.
///
/// ```text
///  "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);
/// ```
#[derive(Debug, Clone)]
pub struct HashTable<K, V> {
    buckets: Vec<Vec<(K, V)>>,
    len: usize,
}

impl<K: Hash + Eq, V> Default for HashTable<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

impl<K: Hash + Eq, V> HashTable<K, V> {
    const BOSHLANGICH: usize = 8;
    const MAX_YUKLAMA: f64 = 0.75;

    /// Bo'sh jadval yaratadi.
    pub fn new() -> Self {
        Self {
            buckets: (0..Self::BOSHLANGICH).map(|_| Vec::new()).collect(),
            len: 0,
        }
    }

    /// Kalit-qiymat qo'shadi. Kalit avval bo'lgan bo'lsa, eski qiymat qaytadi.
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if (self.len + 1) as f64 > self.buckets.len() as f64 * Self::MAX_YUKLAMA {
            self.rehash();
        }
        let idx = self.bucket_index(&key);
        for (k, v) in self.buckets[idx].iter_mut() {
            if *k == key {
                return Some(std::mem::replace(v, value));
            }
        }
        self.buckets[idx].push((key, value));
        self.len += 1;
        None
    }

    /// Kalit bo'yicha qiymatni oladi.
    pub fn get(&self, key: &K) -> Option<&V> {
        let idx = self.bucket_index(key);
        self.buckets[idx]
            .iter()
            .find(|(k, _)| k == key)
            .map(|(_, v)| v)
    }

    /// Qiymatni o'zgartirish uchun havola.
    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        let idx = self.bucket_index(key);
        self.buckets[idx]
            .iter_mut()
            .find(|(k, _)| k == key)
            .map(|(_, v)| v)
    }

    /// Kalit mavjudmi?
    pub fn contains_key(&self, key: &K) -> bool {
        self.get(key).is_some()
    }

    /// Kalitni o'chiradi va qiymatini qaytaradi.
    pub fn remove(&mut self, key: &K) -> Option<V> {
        let idx = self.bucket_index(key);
        let pos = self.buckets[idx].iter().position(|(k, _)| k == key)?;
        self.len -= 1;
        Some(self.buckets[idx].swap_remove(pos).1)
    }

    /// Juftliklar soni.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Bo'shmi?
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Barcha juftliklar bo'ylab iterator (tartib kafolatlanmaydi).
    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        self.buckets
            .iter()
            .flat_map(|b| b.iter().map(|(k, v)| (k, v)))
    }

    fn bucket_index(&self, key: &K) -> usize {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        (hasher.finish() % self.buckets.len() as u64) as usize
    }

    /// Chelaklar sonini ikki barobar oshirib, hammani qayta joylashtiradi.
    fn rehash(&mut self) {
        let yangi_hajm = self.buckets.len() * 2;
        let eski = std::mem::replace(
            &mut self.buckets,
            (0..yangi_hajm).map(|_| Vec::new()).collect(),
        );
        for chelak in eski {
            for (k, v) in chelak {
                let idx = self.bucket_index(&k);
                self.buckets[idx].push((k, v));
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashMap;

    #[test]
    fn asosiy_amallar() {
        let mut m = HashTable::new();
        assert!(m.is_empty());
        assert_eq!(m.insert("a", 1), None);
        assert_eq!(m.insert("a", 2), Some(1));
        assert_eq!(m.len(), 1);
        assert_eq!(m.get(&"a"), Some(&2));
        assert!(m.contains_key(&"a"));
        assert_eq!(m.remove(&"a"), Some(2));
        assert_eq!(m.remove(&"a"), None);
        assert!(m.is_empty());
    }

    #[test]
    fn get_mut_ishlaydi() {
        let mut m = HashTable::new();
        m.insert(1, String::from("bir"));
        m.get_mut(&1).unwrap().push_str("inchi");
        assert_eq!(m.get(&1).map(String::as_str), Some("birinchi"));
    }

    #[test]
    fn std_hashmap_bilan_bir_xil_ishlaydi() {
        let mut ours = HashTable::new();
        let mut theirs = HashMap::new();

        for i in 0..1000i32 {
            let kalit = format!("kalit-{}", i * 7 % 337);
            assert_eq!(ours.insert(kalit.clone(), i), theirs.insert(kalit, i));
        }
        assert_eq!(ours.len(), theirs.len());

        for (k, v) in theirs.iter() {
            assert_eq!(ours.get(k), Some(v));
        }

        for k in theirs.keys() {
            assert!(ours.contains_key(k));
        }
    }

    #[test]
    fn rehashdan_keyin_hamma_kalit_joyida() {
        let mut m = HashTable::new();
        for i in 0..500 {
            m.insert(i, i * i);
        }
        assert_eq!(m.len(), 500);
        for i in 0..500 {
            assert_eq!(m.get(&i), Some(&(i * i)));
        }
        assert_eq!(m.iter().count(), 500);
    }
}