rust初体験

gistfile1.txt

0 is empty! so first insert to 0
1 is empty! so first insert to 1
extend to 4 !
rehash key:0 into slot:0
rehash key:1 into slot:1
2 is empty! so first insert to 2
3 is empty! so first insert to 3
extend to 8 !
rehash key:0 into slot:0
rehash key:1 into slot:1
rehash key:2 into slot:2
rehash key:3 into slot:3
4 is empty! so first insert to 4
5 is empty! so first insert to 5
6 is empty! so first insert to 6
7 is empty! so first insert to 7
extend to 16 !
rehash key:0 into slot:0
rehash key:1 into slot:1
rehash key:2 into slot:2
rehash key:3 into slot:3
rehash key:4 into slot:13
rehash key:5 into slot:14
rehash key:6 into slot:15
rehash key:7 into slot:10
4 is empty! so first insert to 8
11 is empty! so first insert to 9
7 is empty! so first insert to 10
8 is empty! so first insert to 11
9 is empty! so first insert to 12
5 is empty! so first insert to 13
6 is empty! so first insert to 14
12 is empty! so first insert to 15
extend to 32 !
rehash key:0 into slot:0
rehash key:1 into slot:1
rehash key:2 into slot:2
rehash key:3 into slot:3
rehash key:8 into slot:26
rehash key:13 into slot:20
rehash key:14 into slot:21
rehash key:10 into slot:23
rehash key:11 into slot:24
rehash key:12 into slot:25
rehash key:7 into slot:27
rehash key:9 into slot:28
rehash key:15 into slot:22
rehash key:4 into slot:29
rehash key:5 into slot:30
rehash key:6 into slot:31
4 is empty! so first insert to 16
17 is empty! so first insert to 17
18 is empty! so first insert to 18
19 is empty! so first insert to 19
14 is empty! so first insert to 20
15 is empty! so first insert to 21
16 is empty! so first insert to 22
11 is empty! so first insert to 23
12 is empty! so first insert to 24
13 is empty! so first insert to 25
8 is empty! so first insert to 26
9 is empty! so first insert to 27
10 is empty! so first insert to 28
5 is empty! so first insert to 29
6 is empty! so first insert to 30
7 is empty! so first insert to 31
extend to 64 !
rehash key:0 into slot:0
rehash key:1 into slot:32
rehash key:2 into slot:1
rehash key:3 into slot:33
rehash key:16 into slot:52
rehash key:29 into slot:8
rehash key:30 into slot:5
rehash key:31 into slot:37
rehash key:26 into slot:40
rehash key:27 into slot:9
rehash key:28 into slot:41
rehash key:23 into slot:43
rehash key:24 into slot:11
rehash key:25 into slot:44
rehash key:20 into slot:46
rehash key:21 into slot:14
rehash key:22 into slot:47
rehash key:17 into slot:49
rehash key:18 into slot:17
rehash key:19 into slot:50
rehash key:13 into slot:20
rehash key:14 into slot:53
rehash key:15 into slot:21
rehash key:10 into slot:23
rehash key:11 into slot:55
rehash key:12 into slot:24
rehash key:8 into slot:58
rehash key:7 into slot:26
rehash key:9 into slot:27
rehash key:4 into slot:29
rehash key:5 into slot:61
rehash key:6 into slot:30
6 is empty! so first insert to 32
2 is empty! so first insert to 33
34 is empty! so first insert to 34
3 is empty! so first insert to 35
63 is empty! so first insert to 36
31 is empty! so first insert to 37
4 is empty! so first insert to 38
60 is empty! so first insert to 39
28 is empty! so first insert to 40
62 is empty! so first insert to 41
35 is empty! so first insert to 42
25 is empty! so first insert to 43
57 is empty! so first insert to 44
36 is empty! so first insert to 45
22 is empty! so first insert to 46
54 is empty! so first insert to 47
38 is empty! so first insert to 48
19 is empty! so first insert to 49
HashTable { table: [KeyVal { key: 0, val: 0 }, KeyVal { key: 2, val: 4 }, KeyVal { key: 33, val: 1089 }, KeyVal { key: 35, val: 1225 }, KeyVal { key: 38, val: 1444 }, KeyVal { key: 30, val: 900 }, KeyVal { key: 32, val: 1024 }, Empty, KeyVal { key: 29, val: 841 }, KeyVal { key: 27, val: 729 }, Empty, KeyVal { key: 24, val: 576 }, Empty, Empty, KeyVal { key: 21, val: 441 }, Empty, Empty, KeyVal { key: 18, val: 324 }, Empty, KeyVal { key: 49, val: 2401 }, KeyVal { key: 13, val: 169 }, KeyVal { key: 15, val: 225 }, KeyVal { key: 46, val: 2116 }, KeyVal { key: 10, val: 100 }, KeyVal { key: 12, val: 144 }, KeyVal { key: 43, val: 1849 }, KeyVal { key: 7, val: 49 }, KeyVal { key: 9, val: 81 }, KeyVal { key: 40, val: 1600 }, KeyVal { key: 4, val: 16 }, KeyVal { key: 6, val: 36 }, KeyVal { key: 37, val: 1369 }, KeyVal { key: 1, val: 1 }, KeyVal { key: 3, val: 9 }, KeyVal { key: 34, val: 1156 }, KeyVal { key: 42, val: 1764 }, KeyVal { key: 45, val: 2025 }, KeyVal { key: 31, val: 961 }, KeyVal { key: 48, val: 2304 }, Empty, KeyVal { key: 26, val: 676 }, KeyVal { key: 28, val: 784 }, Empty, KeyVal { key: 23, val: 529 }, KeyVal { key: 25, val: 625 }, Empty, KeyVal { key: 20, val: 400 }, KeyVal { key: 22, val: 484 }, Empty, KeyVal { key: 17, val: 289 }, KeyVal { key: 19, val: 361 }, Empty, KeyVal { key: 16, val: 256 }, KeyVal { key: 14, val: 196 }, KeyVal { key: 47, val: 2209 }, KeyVal { key: 11, val: 121 }, Empty, KeyVal { key: 44, val: 1936 }, KeyVal { key: 8, val: 64 }, Empty, KeyVal { key: 39, val: 1521 }, KeyVal { key: 5, val: 25 }, KeyVal { key: 41, val: 1681 }, KeyVal { key: 36, val: 1296 }], size: 64 }

