preface
I can see the interview question of Dacheng today. To be honest, I really understand HashMap, and I have read the source code for many times. I believe most of my friends can have this degree. However, you suddenly come to such a hand, or a little confused circle! So, today, I will sort out for you and help you master it!
Normally, when meeting handwritten HAHSMAP in the interview, it is basically required to implement GET and PUT methods. I will be a little bit more comprehensive, and then add a REMOVE method.
JDK7, 8HashMap get(), put() method flow
JDK7, 8HashMap expansion details
<font size=”5″>== <font size=”5″>==
Handwritten LRU, LFU, let the interviewer to you sit up and take notice!!
What is not secure about HashMap in JDK7, JDK8?
All right, all right, without further ado, let’s get started.
Roll up your sleeves and start building
Implement array + linked list
As we all know, HashMap is both JDK7 and JDK8, the bottom layer is array + linked list, but JDK8 more than a red-black tree, according to the truth will not have handwritten red-black tree, 😰.
Since it’s an array plus a linked list, I’ll implement a linked list
Refer to ==JDK8== source code
We don’t have to be that advanced, 🤭
static class Node { int key, value; // Save the Key and Value Node next; Public Node(int key, int value) {this.key = key; this.value = value; }}If you have a linked list, you can create an array (the interview process basically does not require expansion, so we will simply define a similar value to the array).
private final int CAPACITY = 10000;
Node[] nodes = new Node[CAPACITY];Achieve the Key corresponding array index method
Reference source
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key ! = null && key.equals(k)))) return first; if ((e = first.next) ! = null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }(Warm Tip: If you can’t see clearly, you can open the picture on a new TAB with the right mouse button)
implementation
Since int is the basic data type, we use ==Integer.hashCode(int value)==
Integer.hashCode(int value) returns exactly the value you passed in
public static int hashCode(int value) {
return value;
}private int getIndex(int key) {
int hash = Integer.hashCode(key);
//高16位异或低16位
hash ^= (hash >>> 16);
//与数组长度取模，得到对应的索引下标
return hash % CAPACITY;
}Implementing the GET method
The process is very simple
- Gets the corresponding index index of the key passed in
- Get the first node of the linked list for the corresponding index
- Judge not empty
- If the Key of the first node of the linked list is the target Key, then the corresponding Value is directly returned. If not, then the list is traversed to get, if the completion of the traversal does not return a Value Value, then the HashMap does not have this data, then -1 is returned.
public int get(int key) { int idx = getIndex(key); Node now = nodes[idx]; if (now ! = null) { if (now.key == key) { return now.value; } else { while (now ! = null) { if (now.key == key) { return now.value; } now = now.next; } } } return -1; }Reference source
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) {/ / if it is the first node, then returned directly if (first. The hash = = hash && / / always check first node ((k = first. Key) = = key | | (key! = null && key.equals(k)))) return first; if ((e = first.next) ! If (first instanceof treeNode) return ((treeNode <K,V>)first).getTreeNode(hash, key); / / traversal access do {the if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); }} // return null if not already; }Implementing the PUT method
The process is introduced
Note: We need to save the previous node, so that if put is a new key-value pair, we can get the last node in the list that is not null
- Gets the index value corresponding to the Key
- If it is empty, it means that the linked list corresponding to the index is empty, and a new node can be directly created to add
- If it is not empty, it will loop through, update prev during the traversal, and return value if it is found during the traversal
- If the traversal has not returned, it means that there is no node to add, then according to whether the prev is null add;
public void put(int key, int value) { int idx = getIndex(key); Node now = nodes[idx], tmp = now; if (tmp ! = 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); if (tmp ! = null) { tmp.next = node; } else { nodes[idx] = node; }}Implementing the remove method
The process is similar to the GET method, except that we need == to save the previous node == that needs to be deleted
Public void remove(int key) {int idx = getIndex(key); // Node now = nodes[idx]; // Now! = null) {// save Node prev = null; // while (now! = null) {// If (now.key == key) {// There are two situations here //1. If the node to be deleted is the first node, then the first node bit corresponding to the current array subscript is the next node. If not, then having the next node of the previous node point to the next node of the current node to be deleted accomplishes the deletion effect. = null) { prev.next = now.next; }else { nodes[idx] = now.next; } now. Next = null;} now. Next = null; return; } // If not found, make the previous node point to the current node, and the current node point to the next node prev = now; now = now.next; }}}Test the
public static void main(String[] args) { MyHashMap map = new MyHashMap(); The map. The put (1, 1); The map. The put (2, 2); The map. The put (40); The map. The put (2200); System.out.println(map.get(1)); System.out.println(map.get(2)); }
The complete code
public class MyHashMap { static class Node { int key, value; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } private final int CAPACITY = 10000; Node[] nodes = new Node[CAPACITY]; public void put(int key, int value) { int idx = getIndex(key); Node now = nodes[idx], tmp = now; if (tmp ! = 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); if (tmp ! = null) { tmp.next = node; } else { nodes[idx] = node; } } public int get(int key) { int idx = getIndex(key); Node now = nodes[idx]; if (now ! = null) { if (now.key == key) { return now.value; } else { while (now ! = null) { if (now.key == key) { return now.value; } now = now.next; } } } return -1; } public void remove(int key) { int idx = getIndex(key); Node now = nodes[idx]; if (now ! = null) { Node prev = null; while (now ! = null) { if (now.key == key) { if (prev ! = null) { prev.next = now.next; }else { nodes[idx] = now.next; } now.next = null; return; } prev = now; now = now.next; } } } private int getIndex(int key) { int hash = Integer.hashCode(key); hash ^= (hash >>> 16); return hash % CAPACITY; }}The last
I am aCode pipi shrimp, a love of sharing knowledge of mantis shrimp lovers, in the future will continue to update the beneficial blog, look forward to your attention!!
It is not easy to create, if this blog post is helpful to you, I hope you can == thumb up and pay attention to me, thank you for your support, we will see you next time ~~~
== Share outline ==
Big factory interview topic column
Java from entry to the grave learning route directory index
Open source crawler example tutorial directory index