实现自己的HashMap- 2019-09-21 20:35:53- java
    - 基础: hashmap,java,实现自己的HashMap

    HsahMap1.7jdk原理分析：https://www.jianshu.com/p/068b6d25b593
    HashMap中重要的概念：
    初始化容量直： 1 << 4 map的初始化容量
    最大容量值：1 << 30 map可容纳的最大容量
    扩容因子 ： 0.75 即容量已达到该设置条件,put时会进行扩容
    扩容阈值：扩容阈值=容量(table的size)    扩容因子
    size:map中存储的键值对的数量
    table：存储实体
    实际扩容因子：创建时可由有参构造给出
    实际容量：创建时可由有参构造给出
    扩容次数：可限制扩容
    key允许为null,存储时key为Null,在table中的下标为0.取值时从table[0]中获取链表，查找链表中k为null的节点。
     HashMap使用数组+链表的形式实现的，通过计算key的hash值获取key在数组中对应的下标，添加新的节点到该下标的链表中。
    取值时，通过计算key的hash值获取key在数组中对应的下标，获取该下标上的链表，通过eques方法从链表中找到对应的value。

    以下是代码实现：

    1. public class MyHashMap<K, V> {
    2.         /**
    3.          * 初始化容量 1的4次方
    4.          */
    5.         private final Integer DEFAULT_INITIAL_CAPACITY = 1 << 4;
    6.         /**
    7.          * 最大容量 1的30次方 超过最大量将被最大量所赋值
    8.          */
    9.         private final Integer MAXIMUM_CAPACITY = 1 << 30;
    10.         /**
    11.          * 实际容量
    12.          */
    13.         private Integer capacity;
    14.         /**
    15.          * 默认扩容因子 四分之三
    16.          */
    17.         private final float DEFAULT_LOAD_FACTOR = 0.75f;
    18.         /**
    19.          * 实际扩容因子
    20.          */
    21.         private float loadFactor;
    22.         /**
    23.          * 扩容阈值=容量(table的size)*扩容因子
    24.          */
    25.         private int threshold;
    26.         /**
    27.          * 实际存储
    28.          */
    29.         private MyEntry<K, V>[] table = null;
    30.         /**
    31.          * map 的size  既Map中键值对的数量
    32.          */
    33.         private static int size = 0;
    34.         /**
    35.          * 扩容次数：可做扩容限制
    36.          */
    37.         private static int resizeIndex = 0;
    38.         /**
    39.          * 无参构造
    40.          */
    41.         public MyHashMap() {
    42.             //实际扩容因子
    43.             this.loadFactor = DEFAULT_LOAD_FACTOR;
    44.             //实际容量
    45.             this.capacity = DEFAULT_INITIAL_CAPACITY;
    46.             //扩容阈值
    47.             this.threshold = tableSizeFor(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    48.             //初始化table
    49.             this.table = new MyEntry[DEFAULT_INITIAL_CAPACITY];
    50.         }
    51.         /**
    52.          * @param initialCapacity 初始化容量
    53.          * @param loadFactor      扩容因子
    54.          */
    55.         public MyHashMap(int initialCapacity, float loadFactor) {
    56.             //如果初始化容量大于默认最大容量 则等于最大容量
    57.             if (initialCapacity >= MAXIMUM_CAPACITY) {
    58.                 initialCapacity = MAXIMUM_CAPACITY;
    59.             }
    60.             //实际扩容因子
    61.             this.loadFactor = loadFactor;
    62.             //实际容量
    63.             this.capacity = initialCapacity;
    64.             //计算扩容阈值
    65.             this.threshold = tableSizeFor(initialCapacity, loadFactor);
    66.             //初始化table
    67.             this.table = new MyEntry[initialCapacity];
    68.         }
    69.         /**
    70.          * @param initialCapacity 初始化容量
    71.          */
    72.         public MyHashMap(int initialCapacity) {
    73.             if (initialCapacity >= MAXIMUM_CAPACITY) {
    74.                 initialCapacity = MAXIMUM_CAPACITY;
    75.             }
    76.             //实际容量
    77.             this.capacity = initialCapacity;
    78.             //实际扩容因子
    79.             this.loadFactor = DEFAULT_LOAD_FACTOR;
    80.             //扩容阈值
    81.             this.threshold = tableSizeFor(initialCapacity, loadFactor);
    82.             //初始化table
    83.             this.table = new MyEntry[initialCapacity];
    84.         }
    85.         public V get(K k) {
    86.             if (null == table) {
    87.                 return null;
    88.             }
    89.             if (null == k) {
    90.                 return getForNullKey();
    91.             }
    92.             //计算k对应的hash值,根据hash计算在table中对应下标
    93.             int hash = k.hashCode();
    94.             int index = getIndex(hash, capacity);
    95.             MyEntry<K, V> entry = table[index];
    96.             while (null != entry) {
    97.                 //hash值相同 同时key相同
    98.                 if (hash == entry.getHash() && (k == entry.getK() || k.equals(entry.getK()))) {
    99.                     return entry.getV();
    100.                 }
    101.                 entry = entry.getNext();
    102.             }
    103.             return null;
    104.         }
    105.         /**
    106.          * 获取key为null时的值
    107.          *
    108.          * @return
    109.          */
    110.         private V getForNullKey() {
    111.             MyEntry<K, V> entry = table[0];
    112.             while (null != entry) {
    113.                 if (null == entry.getHash() && null == entry.getK()) {
    114.                     return entry.getV();
    115.                 }
    116.                 entry = entry.getNext();
    117.             }
    118.             return null;
    119.         }
    120.         /**
    121.          * 添加数据
    122.          *
    123.          * @param k
    124.          * @param v
    125.          * @return
    126.          */
    127.         public V put(K k, V v) {
    128.             //put时扩容
    129.             resize();
    130.             //key==null时
    131.             if (null == k) {
    132.                 return putForNullKey(k, v);
    133.             }
    134.             //计算k的hash
    135.             int hash = k.hashCode();
    136.             //计算k在数组中对应的下标
    137.             int index = getIndex(hash, capacity);
    138.             //获取对应下标上的Entry:若新增时 则为下个节点
    139.             MyEntry<K, V> nextEntry = table[index];
    140.             for (MyEntry<K, V> entry = table[index]; entry != null; entry = entry.getNext()) {
    141.                 //判断是否已经存在对应的key
    142.                 if (hash == entry.getHash() && (k == entry.getK() || k.equals(entry.getK()))) {
    143.                     V oldValue = entry.getV();
    144.                     entry.setV(v);
    145.                     return oldValue;
    146.                 }
    147.             }
    148.             size++;
    149.             //新增
    150.             table[index] = new MyEntry<>(k, v, nextEntry, hash);
    151.             //新增时返回Null
    152.             return null;
    153.         }
    154.         /**
    155.          * 存储key为null的值
    156.          *
    157.          * @param k
    158.          * @return
    159.          */
    160.         private V putForNullKey(K k, V v) {
    161.             MyEntry<K, V> entry = table[0];
    162.             //判断是否已经存在key为null的键值对，如果存在则替换
    163.             while (null != entry) {
    164.                 if (null == entry.getHash() && null == entry.getK()) {
    165.                     V oldValue = entry.getV();
    166.                     entry.setV(v);
    167.                     entry.setNext(entry);
    168.                     return oldValue;
    169.                 }
    170.                 entry = entry.getNext();
    171.             }
    172.             //新增
    173.             size++;
    174.             table[0] = new MyEntry<>(k, v, entry, null);
    175.             return null;
    176.         }
    177.         /**
    178.          * 计算k在数组中对应的下标
    179.          *
    180.          * @param hash     hash值
    181.          * @param capacity table容量
    182.          * @return
    183.          */
    184.         private int getIndex(int hash, int capacity) {
    185.             //table的容量
    186.             int index = hash % capacity;
    187.             return index >= 0 ? index : -index;
    188.         }
    189.         /**
    190.          * 扩容
    191.          */
    192.         private void resize() {
    193.             //已是最大扩容，不再扩容
    194.             if (capacity >= MAXIMUM_CAPACITY) {
    195.                 //将阈值设置为Inter的最大容量
    196.                 threshold = Integer.MAX_VALUE;
    197.                 return;
    198.             }
    199.             //未达到最大阈值 无需扩容
    200.             if (size < threshold) {
    201.                 return;
    202.             }
    203.             int newCapacity = capacity * 2;
    204.             if (newCapacity >= MAXIMUM_CAPACITY) {
    205.                 newCapacity = MAXIMUM_CAPACITY;
    206.             }
    207.             //扩容次数
    208.             resizeIndex++;
    209.             //重新计算扩容阈值
    210.             threshold = tableSizeFor(newCapacity, loadFactor);
    211.             //新容量
    212.             capacity = newCapacity;
    213.             MyEntry<K, V>[] oldEntry = table;
    214.             //创建新数组
    215.             MyEntry<K, V>[] newEntry = new MyEntry[newCapacity];
    216.             //将旧数组的值转移到新数组
    217.             transition(oldEntry, newEntry);
    218.             //重新定义table
    219.             table = newEntry;
    220.         }
    221.         /**
    222.          * 转移数组上的数据
    223.          *
    224.          * @param oldEntries
    225.          * @param newEntries
    226.          */
    227.         private void transition(MyEntry<K, V>[] oldEntries, MyEntry<K, V>[] newEntries) {
    228.             for (int i = 0; i < oldEntries.length; i++) {
    229.                 MyEntry<K, V> entry = oldEntries[i];
    230.                 while (null != entry) {
    231.                     MyEntry<K, V> next = entry.getNext();
    232.                     //扩容之后重新计算在数组中的下标
    233.                     int index = getIndex(entry.getK().hashCode(), capacity);
    234.                     //将元素放在数组上：
    235.                     //采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
    236.                     // 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
    237.                     entry.setNext(newEntries[index]);
    238.                     //赋值到新数组
    239.                     newEntries[index] = entry;
    240.                     entry = next;
    241.                 }
    242.             }
    243.         }
    244.         /**
    245.          * 计算扩容阈值
    246.          */
    247.         private int tableSizeFor(int initialCapacity, float loadFactor) {
    248.             BigDecimal init = new BigDecimal(initialCapacity);
    249.             BigDecimal bigLoad = new BigDecimal(loadFactor);
    250.             BigDecimal multiply = init.multiply(bigLoad);
    251.             return multiply.intValue();
    252.         }
    253.     }
    1. * entry组成了链表
    2.         public final class MyEntry<K, V> {
    3.         private K k;
    4.         private V v;
    5.         private MyEntry<K, V> next;
    6.         private Integer hash;
    7.         public MyEntry(K k, V v, MyEntry<K, V> next, Integer hash) {
    8.             this.k = k;
    9.             this.v = v;
    10.             this.next = next;
    11.             this.hash = hash;
    12.         }
    13.         public MyEntry() {
    14.         }
    15.         public MyEntry(K k, V v) {
    16.             this.k = k;
    17.             this.v = v;
    18.         }
    19.         public MyEntry(K k, V v, MyEntry<K, V> next) {
    20.             this.k = k;
    21.             this.v = v;
    22.             this.next = next;
    23.         }
    24.         public Integer getHash() {
    25.             return hash;
    26.         }
    27.         public void setHash(Integer hash) {
    28.             this.hash = hash;
    29.         }
    30.         public K getK() {
    31.             return k;
    32.         }
    33.         public void setK(K k) {
    34.             this.k = k;
    35.         }
    36.         public V getV() {
    37.             return v;
    38.         }
    39.         public void setV(V v) {
    40.             this.v = v;
    41.         }
    42.         public MyEntry<K, V> getNext() {
    43.             return next;
    44.         }
    45.         public void setNext(MyEntry<K, V> next) {
    46.             this.next = next;
    47.         }
    48.     }
    1. * 最后测试一下：
    2.         @Test
    3.         public void demo() {
    4.             MyHashMap<String, String> map = new MyHashMap();
    5.             System.out.println("-------------------MyHashMap begin-------------------------");
    6.             Long t1 = System.currentTimeMillis();
    7.             for (int i = 0; i < 1000; i++) {
    8.                 map.put("key" + i, "value" + i);
    9.             }
    10.             for (int i = 0; i < 1000; i++) {
    11.                 String value = map.get("key" + i);
    12.                 System.out.println("key: " + "key" + i + "---" + "value: " + value);
    13.                 assert (value.equals("value" + i));
    14.             }
    15.             //null key
    16.             map.put(null, "value:key is null");
    17.             System.out.printf(map.get(null));
    18.             Long t2 = System.currentTimeMillis();
    19.             System.out.println("MyHashMap耗时：" + (t2 - t1));
    20.             System.out.println("-------------------MyHashMap end-------------------------");
    21.             Map<String, String> hashMap = new HashMap();
    22.             Long t3 = System.currentTimeMillis();
    23.             for (int i = 0; i < 1000; i++) {
    24.                 hashMap.put("key" + i, "value" + i);
    25.             }
    26.             for (int i = 0; i < 1000; i++) {
    27.                 System.out.println("key: " + "key" + i + "---" + "value: " + hashMap.get("key" + i));
    28.             }
    29.             Long t4 = System.currentTimeMillis();
    30.             System.out.println("JDK的HashMap耗时：" + (t4 - t3));
    31.         }

    **