如何快速自己实现Map

　　第一步： 定义一个接口public interface MyMap {      /**      * 向集合中插入值      *      * @param k      * @param v      * @return      */     V put(K k, V v);      /**      * 根据Key 获取集合中的值      *      * @param k      * @return      */     V get(K k);      /**      * 获取集合中元素个数      *      * @return      */     int size();      /**      * 清空      */     void clear();       /**      * 判断是否存在 某值      *      * @param value      * @return      */     boolean containsValue(V value);       /**      * 判断是否存在 某键      *      * @param key      * @return      */     boolean containsKey(K key);       /**      * 判断是否为空      *      * @return      */     boolean isEmpty();      /**      * 用于获取集合中,键值对的对象      *      * @param       * @param       */     interface Entry {         /**          * 获取 Key          *          * @return          */         K getKey();          /**          * 获取 Value          *          * @return          */         V getValue();          /**          * 设置 Value          *          * @param value          * @return          */         V setValue(V value);          /**          * 获取 next          *          * @return          */         Entry getNext();          /**          * 设置 next          *          * @param next          * @return          */         Entry setNext(Entry next);     } }
　　对上述编写的接口以及内容进行说明：V put(K k, V v);V get(K k);int size();void clear();boolean containsValue(V value);boolean containsKey(K key);boolean isEmpty();interface Entry {}第二步 定义一个类实现 这个接口
　　首先定义这个类的成员变量/**   *  用于存放 Entry 数据   */ private Entry[] table = null;  /**   * 记录HashMap 的元素个数   */ private int size;  /**   * HashMap 集合中数组的默认长度 2^4 位移算法   */ private static int defaultLength = 1 << 4;   /**   * 默认加载因子 0.75   */ private static double defaultLoad = 0.75;
　　V put（K k，V v）		@Override     public V put(K k, V v) {         if (table == null) {             table = new Entry[defaultLength];         }          if (size >= defaultLength * defaultLoad) {             resize();         }          int index = getIndex(k, defaultLength);          MyMap.Entry entry = table[index];         while (entry != null) {             if (entry.getKey().equals(k)) {                 return entry.setValue(v);             } else {                 entry = entry.getNext();             }         }         table[index] = new Entry<>(k, v, table[index]);         this.size++;         return v;     }
　　执行过程:
　　第一步 判断该集合是否需要扩容;
　　第二步 计算位置 需要将该元素放置在哪里;
　　第三步 判断是否是修改(可能计算的位置已经有元素存在);
　　第四步 该位置可能已经形成链表(所以需要判断下一个元素)
　　第五步 创建 Entry 元素 并存放在 table 的 index 下标上。
　　int getIndex(K k,int length)private int getIndex(K k, int length) {         // HashMap 是允许 null 值 和 null key         if (k == null) {             return 0;         }         // 计算的 hashCode码值 过大  如何处理         // 00000100  4      00000111	7         // 00000010  2		00000010	2         // 00000000  0		00000010	2         int hash = k.hashCode();         return hash & (length - 1); }
　　知识点  计算下标的方法一般有两种:
　　&(与)算法 ---- 与 得到的值一定不会大于这两个数的最小值 [0,最小值]
　　模算法 ---- 取模 后得到的值一定是比取模的数小 [0,取模数)
　　计算下标： hashCode 是根据对象的地址或者字符串的值计算得到的 int 类型的数值
　　特点： 同一对象多次调用hashCode()方法,必须返回相同的数值   [储存哪个位置  在哪个位置获取] 即调用多次 如果两个对象根据 equals() 方法比较是相等的,那么两个对象调用hashCode()方法返回的结果必须相等 如果两个对象根据equals() 方法比较是不相等的,那么两个对象调用hashCode()方法返回的结果不一定不相等
　　V get（K k）public V get(K k) {         if (table != null) {             int index = getIndex(k, defaultLength);             MyMap.Entry entry = table[index];             while (entry != null) {                 if (entry.getKey() != null && entry.getKey().equals(k)) {                     return entry.getValue();                 } else {                     entry = entry.getNext();                 }             }         }         return null; }
　　执行过程：
　　第一步：根据 getIndex(K k, int length) 查询下标 (注意此时获取的下标可能代表好多值)
　　第二步: 根据 index 获取 Entry
　　第三步: 循环判断 需要满足两个条件(1.entry 不为空 2.entry 的key等于该值) ;如果不满足则获取下一个 entry 继续判断
　　void clear()public void clear() {         Entry[] tab;         if ((tab = table) != null && size > 0) {             size = 0;             for (int i = 0; i < tab.length; ++i) {                 tab[i] = null;             }         } }
　　boolean containsValue(V value)public boolean containsValue(V value) {         Entry[] tab = table;         if (tab != null && size > 0) {             for (MyMap.Entry e : tab) {                 for (; e != null; e = e.getNext()) {                     V v = e.getValue();                     if (v == value) {                         return true;                     } else if (value != null && value.equals(v)) {                         return true;                     }                 }             }         }         return false; }
　　执行过程:
　　第一步: 将类的成员变量 赋值给该方法中的成员变量
　　第二步: 判断该成员变量是否为空,若为空直接返回 false
　　第三步: 循环遍历 Entry ,再次遍历 Entry 链表中的所有元素
　　第四步: 需要考虑到 V 可能是 对象，所以不能简单的通过 == 来判断。
　　boolean containsKey(K key)public boolean containsKey(K key) {         // 1.计算该key 对应的 hashCode         int index = getIndex(key, defaultLength);         return getEntry(index, key); }  private boolean getEntry(int hash, K key) {         Entry[] tab = table;         if (tab != null) {             MyMap.Entry entry = table[hash];             while (entry != null) {                 if (entry.getKey() != null && entry.getKey().equals(key)) {                     return true;                 } else {                     entry = entry.getNext();                 }                 if (entry == key) {                     return true;                 }             }         }         return false; }
　　执行过程：
　　第一步： 根据 key 计算出 对应的 hashCode getIndex（K k，int length）；
　　第二步： 将类的成员变量 赋值给该方法中的成员变量；
　　第三步： 判空，如果为 null 直接返回 false；
　　第四步： 不为空，根据 hashCode 获取对应的 Entry，如果 Entry 不为空 循环判断
　　第五步： 如果 entry.getKey() 不为空 且 两者的 equals 比较相同 则返回 true;
　　否则 获取 entry.getNext()，继续判断；如果都不满足 则直接 判断 entry == key。（考虑到对象的存在）
　　boolean isEmpty（）public boolean isEmpty() {         Entry[] tab = table;         return (tab == null) ? true : false; }
　　int size（）public int size() {         return this.size; }
　　void resize（）
　　最重要的是扩容方法private void resize() {          // 重新散列         if (size >= defaultLength * defaultLoad) {             System.out.println(＂-----------------扩容开始----------------＂);             Entry[] newTable = new Entry[defaultLength << 1];             MyMap.Entry entry = null;             for (int i = 0; i < table.length; i++) {                 entry = table[i];                 // while 中的 五行代码每一行都是精髓                 while (entry != null) {                     int index = getIndex(entry.getKey(), newTable.length);                     MyMap.Entry oldEntry = entry.getNext();                     entry.setNext(newTable[index]);                     newTable[index] = (Entry) entry;                     entry = oldEntry;                 }             }             table = newTable;             defaultLength = newTable.length;         } }
　　执行过程：
　　第一步：判断当前的 size 是否大于 当前的默认的长度 * 默认因子
　　第二步：如果不大于，则什么都不用做
　　第三步：如果大于，就需要扩容：
　　a. 定义一个新的 table 用于临时存储 扩容的 Entry 对象
　　b. 定义一个临时变量 entry 用于存储每一个下标的 Entry 对象
　　c. 准备遍历 old 的 table [0,table.length)
　　d. 取出 table[i] 赋值给 b 步骤定义的 entry（这是一个链表）
　　e.while 循环 判断 entry 是否为空
　　以下步骤是操作链表（精华）：拿到节点重新散列（拿到 entry 的 key，以及临时 table 的长度）计算新的下标entry 并不简单，需要处理 key，value以及 next 得有一个中间变量 相当于 a b的值互换 即 c = a，a = b，b = c内部类的实现
　　具有的成员变量：
　　K k；V value
　　MyMap.Entry next；（指针，指向下一个 Entry）。
　　通过 setNext（）方法实现。static class Entry implements MyMap.Entry {          K key;         V value;         MyMap.Entry next;          /**          * 拿到存放的位置后 , 只需要将 key / value 存放进来          * 首先得先有一个 key / value  ---> 创建一个 key/value 对象 来 存储          * 对象如何去创建 我们有一个 Entry ,通过 Entry 的构造方法 来创建          *          * @param key          * @param value          * @param next          */         public Entry(K key, V value, MyMap.Entry next) {             this.key = key;             this.value = value;             this.next = next;         }          @Override         public final K getKey() {             return this.key;         }          @Override         public V getValue() {             return this.value;         }          @Override         public V setValue(V value) {             V oldValue = this.value;             this.value = value;             return oldValue;         }          @Override         public final String toString() {             return key + ＂=＂ + value;         }          @Override         public final boolean equals(Object o) {             if (o == this) {                 return true;             }             if (o instanceof MyMap.Entry) {                 MyMap.Entry<?, ?> e = (MyMap.Entry<?, ?>) o;                 if (Objects.equals(key, e.getKey()) &&                         Objects.equals(value, e.getValue()))                     return true;             }             return false;         }          @Override         public final int hashCode() {             return Objects.hashCode(key) ^ Objects.hashCode(value);         }          @Override         public MyMap.Entry getNext() {             return this.next;         }          @Override         public MyMap.Entry setNext(MyMap.Entry next) {             MyMap.Entry oldNext = next;             this.next = next;             return oldNext;         } }