手写HashMap

首先先写个Map接口

package writeMap;

public interface Map {
    V put(K k,V v);
    V get(K k);
    int size();

    interface Entry{
        K getKey();
        V getValue();
    }
}

接着写HashMap

package writeMap;
import java.util.*;
public class HashMap1  implements Map{
    private Entry table[]=null;
   int size=0;


    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public HashMap1() {
        this.table = new Entry[16];
    }

  private int hash(K k){
        int index=k.hashCode()%16;
        return index>=0?index:-index;
  }
    @Override
    public V put(K k, V v) {
        int index = hash(k);
    Entryentry= table[index];
    if (null==entry){
        table[index]=new Entry<>(k,v,index,null);

    }else {
        table[index]=new Entry<>(k,v,index,entry);
       }
    size++;
    return table[index].getValue();
    }

    @Override
    public V get(K k) {
        if (size == 0) {
            return null;
        }
        int index = hash(k);
        Entry entry = findValue(table[index], k);
        return entry==null?null:entry.getValue();

    }
    private Entry findValue(Entry entry,K k){
        if (k.equals(entry.getKey())|| k==entry.getKey()){
            return entry;
        }else {
            if (entry.next!=null){
                return findValue(entry.next,k);
            }
        }return null;
    }

        @Override
    public int size() {
        return size;
    }

    class Entry implements Map.Entry{
        K k; V v; int hash; Entry next;

        public Entry(K k, V v, int hash, Entry next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }
}

测试！！！

package writeMap;

public class Test {
    public static void main(String[] args) {
        Map map1 = new HashMap1<>();
        String value = map1.put("Bean", "帅哥");
        System.out.println(value);
        System.out.println(map1.get("Bean"));
    }
}

因为以上代码并不难理解，因此不做讲解，自行研究即可！！！ 

 测试发现链表太长了，查找效率可以说是非常查了，所以jdk8中引入了红黑树来提高查找效率。

下面七个结点，index都相同，如果需要查找007结点，不用红黑树需要查找七次，使用了红黑树只需要查找4次，大大提高了查找效率，这就是为什么要JDK8要引入红黑树的原因！！！