不使用任何内建的哈希表库设计一个哈希映射
具体地说，你的设计应该包含以下的功能
示例：
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.remove(2); // 删除键为2的数据
hashMap.get(2); // 返回 -1 (未找到)
注意：
所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。
题型归类: vec
用vec来进行存储，因为涉及key和val，有可能会key和val不是一个类型，那么就用stuct来进行存储单个的key,val键值对。然后通过循环查询查看是否有这个key，有就更新val，如果没有，就插入这个strut。
// 代码实现
#[derive(Debug)]
struct KeyVal {
key:i32,
value:i32
}
#[derive(Debug)]
struct MyHashMap {
data: Vec<KeyVal>,
}
//
// * `&self` means the method takes an immutable reference.
// * If you need a mutable reference, change it to `&mut self` instead.
// */
impl MyHashMap {
/** Initialize your data structure here. */
fn new() -> Self {
MyHashMap {
data: vec![]
}
}
/** value will always be non-negative. */
fn put(&mut self, key: i32, value: i32) {
for key_val in self.data.iter_mut() {
if key == key_val.key {
key_val.value = value;
return;
}
}
self.data.push(KeyVal{key, value});
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
fn get(&self, key: i32) -> i32 {
for key_val in self.data.iter() {
if key == key_val.key {
return key_val.value;
}
}
-1
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
fn remove(&mut self, key: i32) {
for (i, key_val) in self.data.iter().enumerate() {
if key == key_val.key {
self.data.remove(i);
break;
}
}
}
}
#[cfg(test)]
mod test {
use super::MyHashMap;
#[test]
fn test() {
let mut hashMap = MyHashMap::new();
hashMap.put(1,1);
hashMap.put(2, 2);
assert_eq!(1, hashMap.get(1));
assert_eq!(2, hashMap.get(2));
assert_eq!(-1, hashMap.get(3));
hashMap.put(2, 1); // 更新已有的值
assert_eq!(1, hashMap.get(2));
hashMap.remove(2); // 删除键为2的数据
assert_eq!(-1, hashMap.get(2));
}
}
执行用时 : 60 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 4.4 MB , 在所有 Rust 提交中击败了 100.00% 的用户
要怎么做才可以更快呢？
思路一中，因为为了做数据更新，所以每次插入数据都去循环检查了有没有这个key，有就更新，没有就插入。为了提升速度，我们可以只管插入，每次都是从0插入，不管更新。获取的时候都从开始往后找。要remove我们就标记最近一个单元的状态为delete，这样可以减少很多循环。
#[derive(Debug)]
struct KeyVal {
key:i32,
value:i32,
del:bool,
}
#[derive(Debug)]
struct MyHashMap {
data: Vec<KeyVal>,
}
//
// * `&self` means the method takes an immutable reference.
// * If you need a mutable reference, change it to `&mut self` instead.
// */
impl MyHashMap {
/** Initialize your data structure here. */
fn new() -> Self {
MyHashMap {
data: vec![]
}
}
/** value will always be non-negative. */
fn put(&mut self, key: i32, value: i32) {
self.data.insert(0, KeyVal{key, value, del:false});
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
fn get(&self, key: i32) -> i32 {
for key_val in self.data.iter() {
if key == key_val.key {
if key_val.del {
return -1;
}
return key_val.value;
}
}
-1
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
fn remove(&mut self, key: i32) {
for key_val in self.data.iter_mut() {
if key == key_val.key {
key_val.del = true;
break;
}
}
}
}
#[cfg(test)]
mod test {
use super::MyHashMap;
#[test]
fn test() {
let mut hashMap = MyHashMap::new();
hashMap.put(1,1);
hashMap.put(2, 2);
assert_eq!(1, hashMap.get(1));
assert_eq!(2, hashMap.get(2));
assert_eq!(-1, hashMap.get(3));
hashMap.put(2, 1); // 更新已有的值
assert_eq!(1, hashMap.get(2));
hashMap.remove(2); // 删除键为2的数据
assert_eq!(-1, hashMap.get(2));
}
}
执行用时 : 44 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 4.4 MB , 在所有 Rust 提交中击败了 100.00%
感谢Lewis的提醒，又有了思路三。因为题目中，HashMap的key范围是有限的为0到100000，那么我们直接初始化一个确定大小范围内的vec，初始值都为-1，这样hashmap的key就可以是vec的index，设置值就可以用下标进行，删除值就可以重新赋值为-1。
// 代码实现
struct MyHashMap {
data: Vec<i32>,
}
//
// * `&self` means the method takes an immutable reference.
// * If you need a mutable reference, change it to `&mut self` instead.
// */
impl MyHashMap {
/** Initialize your data structure here. */
fn new() -> Self {
let mut v = Vec::with_capacity(100000);
v.resize(100000, -1);
MyHashMap {
data:v
}
}
/** value will always be non-negative. */
fn put(&mut self, key: i32, value: i32) {
self.data[key as usize] = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
fn get(&self, key: i32) -> i32 {
match self.data.get(key as usize) {
Some(i) => *i,
None => -1,
}
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
fn remove(&mut self, key: i32) {
self.data[key as usize] = -1;
}
}
执行用时 : 28 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 4.8 MB , 在所有 Rust 提交中击败了 25.00% 的用户
2019-09-26 01:08