rust初体験
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 } |
// 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) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment