底层数据结构:数组，链表
支持动态扩容

支持以下操作

put(K key, V value)
getIndex(K k, int length)
get(K k)
getNode(Node node, K k)

MyMap接口

  1. public interface MyMap<K, V> {
  2.     // 向集合中插入数据
  3.     public V put(K k, V v);
  4.     // 根据k 从Map集合中查询元素
  5.     public V get(K k);
  6.     // 获取集合元素个数
  7.     public int size();
  8.     // Entry的作用 === Node节点
  9.     interface Entry<K, V> {
  10.         K getKey();
  11.         V getValue();
  12.         V setValue(V value);
  13.     }
  14. }

具体实现MyHashMap

  1. public class MyHashMap<K, V> implements MyMap<K, V> {
  2.     // 定义table 存放HasMap 数组元素 默认是没有初始化容器 懒加载
  3.     Node<K, V>[] table = null;
  4.     // 实际用到table 存储容量 大小
  5.     int size;
  6.     // HashMap默认负载因子，负载因子越小，hash冲突机率越低
  7.     float DEFAULT_LOAD_FACTOR = 0.75f;
  8.     // table默认初始大小 16
  9.     static int DEFAULT_INITIAL_CAPACITY = 16;
  10.     public V put(K key, V value) {
  11.         // 1.判断table 数组大小是否为空（如果为空的情况下 ，做初始化操作）
  12.         if (table == null) {
  13.             table = new Node[DEFAULT_INITIAL_CAPACITY];
  14.         }
  16.         // 2. 判断是否需要扩容
  17.         // 实际存储大小=负载因子*初始容量=DEFAULT_LOAD_FACTOR0.75*DEFAULT_INITIAL_CAPACITY16=x
  18.         // 如果size>x的时候就需要开始扩容数组,扩容数组大小之前两倍
  19.         if (size > (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)) {
  20.             // 需要开始对table进行属数组扩容
  21.             resize();
  22.         }
  23.         // 3.取出hash值指定下标位置对应的那个Node
  24.         int index = getIndex(key, DEFAULT_INITIAL_CAPACITY);
  25.         Node<K, V> indexNode = table[index];
  26.         Node<K, V> newNode = null;
  28.         // 4.没有发生hash冲突(index冲突)问题
  29.         if (indexNode == null) {
  31.             newNode = new Node<K, V>(key, value, null);
  32.             size++;
  34.         // 5.发生hash冲突(index冲突)问题
  35.         } else {
  36.             Node<K, V> curNode = indexNode;
  37.             //遍历链表的元素
  38.             while (curNode != null) {
  39.                 // 1.key相同，修改值
  40.                 //这里即用到了equals和==是因为 k有可能被重写hashCode方法，并且k有可能是基本数据类型(用==比较)。
  41.                 //equals和==位置不能调换，因为如果k被重写hashCode，假如==在前，比较的是对象的地址
  42.                 if (curNode.getKey().equals(key) || curNode.getKey() == key) {
  43.                     return curNode.setValue(value);
  45.                 //2 key不同，添加到链表末尾
  46.                 //        两种情况: 1.hascode不同但取模余数相同  2.或者hashCode 相同
  47.                 } else if (curNode.next == null){
  49.                     // 说明遍历到最后一个node且该操作不是修改值。创建新的node，下一个结点为indexNode
  50.                         newNode = new Node<K, V>(key, value, indexNode);
  51.                         size++;
  52.                 }
  53.                 //取链表下一个node
  54.                 curNode = curNode.next;
  55.             }
  56.         }
  57.         //将新创建的node放在table[index]
  58.         table[index] = newNode;
  59.         return null;
  60.     }
  61.     // 对table进行扩容
  62.     private void resize() {
  63.         // 1.生成新的table 是之前的两倍的大小 DEFAULT_INITIAL_CAPACITY*2
  64.         Node<K, V>[] newTable = new Node[DEFAULT_INITIAL_CAPACITY << 1];
  65.         // 2.重新计算index索引,存放在新的table里面
  66.         for (int i = 0; i < table.length; i++) {
  67.             //存放在之前的table的Node
  68.             Node<K, V> oldNode = table[i];
  69.             //遍历该链表，将oldTable的值一个个放进新的table中
  70.             while (oldNode != null) {
  71.                 //table[i] = null;// 赋值为null---为了垃圾回收机制能够回收 将之前的node删除
  72.                 //1.重新计算该Node在新table的index
  73.                 K oldK = oldNode.key;
  74.                 int newIndex = getIndex(oldK, newTable.length);
  76.                 //2.这里记录oldNext，因为下面将oldNodex.next指向新table的结点
  77.                 Node<K, V> oldNext = oldNode.next;
  79.                 //3.oldNode每次都插入newTable[newIndex]，如果newTable[newIndex]已经有值，则形成链表
  80.                     oldNode.next = newTable[newIndex];
  81.                     newTable[newIndex] = oldNode;
  83.                 //4.继续取oldNext
  84.                 oldNode = oldNext;
  85.             }
  86.         }
  87.         // 3.将newtable赋值给老的table
  88.         table = newTable;
  89.         DEFAULT_INITIAL_CAPACITY = newTable.length;
  90.         newTable = null;// 赋值为null---为了垃圾回收机制能够回收
  91.     }
  93.     public int getIndex(K k, int length) {
  94.         int hashCode = k.hashCode();
  95.         int index = hashCode % length;
  96.         return index;
  97.     }
  98.     public V get(K k) {
  99.         Node<K, V> node = getNode(table[getIndex(k, DEFAULT_INITIAL_CAPACITY)], k);
  100.         return node == null ? null : node.value;
  101.     }
  102.     public Node<K, V> getNode(Node<K, V> node, K k) {
  103.         while (node != null) {
  104.             if (node.getKey().equals(k)) {
  105.                 return node;
  106.             }
  107.             node = node.next;
  108.         }
  109.         return null;
  110.     }
  111.     public int size() {
  112.         return size;
  113.     }
  115.     // 测试方法.打印所有的链表元素
  116.     void print() {
  117.         for (int i = 0; i < table.length; i++) {
  118.             Node<K, V> node = table[i];
  119.             System.out.print("下标位置[" + i + "]");
  120.             while (node != null) {
  121.                 System.out.print("[ key:" + node.getKey() + ",value:" + node.getValue() + "]");
  122.                 node = node.next;
  123.             }
  124.             System.out.println();
  125.         }
  126.     }
  128.     // 定义节点
  129.     class Node<K, V> implements Entry<K, V> {
  130.         // 存放Map 集合 key
  131.         private K key;
  132.         // 存放Map 集合 value
  133.         private V value;
  134.         // 下一个节点Node
  135.         private Node<K, V> next;
  136.         public Node(K key, V value, Node<K, V> next) {
  137.             super();
  138.             this.key = key;
  139.             this.value = value;
  140.             this.next = next;
  141.         }
  142.         public K getKey() {
  143.             return this.key;
  144.         }
  145.         public V getValue() {
  146.             return this.value;
  147.         }
  148.         public V setValue(V value) {
  149.             // 设置新值的返回老的 值
  150.             V oldValue = this.value;
  151.             this.value = value;
  152.             return oldValue;
  153.         }
  154.     }
  155. }

总结:

在put时再进行容器的初始化，整个过程下来，我觉得最难的那部分就是扩容，当出现索引冲突(hash冲突)时如何处理，这个流程各位朋友自己尝试实现一遍相信会理解很多。