Java实现 LeetCode 706 设计哈希映射（数组+链表）
2024-08-29 22:29:27
706. 设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射
具体地说，你的设计应该包含以下的功能
put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。
示例：
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 (未找到)
注意：
所有的值都在 [0, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。
class MyHashMap {
/** Initialize your data structure here. */
class Entry {
int key;
int value;
Entry next;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
int cap = 200000;
Entry [] arr = new Entry[cap];
public MyHashMap() {
}
/** value will always be non-negative. */
public void put(int key, int value) {
if(arr[key % cap] != null) {
boolean isFound = false;
Entry entry = arr[key % cap], last = null;
while(entry != null) {
last = entry;
if(entry.key == key) {
entry.value = value;
isFound = true;
break;
}
entry = entry.next;
}
if(!isFound) {
last.next = new Entry(key, value);
}
} else {
arr[key % cap] = new Entry(key, value);
}
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
Entry entry = arr[key % cap];
while(entry != null) {
if(entry.key == key) {
return entry.value;
}
entry = entry.next;
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
Entry entry = arr[key % cap], prev = null;
while(entry != null) {
if(entry.key == key) {
if (prev == null) {
arr[key % cap] = entry.next;
} else {
prev.next = entry.next;
}
break;
}
prev = entry;
entry = entry.next;
}
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
最新文章
- C#使用GET、POST请求获取结果
- walk around by The provided App differs from another App with the same version and product ID 分类： Sharepoint 2015-07-05 08:14 4人阅读 评论(0) 收藏
- 理解一下单片机的I2C和SPI通信
- ASP.NET 大文件上传
- Visual Studio Code 与 Github 集成
- jquery.tochart.js
- SQL 编码标准
- Windows下使用console线连接思科交换机
- Django（五）母版继承、Cookie、视图装饰器等
- 多线程之CEvent
- template.js artTemplate 简洁语法官网下载不了 template.js artTemplate 新下载地址
- NLP-训练个model出来写诗
- Xcode 6 免证书真机调试
- hadoop学习---运行第一个hadoop实例
- Haskell语言学习笔记（49）ByteString Text
- HDU - 1051 Wooden Sticks 贪心 动态规划
- Flink-on-yarn
- 原生JS,运动的小人
- fastjson 应用
- 使用BIND安装智能DNS服务器（二）---配置rndc远程控制