---

preface

Today look at the face by see the big factory interview questions, to tell the truth, HashMap feel really understand, source code has seen many times, I believe most small partners can have this degree. But, suddenly give you come such a hand, still have a little muddled circle! So, today I will tidy up for you and help you master!

Normally, when you meet a handwritten HahsMap in an interview, you are basically asked to implement get and put methods, so I will be a little more comprehensive and add a remove method.

JDK7, 8HashMap get(), put() method flow

Detailed expansion of JDK7 and 8HashMap

The key to master

Write LRU and LFU by hand to impress the interviewer!!

Where is the unsafe HashMap in JDK7 and JDK8?

All right, all right, so without further ado, let’s get started.

---

Roll up your sleeves and start building

Implement array + linked list

As we all know, whether JDK7 or JDK8, the bottom layer of HashMap is array + list, but JDK8 has a red black tree, according to the reason, there will not be 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 so advanced, 🤭

static class Node {
    int key, value; // Save the Key and Value of the node
    Node next; // Point to the next node

    public Node(int key, int value) {
        this.key = key;
        this.value = value; }}Copy the code

Once you have the list, you need to add an array. (The interview process basically doesn’t require expansion, so let’s just define a similar value for the array.)

private final int CAPACITY = 10000;
Node[] nodes = new Node[CAPACITY];
Copy the code

---

Obtain the Key corresponding to the 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;
}
Copy the code

Graphic interpretation of the

implementation

Since int is a basic data type, we use == integer.hashcode (int value)==

The Integer. HashCode (int value), on the other hand, returns the value you passed in

public static int hashCode(int value) {
    return value;
}
Copy the code

private int getIndex(int key) {
    int hash= Integer.hashCode(key); / / high16An exclusive or low16positionhash^ = (hash >>> 16); // Obtain the corresponding index by modulo of the array lengthreturn hash % CAPACITY;
}
Copy the code

---

Implement the GET method

The process is simple

1. Gets the index index corresponding to the key passed in
2. Get the first node of the list corresponding to the subscript
3. Judge not empty
4. If the Key of the first node of the list is the target Key, then the corresponding Value is directly returned. If not, then the list is traversed. If no Value is returned, then the HashMap does not have the data and returns -1.

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) {
                    returnnow.value; } now = now.next; }}}return -1;
}
Copy the code

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 return it directlyif (first.hash= =hash&& // always check first node ((k = first.key) == key || (key ! = null && key.equals(k))))return first;
        if ((e = first.next)! = null) {// Do not worry about the red-black tree judgmentif (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 if not alreadyreturn null;
}
Copy the code

---

Implement 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 non-null node in the list

1. Gets the index value corresponding to the Key
2. If the value is empty, the linked list corresponding to the index is empty. You can directly create a node and add it
3. If it is not empty, the loop is traversed. The traversal updates prev, and returns value if found during the traversal
4. If prev is null or not, there is no object to 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; }}Copy the code

---

Implement the remove method

The process is similar to get, except that we need == to save the node == before the node to be deleted

 public void remove(intKey) {// Get the indexintidx = getIndex(key); Node now = nodes[idx]; // Non-null judgmentif(now ! = null) {// Save the former Node Node prev = null; // Look through the searchwhile(now ! = null) {// if foundif(now.key == key) {// There are two cases //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 //2.If not, the deletion effect is achieved by having the node next to the previous node point to the node next to the node currently being deletedif(prev ! = null) { prev.next = now.next;
                 }else {
                     nodes[idx] = now.next; } // Make the next node null, no matter how you delete it.next = null;
                 return; } // If not, make the previous node point to the current node, and the current node point to its next node. now = now.next; }}}Copy the code

---

Test the

public static void main(String[] args) {
    MyHashMap map = new MyHashMap();
    map.put(1.1);
    map.put(2.2);
    map.put(1.40);
    map.put(2.200);

    System.out.println(map.get(1));
    System.out.println(map.get(2));
}
Copy the code

---

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) {
                        returnnow.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);
        returnhash % CAPACITY; }}Copy the code

---

CSDN exclusive benefits come!!

Recently, CSDN has produced an exclusive event, which is the following “Java full stack Knowledge Graph”, the route planning is very detailed, the size is870mm x 560mmFriends can follow the above process for systematic learning, don’t like me at the beginning of no one to take their own random book disorderly learning, systematic and regular learning, it is the most solid foundation, in our line, “The foundation is not strong, the Earth shakes” is particularly obvious.

Finally, if you are interested, you can buy it at your discretion to pave the way for your future!!

---

The last

I am aCode pipi shrimpI am a mantis shrimp lover who loves to share knowledge. I will keep updating my blog in the future. I look forward to your attention!!

Creation is not easy, if this blog is helpful to you, I hope you can == a key three! ==, thanks for your support, see you next time ~~~

Share the outline

Big factory interview questions column

Java from entry to grave learning route directory index

Open source crawler instance tutorial directory index

More exciting content to share, please clickHello World (low low ◡)

---