V get(Object key);
V put(K key, V value);
}
要求如下:
1. 要有清晰的数据结构。
2. get()、put()方法是时间复杂度最优为O(1),最坏情况O(n)。
3. 不使用第三方库和 java.util.Map 接口下的实现类
public class MyMap implements Map{
//默认数组长度
private static int defaultLength=16;
private int size=0;
//Entry数组
private Entry[] entrys;
public MyMap(){
this(defaultLength);
}
public MyMap(int length){
entrys = new Entry[16];
}
public Object get(Object key) {
//根据key的HashCode获取数组index
int index = getHashCode(key);
Entry entry = entrys[index];
if(entry!=null){
//遍历链式Entry
while(!entry.key.equals(key)){
entry = entry.nextEntry;
}
return entry.value;
}
return null;
}
public Object put(Object key, Object value) {
//判断是否需要扩展数组长度
if(entrys!=null&&entrys.length==size){
Extension();
}
int index = getHashCode(key);
//获取数组下标位置链表
Entry tempEntry = entrys[index];
if(tempEntry==null){
//如果index处没有链表
tempEntry = new Entry(key,value);
entrys[index]= tempEntry;
size++;
}else{
//如果index处有链表
while(!tempEntry.key.equals(key)){
//如果链表中没有相同的key则追加在尾部
if(tempEntry.nextEntry==null){
tempEntry.nextEntry=new Entry(key,value);
return null;
}
tempEntry = tempEntry.nextEntry;
}
//有相同的key则替换value
tempEntry.value = value;
}
return null;
}
/***
* 根据KEY获取hash值
* @param key
* @return
*/
private int getHashCode(Object key){
if(key!=null){
return key.toString().hashCode()&(defaultLength-1);
}
return 0;
}
/**
* 扩容
*/
private void Extension(){
Entry[] newEntry = new Entry[size*2];
for(int i=0;i<entrys.length;i++){
newEntry[i]=entrys[i];
}
entrys = newEntry;
newEntry = null;
}
}
class Entry{
public Object key;
public Object value;
public Entry nextEntry;
Entry(Object key,Object value){
this.key = key;
this.value = value;
}
}
public class MyMap { Entry[] array; int size; public MyMap(){ this(10); } public MyMap(int initLength){ array = new Entry[initLength]; } // 扩容 public Entry[] expandLength(Entry[] array){ Entry[] newArray = new Entry[array.length * 2 + 1]; for (int i = 0; i < array.length; i++){ newArray[i] = array[i]; } return newArray; } public boolean put(Object key, Object value){ if(size == array.length){ array = expandLength(array); } // 判断键是否已经存在,存在的话则更新 for(int i = 0; i < array.length; i++){ if(array[i].key.equals(key)){ array[i].value = value; return true; } } array[size] = new Entry(key, value); size++; return true; } public Object get(Object key){ if(size != 0){ for (int i = 0; i < size; i++){ if(array[i].key.equals(key)){ return array[i].value; } } } return null; } public boolean containsKey(Object key){ for(int i= 0; i < array.length; i++){ if(array[i].key.equals(key)) return true; } return false; } public boolean containsValue(Object value){ for (int i = 0; i < array.length; i++){ if(array[i].value.equals(value)){ return true; } } return false; } public void clear(){ Entry[] newArray = new Entry[array.length]; array = newArray; size = 0; } } class Entry{ Object key; Object value; public Entry(Object key, Object value){ this.key = key; this.value = value; } }
package test; import org.junit.Test; /** * @Autre beyond * @Data 2019/10/19 */ public class MyMapTest implements Map { //1.使用array初始数组 //2.定义一个Entry数组类 Entry [] array; //标识当前位置 int size; //3.添加的时候判断是否为空,返回 //查询默认返回null //注意:数组需要扩容ExplanArray。添加如果是重复的需要更新 //设置默认值 public MyMapTest() { this(10); } public MyMapTest(int size) { array=new Entry[size]; } //扩容 public Entry[] explanArray (Entry[] array){ //扩容 Entry []newAarray=new Entry[array.length*2+1]; //扩容以后需要把原来的数据添加到新的数组中 for (int i = 0; i <array.length ; i++) { newAarray[i]=array[i]; } return newAarray; } @Override public Object get(Object key) { for (int i = 0; i <array.length ; i++) { if (array[i].key.equals(key)){ return array[i].value; } } return null; } @Override public Object put(Object key, Object value) { //首先判断数组容量,如果太小需要扩容 if (size==array.length){ array= explanArray(array); } //其次判断是否重复 /*for (int i = 0; i <array.length ; i++) { if (array[i].key.equals(key)){ array[i].value=value; } }*/ //不重复添加数据 array[size]=new Entry(key,value); size++; return null; } class Entry{ Object key; Object value; public Entry(Object key, Object value) { this.key = key; this.value = value; } } } package test; /** * @Autre beyond * @Data 2019/10/19 */ public interface Map<K,V> { V get(Object key); V put(Object key,Object value); } /* MyMapTest myMapTest=new MyMapTest(); myMapTest.put("chen","zhuang");*/
不考虑扩容,数组+链表做法: public class NowcoderMap implements Map { private final int initSize = 16; LinkedList<Node>[] nodes = new LinkedList[initSize]; class Node { Object K; Object V; public Node(Object key, Object value) { K = key; V = value; } } @Override public Object get(Object key) { Object obj = nodes[hash(key)]; if (obj == null) return null; if (obj instanceof Node) return obj; for (Node node : ((LinkedList<Node>) obj)) { if (node.K.equals(key)) { return node; } } return null; } @Override public Object put(Object key, Object value) { int idx = hash(key); Node entry = new Node(key, value); LinkedList<Node> nodelist = nodes[idx]; if (nodelist == null) { LinkedList<Node> list = new LinkedList<>(); list.push(entry); nodes[idx] = list; return value; } else { for (Node node : nodelist) { if (node.K.equals(entry.K)) { node.V = entry.V; return value; } } nodelist.push(entry); return value; } } private int hash(Object key) { return key == null ? 0 : key.hashCode() & ((initSize >> 2) - 1); } }