This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
Topic describes
This is 706. Design hash mapping on LeetCode.
Design a HashMap without using any built-in hash table libraries.
Implement MyHashMap class:
- MyHashMap() initializes the object with an empty map
- Void put(int key, int value) Inserts a key/value pair into the HashMap. If the key already exists in the map, its corresponding value value is updated.
- Int get(int key) returns the value mapped to a particular key; If the mapping does not contain key, -1 is returned.
- Void Remove (key) If a key mapping exists, remove the key and its corresponding value.
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 codeTip:
- 0 <= key, value <=
- Call the PUT, GET, and remove methods up to 10410^4104 times
Advanced: Can you solve this problem without using the built-in HashMap library?
Simple array solution
Unlike yesterday’s 705. Design hash sets.
We need to record not only whether an element exists or not, but also what the value of that element is.
0<=key,value<=1060 <=key,value<=10 ^60<=key,value<=106, and kv
We can use arrays of type int to implement hash table functionality.
class MyHashMap {
int INF = Integer.MAX_VALUE;
int N = 1000009;
int[] map = new int[N];
public MyHashMap(a) {
Arrays.fill(map, INF);
}
public void put(int key, int value) {
map[key] = value;
}
public int get(int key) {
return map[key] == INF ? -1 : map[key];
}
public void remove(int key) { map[key] = INF; }}Copy the code- Time complexity: O(1)O(1)O(1)
- Space complexity: O(1)O(1)O(1)
The linked list method
In the same way that we design hash sets, we can use “linked lists” to build maps, which is the easiest way to implement them in engineering.
class MyHashMap {
static class Node {
int key, value;
Node next;
Node(int _key, int_value) { key = _key; value = _value; }}// This value can be very small due to the use of "linked lists"
Node[] nodes = new Node[10009];
public void put(int key, int value) {
// Get the hash bucket location based on key
int idx = getIndex(key);
// Check whether the list already exists
Node loc = nodes[idx], tmp = loc;
if(loc ! =null) {
Node prev = null;
while(tmp ! =null) {
if (tmp.key == key) {
tmp.value = value;
return;
}
prev = tmp;
tmp = tmp.next;
}
tmp = prev;
}
Node node = new Node(key, value);
/ / head interpolation
// node.next = loc;
// nodes[idx] = node;
/ / stern interpolation
if(tmp ! =null) {
tmp.next = node;
} else{ nodes[idx] = node; }}public void remove(int key) {
int idx = getIndex(key);
Node loc = nodes[idx];
if(loc ! =null) {
Node prev = null;
while(loc ! =null) {
if (loc.key == key) {
if(prev ! =null) {
prev.next = loc.next;
} else {
nodes[idx] = loc.next;
}
return; } prev = loc; loc = loc.next; }}}public int get(int key) {
int idx = getIndex(key);
Node loc = nodes[idx];
if(loc ! =null) {
while(loc ! =null) {
if (loc.key == key) {
returnloc.value; } loc = loc.next; }}return -1;
}
int getIndex(int key) {
// Since the length of nodes is only 10009, the corresponding decimal 10011100011001 (total length is 32 bits, other bits are 0)
// In order for the high hash of the key to participate in the calculation, the hashCode is shifted right xor
// Make the high and low randomness of hashCode appear in the lower 16 bits
int hash = Integer.hashCode(key);
hash ^= (hash >>> 16);
returnhash % nodes.length; }}Copy the code- Time complexity: Because there is no expansion logic, the worst-case complexity is O(n)O(n)O(n) O(n) and the general complexity is O(1)O(1)O(1) O(1)
- Space complexity: O(1)O(1)O(1)
Open addressing solution
In addition to using “linked lists” to resolve hash conflicts, you can also use “open addressing” to resolve hash conflicts.
class MyHashMap {
static class Node {
int key, value;
Node next;
boolean isDeleted;
Node(int _key, int_value) { key = _key; value = _value; }}// The offset of the conflict
int OFFSET = 1;
Node[] nodes = new Node[10009];
public void put(int key, int value) {
int idx = getIndex(key);
Node node = nodes[idx];
if(node ! =null) {
node.value = value;
node.isDeleted = false;
} else {
node = newNode(key, value); nodes[idx] = node; }}public void remove(int key) {
Node node = nodes[getIndex(key)];
if(node ! =null) node.isDeleted = true;
}
public int get(int key) {
Node node = nodes[getIndex(key)];
if (node == null) return -1;
return node.isDeleted ? -1 : node.value;
}
GetIndex always returns an empty position when there is no key in the map
// When a map contains a key, getIndex always returns the key's location
int getIndex(int key) {
int hash = Integer.hashCode(key);
hash ^= (hash >>> 16);
int n = nodes.length;
int idx = hash % n;
while(nodes[idx] ! =null&& nodes[idx].key ! = key) { hash += OFFSET; idx = hash % n; }returnidx; }}Copy the code- Time complexity: O(1)O(1)O(1) O(1) in general, O(n)O(n)O(n) O(n) in extreme cases
- Space complexity: O(1)O(1)O(1)
The last
This is the No.706 of our “Brush through LeetCode” series. The series started on 2021/01/01.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.