试写出Map接口的简单实现，接口定义如下： publi

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 MyMap<k> implements Map<k> { // 使用数组来存储键值对 private Entry<k>[] entries; private int size; // 构造函数，初始化数组大小 public MyMap() { entries = (Entry<k>[]) new Entry[16]; size = 0; } @Override public V get(Object key) { // 计算键的哈希值，确定在数组中的索引位置 int index = hash(key) % entries.length; Entry<k> entry = entries[index]; while (entry!= null) { if (entry.key.equals(key)) { return entry.value; } entry = entry.next; } return null; } @Override public V put(K key, V value) { // 计算键的哈希值，确定在数组中的索引位置 int index = hash(key) % entries.length; Entry<k> entry = entries[index]; Entry<k> prev = null; while (entry!= null) { if (entry.key.equals(key)) { V oldValue = entry.value; entry.value = value; return oldValue; } prev = entry; entry = entry.next; } // 如果键不存在，则创建新的键值对并插入 Entry<k> newEntry = new Entry<>(key, value); if (prev == null) { entries[index] = newEntry; } else { prev.next = newEntry; } size++; // 如果数组使用率超过一定阈值，进行扩容 if (size >= entries.length * 0.75) { resize(); } return null; } // 哈希函数，这里简单使用对象的hashCode方法 private int hash(Object key) { return key == null? 0 : key.hashCode(); } // 扩容方法，创建一个更大的数组，并重新散列所有键值对 private void resize() { Entry<k>[] newEntries = (Entry<k>[]) new Entry[entries.length * 2]; for (Entry<k> entry : entries) { while (entry!= null) { int index = hash(entry.key) % newEntries.length; Entry<k> newEntry = newEntries[index]; if (newEntry == null) { newEntries[index] = entry; } else { while (newEntry.next!= null) { newEntry = newEntry.next; } newEntry.next = entry; } entry = entry.next; } } entries = newEntries; } // 内部类，用于表示键值对 private static class Entry<k> { K key; V value; Entry<k> next; public Entry(K key, V value) { this.key = key; this.value = value; this.next = null; } } } </k></k></k></k></k></k></k></k></k></k></k></k></k></k>

不考虑扩容,数组+链表做法：
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);
    }
}

可以来个hashmap默写吗？🤣