java hashmap实现思路

阶段:1：先写个ListMap，用ArrayList来装key/value对象。

public class MyListMap {
    private List list = new ArrayList<>();

    private class Node{
        K k;
        V v;
        public Node(K k,V v){
            this.k = k;
            this.v = v;
        }
    }
    public void put(K k,V v){
        Node node = new Node<>(k,v);
        list.add(node);
    }

    public V get(K k){
        for (Node node : list) {
            if(node.k.equals(k)){
                return (V) node.v;
            }
        }
        return null;
    }
}

阶段2：再写个HashMap，用数组来装key/value对象

public class MyHashMap {
    private Node[] nodes = new Node[10000];

    private class Node{
        K k;
        V v;
        public Node(K k,V v){
            this.k = k;
            this.v = v;
        }
    }

    public void put(K k,V v){
//放在数组里的位置：用key的hashcode除以数组长度(即10000)取余
        int index = k.hashCode() % nodes.length;
        this.nodes[index] = new Node(k, v);
    }

    public V get(K k){
        int index = k.hashCode() % nodes.length;
        if(k.equals(nodes[index].k))
            return (V) nodes[index].v;

        return null;
    }
}

阶段2的put方法，会遇到一个问题，不同的key，hashcode会有相同的时候，这样后面放的就会覆盖掉前面的。取名，哈希碰撞。

需要解决这个问题：在key、value对象Node中，增加一个字段，用来保存key的hashcode相等的key/value对象。

对key/value对象Node进行改造

    private class Node{
        K k;
        V v;
//增加一个字段
        Node next;
        public Node(K k,V v){
            this.k = k;
            this.v = v;
        }
    }

对put方法进行改造

    public void put(K k,V v){
        int index = k.hashCode() % nodes.length;
        Node node = new Node(k, v);
        if(null != this.nodes[index]) {
            node.next = this.nodes[index];
        }
        this.nodes[index] = node;
    }

这里把key/value对象给到字段next来存，又有两种方法：头插法，尾插法。

hashmap头插法导致的问题

JDK1.7的HashMap，哈希碰撞时，最后插入的元素会放在前面，这个称为 “头插法”：

        node.next = this.nodes[index];
        this.nodes[index] = node;

关于Java你不知道的那些事之Java8新特性[HashMap优化]_轻狂书生FS的博客-CSDN博客