This is the 17th day of my participation in Gwen Challenge
Designing hash mappings (706)
Topic describes
Design a HashMap without using any built-in hash table libraries.
Implement MyHashMap class:
MyHashMap()Initialize an object with an empty mapvoid put(int key, int value)Insert a key-value pair into the HashMap(key, value). ifkeyIf it already exists in the map, its corresponding value is updatedvalue。int get(int key)Return specifickeyThe mappingvalue; If the mapping does not containkeyReturns a mapping of- 1。void remove(key)If the mapping existskeyIs removedkeyAnd what that corresponds tovalue。
Example:
Input: ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2] : [NULL, NULL, NULL, 1, -1, NULL, 1, NULL, -1] myHashMap.put(1, 1); // myHashMap is now [[1,1]] myhashmap.put (2, 2); / / myHashMap now for [[1, 1], [2]] myHashMap. Get (1); // return 1, myHashMap is now [[1,1], [2,2]] myhashmap.get (3); // Return -1 (not found), myHashMap is now [[1,1], [2,2]] myhashmap.put (2, 1); // myHashMap is now [[1,1], [2,1]] (updating existing values) myhashmap.get (2); // Return 1, myHashMap is now [[1,1], [2,1]] myHashmap.remove (2); // delete data with key 2, myHashMap is now [[1,1]] myhashmap.get (2); // Return -1 (not found), myHashMap is now [[1,1]]Copy the codeprompt
0 <= key, value <= 106- Most call
104次put,get和removemethods
** Advanced: ** Can you solve this problem without using the built-in HashMap library?
Thought analysis
To design a hash map, we can design based on the array and LinkedList in Java. LinkedList has some encapsulation to make the code call more convenient. We can store a LinkedList for each item in the array, and the calculation of hash value can use the operation of complement.
And we need an inner class Pair that holds a key and a value. We need to provide query, add, and delete methods.
The code shown
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(a) {
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)];
}
// Find the list with the same 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){
returnpair.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; }}}}Copy the codeLRU Caching Mechanism (146)
Topic describes
Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism.
Implement the LRUCache class:
LRUCache(int capacity)The capacity is a positive integercapacityInitialize the LRU cacheint get(int key)If the keywordkeyExists in the cache, returns the value of the keyword, otherwise returns- 1。void put(int key, int value)If the keyword already exists, change its data value; If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.
Advanced: Can you do both in O(1) time?
Example 1:
Input [" LRUCache ", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2]. [4, 4], [1], [3], [4] Output [NULL, NULL, NULL, 1, NULL, -1, NULL, -1, 3, 4] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the codeTip:
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104- Most call
3 * 104次get和put
Thought analysis
LRU cache mechanism is to delete the latest at least use a cache mechanism, we can not directly use Java built-in LinkedHashMap, but can use HashMap, and then customize a bidirectional linked list; In the topic, we can use virtual head node and virtual tail node to carry out a universal operation of linked list, that is, we do not need to judge the special position of special processing, to simplify our processing process.
Finding and adding values from the cache involves deleting the existing target node if it is already in the LRU’s data structure, and also moving the node to the header node. We can separate these two operations into methods because both operations are called.
Note also that our virtual head and tail nodes are always at the head/tail of the list, so we should also be careful when deleting nodes. If the list is full, we need to delete the first node before the tail node when putting nodes.
Finally, note that keys in a HashMap store ints, while values store linked list nodes, and each linked list node stores corresponding keys and values.
The code shown
Solution a:
class LRUCache {
int size = 0;
int capacity = 0;
private DListNode head;
private DListNode tail;
private Map<Integer,DListNode> map = null;
//1. Find data from cache
//2. Add data from the cache
//3. Delete data from the cache
// Remove the specified node and add the node to the header (note that the virtual head node remains the virtual head node)
// Also note that bidirectional lists store keys,value hashmaps store keys, and dlistNodes store keys
// If it is full, the last node of the end node is deleted
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) {// Delete the node at the specified location
removeNode(node);
// Move the node to the head
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){// Remove data from the cache
// 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; }}}Copy the codeconclusion
Hash table related topics, design a hash map and LRU is a very classic problem, must firmly grasp.