hashtable.rs

// use std::hash::{Hasher, SipHasher};

#[derive(Clone, Debug)]
enum Slot {
    KeyVal {key: i32, val: i32},
    Empty
}

#[derive(Debug)]
struct HashTable {
    table: Vec<Slot>,
    size: usize
}

impl HashTable {
    fn new() -> HashTable {
        HashTable { table: vec![Slot::Empty, Slot::Empty], size: 2}
    }

    fn hash(&self, key: i32) -> u64 {
        key as u64 * 19937 % 1763
    }

    fn insert(&mut self, key: i32, val: i32) -> bool {
        let mut pos = self.hash(key) as usize % self.size;

        let mut iter = 0;
        loop {
            match self.table[pos] {
                Slot::Empty => {
                    self.table[pos] = Slot::KeyVal{key: key, val: val};
                    println!("{} is empty! so first insert to {}", pos, key);
                    return true
                }
                Slot::KeyVal{key: k, val: _} => {
                    if key == k {
                        return false;
                    }
                    iter += 1;
                }
            }

            if iter == self.size {
                // rehash
                self.size *= 2;
                iter = 0;
                println!("extend to {} !", self.size);
                let mut newtable = vec![Slot::Empty; self.size];
                for slot in &self.table {
                    match slot {
                        &Slot::KeyVal{key: k, val: v} => {
                            let mut newpos = self.hash(k) as usize % self.size;
                            loop {
                                match newtable[newpos] {
                                    Slot::KeyVal{key: _, val: _} => {
                                        newpos += 1;
                                    },
                                    Slot::Empty => {
                                        println!("rehash key:{} into slot:{}", k, newpos);
                                        newtable[newpos] = Slot::KeyVal{key: k, val: v};
                                        break;
                                    }
                                }
                            }
                        },
                        _ => {}
                    }
                }
                self.table = newtable;
            }

            // prove next slot(it is linear probing)
            pos = (pos + 1) % self.size;
        }
    }
}

fn main() {
    let mut b = HashTable::new();
    for x in 0..50 {
        b.insert(x, x * x);
    }
    println!("{:?}", b)
}