Pan's RD

什么是Hash Table?

哈希表又称散列表、通过构建键、值之间的映射关系实现高效存储和读取数据的一种数据结构。

常见操作：

插入，将元素添加到数组（或者链表）尾部即可，时间复杂度O(1)
删除,需要遍历数组或者链表找到要删除目标的index，时间复杂度O(n)
查找，同删除操作

理想状态下哈希表中进行增删查改的时间复杂度都是O(1) ,哈希表相当高效。

Rust中哈希表的基本操作:

rust

use::std::collections::HashMap;
fn main() {
    //1.创建hash，语法：let mut map: HashMap<keyType, valueType> = HashMap::new();
    let mut map: HashMap<i32, String> = HashMap::new();
    
    //2.添加元素
    map.insert(1, "one".to_string());
    map.insert(2, "two".to_string());
    map.insert(3, "three".to_string());
    
    //3.获取对应key的value
    let No = map.get(&3);
    
   
    //4.从HashMap中移除指定键的键值对，并返回被移除的值。
    let removed_No = map.remove(&2);

}

实现哈希表数据结构

通过一个数组简单实现Hash数据结构，本质：存在一个哈希函数处理输入的key来获取对应 桶 的索引。这里用数组的每一个连续空间存储桶，每个桶里包含hash每个子项的键值对。

核心就是编写hash函数来实现由key -> index的映射,示例使用key取模映射index(实际应用中存在更复杂的映射)。

rust

#[derive(Debug,PartialEq,Clone)]
pub  struct Pair{
    key:i32,
    val:String
}
#[derive(Debug)]
pub struct ArrayHash{
    buckets:Vec<Option<Pair>>
}

impl ArrayHash {
    pub fn new() -> ArrayHash {
        Self {
            buckets: vec![None; 100]
        }
    }

    fn hash_func(&self, key: i32) -> usize {
        key as usize % 100
    }

    pub  fn get(&self,key:i32) -> Option<&String>{
        let index = self.hash_func(key);
        self.buckets[index].as_ref().map(|pair| {&pair.val})
    }
    pub fn put(&mut self,key:i32,val:&str){
        let index = self.hash_func(key);
        self.buckets[index] = Some(
            Pair{
                key,
                val:val.to_string()
            }
        )
    }
    pub fn remove(&mut self,key:i32){
        let index = self.hash_func(key);
        self.buckets[index] = None;
    }
    pub  fn entry(&self) -> Vec<&Pair>{
        self.buckets.iter().filter_map(|pair| {
            //通过pair.as_ref().map(|x| {})发现x即为&Pair类型，只需collect到vec中,就能获得目标返回类型Vec<Pair>
            pair.as_ref()
        }).collect()
    }
    pub  fn keys(&self) -> Vec<&i32>{
        self.buckets.iter().filter_map(|pair| {
            pair.as_ref().map(|x| {
                &x.key
            })
        }).collect()
    }
    pub  fn vals(&self) -> Vec<&String>{
        self.buckets.iter().filter_map(|pair| {
            pair.as_ref().map(|x| {
                &x.val
            })
        }).collect()
    }
}

fn main() {

}

#[cfg(test)]
mod test{
    use super::*;
    #[test]
    fn test_new(){
        let hash = ArrayHash::new();
        assert_eq!(hash.buckets,vec![None;100])
    }

    #[test]
    //测试四个方法：hash_func、get、put、remove
    fn test_methods(){
        let mut hash = ArrayHash::new();
        let index = hash.hash_func(102);
        assert_eq!(index,2);
        hash.buckets[index] = Some(
            Pair{
                key:007,
                val:"lucy".to_string()
            }
        );
        assert_eq!(hash.get(102),Some(&"lucy".to_string()));

        hash.remove(102);
        assert_eq!(hash.buckets[index],None);

        hash.put(008,"lily");
        assert_eq!(hash.buckets[8],Some(Pair{key:008,val:"lily".to_string()}))

    }
}

哈希冲突

哈希表中多个输入对应同一输出的情况称为哈希冲突（hash collision），哈希函数的本质就是把所有 key 构成的输入空间映射到数组所有索引构成的输出空间。理论上存在多个输入对应一个输出的情况，这就是哈希冲突。

什么是Hash Table? ​

实现哈希表数据结构 ​

哈希冲突 ​

什么是Hash Table?

实现哈希表数据结构

哈希冲突