Links to the original text: https://blog.csdn.net/m0_37499059/article/details/80623438

I. Code Implementation

1) MyMap interface

package com.cxx.map.HashMap;
/**
 * @Author: cxx
 * Implementing map interface by oneself
 * @Date: 2018/6/8 11:18
 */
public interface MyMap<K,V> {
    //Size
    int size();
    //Is it empty?
    boolean isEmpty();
    //Get elements by key
    Object get(Object key);
    //Adding elements
    Object put(Object key,Object value);
    interface Entry<k,v>{
        k getkey();
        v getValue();
    }
}

2) MyHashMap implementation class

package com.cxx.map.HashMap;
import java.util.Map;
import java.util.Set;
/**
 * @Author: cxx
 * Realize HashMap by oneself
 * Bottom structure: array + linked list
 * @Date: 2018/6/8 11:30
 */
public class MyHashMap<K,V> implements MyMap {
    //Default capacity 16
    private final int DEFALUT_CAPACITY=16;
    //Internal storage structure
    Node[] table = new Node[DEFALUT_CAPACITY];
    //length
    private int size=0;
    //keySet
    Set<K> keySet;
    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public Object get(Object key) {
        int hashValue = hash(key);
        int i=indexFor(hashValue,table.length);
        for (Node node=table[i];node!=null;node=node.next){
            if (node.key.equals(key)&&hashValue==node.hash){
                return node.value;
            }
        }
        return null;
    }

    @Override
    public Object put(Object key, Object value) {
        //Get hash value by key
        int hashValue=hash(key);
        //Through hash, find the location where the key should be placed.
        int i=indexFor(hashValue,table.length);
        //i location already has data, add elements to the list
        for (Node node=table[i];node!=null;node=node.next){
            Object k;
            //And there's this key in the array that overrides its value
            if (node.hash==hashValue&&((k=node.key)==key||key.equals(k))){
                Object oldValue=node.value;
                node.value=value;
                //Return oldValue
                return oldValue;
            }
        }
        //If the i location has no data, or the i location has data, but the key is a new key, add a node
        addEntry(key,value,hashValue,i);
        return null;
    }

    public void addEntry(Object key,Object value,int hashValue,int i){
        //If the size of the original array is exceeded, the array is enlarged
        if (++size==table.length){
            Node[] newTable=new Node[table.length*2];
            System.arraycopy(table,0,newTable,0,table.length);
            table=newTable;
        }
        //Data to position i
        Node eNode=table[i];
        //Add a node that points next to the previous node
        table[i]=new Node(hashValue,key,value,eNode);
    }

    //Get the insertion position
    public int indexFor(int hashValue,int length){
        return hashValue%length;
    }
    //Get hash value
    public int hash(Object key){
        return key.hashCode();
    }

    //Static inner class: Node node implements Entry interface
    static class Node implements MyMap.Entry{
        int hash;//hash value
        Object key;//key
        Object value;//value
        Node next;//Point to the next node (singleton table)
        Node(int hash,Object key,Object value,Node next){
            this.hash=hash;
            this.key=key;
            this.value=value;
            this.next=next;
        }
        @Override
        public Object getkey() {
            return this.key;
        }

        @Override
        public Object getValue() {
            return this.value;
        }
    }
}

3) MyHashMapTest test class

package com.cxx.map.HashMap;
import java.util.HashMap;
import java.util.Map;
/**
 * @Author: cxx
 * @Date: 2018/6/8 11:41
 */
public class TestMap {
    public static void main(String[] args) {
        MyMap map = new MyHashMap();
        map.put("a1",1);
        map.put("a2",2);
        System.out.println("size:"+map.size());
        System.out.println("isEmpty:"+map.isEmpty());
        System.out.println(map.get("a1"));
    }
}

II. Understanding

The underlying implementation of HashMap is mainly based on arrays and linked lists. HashMap calculates the hash value by hashCode of key, calculates the position of the hash value in the array, and places the newly inserted element in this position of the array if the hash value of the newly inserted element is the same as that of the existing element in this position. A hash conflict occurs, where new elements are inserted through the list.  
Reference: http://www.cnblogs.com/chengxiao/p/6059914.html

Summary

Simply speaking, HashMap is composed of arrays + linked lists. Arrays are the main body of HashMap, and linked lists exist mainly to solve hash conflicts. If the location of the array does not contain linked lists (the next entry of the current entry points to null), then for searching, adding and other operations are very fast, only one addressing is needed. The array contains linked lists. For addition operations, the time complexity is O(n). First, the list is traversed, that is, the existence is covered, otherwise it is added. For search operations, it is still necessary to traverse the linked list, and then the key object equals method is used to search one by one. Therefore, performance considerations, the fewer lists in HashMap, the better performance.