手写hashmap Java

hashmap 内部有一个数组，这个数组保存的是若干个内部类Entry， Entry有3个属性，key,value,next（Entry）
next（Entry）是指向下一个Entry的指针，目的是为了解决hash冲突而设计的链表

1.动态扩容
当调用put方法，函数会判断map的当前size/默认长度*负载因子，如果超过这个值，会动态扩容，原理是取出所有Entry（递归）到一个List,新建一个新的hash表，通过hash函数重新存储到这个表里

2.hash冲突
首先拿到当前key的hashcode取出Entry，对比key和Entry的key值，相等则取出Entry的value，不等则向下拿next（递归），直到相等，最后取出Entry的value

手写源码：

package test; public interface MyMap { public V put(K k,V v); public V get(K k); public int size(); public interface Entry { public K getKey(); public V getValue(); } }

package test; import java.util.ArrayList; import java.util.List; public class MyHashMapimplements MyMap{private static int defaultLength=16; private static double defaultLoader=0.75; private Entry[] table=null; private int size=0; public MyHashMap(int a,double b){ defaultLength=a; defaultLoader=b; }public MyHashMap(){ this(defaultLength,defaultLoader); }@Override public V put(K k, V v) { if(size>defaultLoader*defaultLength){ zpSize(); }if(table==null) { table = new Entry[defaultLength]; } int index = getIndex(k); Entry kvEntry = table[index]; if(kvEntry == null){ table[index]=newEntry(k,v,null); size++; }else { table[index]=newEntry(k,v,kvEntry); } return table[index].getValue(); }private void zpSize() { Entry[] newTbale=new Entry[2*defaultLength]; againHash(newTbale); }private void againHash(Entry[] newTbale) { List> list=new ArrayList(); for(int i=0; i0){ size=0; defaultLength=defaultLength*2; table=newTbale; for(Entry entry:list){ if(entry.next!=null){ entry.next=null; } put(entry.getKey(),entry.getValue()); } }}private void addNext(Entry kvEntry,List list) { if(kvEntry.next!=null){ list.add(kvEntry.next); addNext(kvEntry.next,list); } }private Entry newEntry(K k,V v,Entry next){ return new Entry<>(k,v,next); }private int getIndex(K k){ int m=defaultLength; int i = k.hashCode() % m; return i>0?i:-i; }@Override public V get(K k) { int index = getIndex(k); Entry kvEntry = table[index]; if(k == kvEntry.getKey() || k.equals(kvEntry.getKey())){ return kvEntry.getValue(); }returngetNext(k, kvEntry); }private V getNext(K k, Entry kvEntry) { if(kvEntry.next==null){ return kvEntry.getValue(); } if(k == kvEntry.next.getKey() || k.equals(kvEntry.next.getKey())){ return kvEntry.next.getValue(); } returngetNext(k,kvEntry.next); }@Override public int size() { return 0; }class Entry implements MyMap.Entry{K k; V v; Entry next; public Entry(K k,V v,Entry next){ this.k=k; this.v=v; this.next=next; }@Override public K getKey() { return k; }@Override public V getValue() { return v; } } }

测试：

package test; public class A { public static void main(String[] args) { //List list= Arrays.asList("3","1","2"); //list.sort(String::compareTo); //list.sort(Comparator.reverseOrder()); //list.forEach((a)-> System.out.println(a)); MyHashMap map=new MyHashMap(); for(int i=1; i<1000; i++){ map.put(i,i); }for(int i=1; i<1000; i++){ System.out.println(i+"----"+map.get(i)); } } }

【手写hashmap】