这是我参与更文挑战的第 17 天，活动详情查看： 更文挑战
设计哈希映射（706）
题目描述
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap()用空映射初始化对象void put(int key, int value)向 HashMap 插入一个键值对(key, value)。如果key已经存在于映射中，则更新其对应的值value。int get(int key)返回特定的key所映射的value；如果映射中不包含key的映射，返回-1。void remove(key)如果映射中存在key的映射，则移除key和它所对应的value。
示例：
输入：
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]
解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]
复制代码提示
0 <= key, value <= 106- 最多调用
104次put、get和remove方法
**进阶：**你能否不使用内置的 HashMap 库解决此问题？
思路分析
设计一个哈希映射，我们可以基于 Java 中的数组和 LinkedList 进行设计，LinkedList 进行了一些封装，让代码的调用更方便，我们可以在数组中的每一项存放一个链表，而哈希值的计算可以使用求余运算。
同时我们需要一个内部类 Pair 里面存放的是 key 和 value。我们需要提供查询，添加，删除这三个方法。
代码展示
class MyHashMap {
/** Initialize your data structure here. */
private class Pair{
public int key;
public int value;
public Pair(int key,int value){
this.key = key;
this.value = value;
}
}
private static final int SLOTS_COUNT = 3535;
private LinkedList<Pair>[] slots = null;
public MyHashMap() {
slots = new LinkedList[SLOTS_COUNT];
}
private int hash(int key){
return key % SLOTS_COUNT;
}
/** value will always be non-negative. */
public void put(int key, int value) {
LinkedList<Pair> slot = slots[hash(key)];
if (slot == null){
slots[hash(key)] = new LinkedList<>();
slot = slots[hash(key)];
}
//寻找链表中 key相等的
for (int i = 0; i < slot.size(); i++) {
Pair pair = slot.get(i);
if (pair.key == key){
slot.remove(i);
break;
}
}
slot.add(new Pair(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) {
LinkedList<Pair> slot = slots[hash(key)];
if (slot == null){
return -1;
}
for (int i = 0; i < slot.size(); i++) {
Pair pair = slot.get(i);
if (pair.key == key){
return pair.value;
}
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
LinkedList<Pair> slot = slots[hash(key)];
if (slot == null){
return;
}
for (int i = 0; i < slot.size(); i++) {
Pair pair = slot.get(i);
if (pair.key == key){
slot.remove(i);
break;
}
}
}
}
复制代码LRU 缓存机制（146）
题目描述
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例 1：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
复制代码提示：
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104- 最多调用
3 * 104次get和put
思路分析
LRU 缓存机制是删除最近最少使用一个缓存机制，我们不可以直接使用 Java 内置的 LinkedHashMap，但是可以使用 HashMap，然后自定义一个双向链表；题目中我们可以使用虚拟头结点和虚拟尾节点对链表的操作进行一个普适性，就是不用进行判断特殊位置特殊处理，简化我们的处理流程。
从缓存中查找和添加值，都涉及到如果已经存在 LRU 的数据结构中，我们需要删除已经存在的目标节点，同时还要将该节点移到头部节点中，这两个操作我们可以单独抽离成方法，因为两个操作都被调用到。
还要注意的是我们的虚拟头结点和虚拟尾节点一直是保持在链表的头部/尾部，所以我们在删除节点的时候也要注意，如果链表满了，这个时候 put 节点的时候，需要先删除尾部节点的前面一个节点。
最后我们要注意 HashMap 中的 key 存放的是 int 值，而 value 存放的是链表的节点，同时每个链表的节点中存放的是对应的 key 和 value 值。
代码展示
解法一：
class LRUCache {
int size = 0;
int capacity = 0;
private DListNode head;
private DListNode tail;
private Map<Integer,DListNode> map = null;
//1.从缓存中查找数据
//2.从缓存中添加数据
//3.从缓存中删除数据
//移除指定节点，添加节点到头部（注意虚拟头节点还一直是虚拟头节点） 这两个方法需要注意
//还有需要注意的是双向链表存储的是key,value hashmap 存储的是key,DListNode
//如果满了，删除的是尾结点的上一个节点
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
map = new HashMap<>(capacity);
this.head = new DListNode(-1,-1);
this.tail = new DListNode(-1,-1);
this.head.prev = null;
this.head.next = tail;
this.tail.prev = this.head;
this.tail.next = null;
}
public int get(int key) {
if (size == 0){
return -1;
}
DListNode node = map.get(key);
if (node != null){
//将指定位置节点删除
removeNode(node);
//将该节点移到头部
addNodeToHead(node);
return map.get(key).value;
} else {
return -1;
}
}
public void put(int key, int value) {
DListNode node = map.get(key);
if (node != null){
node.value = value;
removeNode(node);
addNodeToHead(node);
return;
}
if (size == capacity){
map.remove(tail.prev.key);
removeNode(tail.prev);
size--;
}
DListNode node1 = new DListNode(key, value);
addNodeToHead(node1);
map.put(key,node1);
size++;
}
// public void remove(int key){ //从缓存中删除数据
// DListNode node = map.get(key);
// if (node != null){
// removeNode(node);
// map.remove(key);
// }
// }
private void removeNode(DListNode node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addNodeToHead(DListNode node){
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
private class DListNode{
DListNode prev;
DListNode next;
private int key;
private int value;
public DListNode(int key,int value){
this.key = key;
this.value = value;
}
}
}
复制代码总结
哈希表相关的题目，设计一个哈希映射和 LRU 是非常经典的问题，一定要牢牢掌握。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
