源码分析系列教程（11） - 手写Map框架（基于LinkedList）

代码已上传到GitHub，有兴趣的同学可以下载来看看：https://github.com/ylw-github/Java-CodeAnalysis-Demo

1.Map原理

HashMap的底层结构是由数组+链表构成的： 数组（紫色） ：hash数组（桶），数组元素是每个链表的头节点

链表（绿色） ：解决hash冲突，不同的key映射到了数组的同一索引处

1.1 put和get方法

put()方法大概过程如下：

1. 如果添加的key值为null，那么将该键值对添加到数组索引为0的链表中，不一定是链表的首节点。
2. 如果添加的key不为null，则根据key计算数组索引的位置： ----- 数组索引处存在链表，则遍历该链表，如果发现key已经存在，那么将新的value值替换旧的value值。 ----- 数组索引处不存在链表，将该key-value添加到此处，成为头节点。

get()方法的大概过程：

1. 如果key为null，那么在数组索引table[0]处的链表中遍历查找key为null的value 。
2. 如果key不为null，根据key找到数组索引位置处的链表，遍历查找key的value，找到返回value，若没找到则返回null。

1.2 扩容机制

先看一个例子，创建一个HashMap，初始容量默认为16，负载因子默认为0.75，那么什么时候它会扩容呢？

来看以下公式：

实际容量 = 初始容量 × 负载因子

计算可知，16×0.75=12，也就是当实际容量超过12时，这个HashMap就会扩容。

初始容量 ：当构造一个hashmap时，初始容量设为不小于指定容量的2的次方的一个数（new HashMap(5)， 指定容量为5，那么实际初始容量为8，2^3=8>5），且最大值不能超过2的30次方。

负载因子 ：负载因子是哈希数组在其容量自动增加之前可以达到多满的一种尺度。（时间与空间的折衷） 当哈希数组中的条目数超出了加载因子与初始容量的乘积时，则要对该哈希数组进行扩容操作（即resize）。

特点：

• 负载因子越小，容易扩容，浪费空间，但查找效率高
• 负载因子越大，不易扩容，对空间的利用更加充分，查找效率低（链表拉长） 扩容过程

HashMap在扩容时，新数组的容量将是原来的2倍，由于容量发生变化，原有的每个元素需要重新计算数组索引Index，再存放到新数组中去，这就是所谓的rehash。

1.3 eqauls方法和hashCode方法

1. 如果两个对象相同，那么它们的hashCode值一定要相同。也告诉我们重写equals方法，一定要重写hashCode方法，也就是说hashCode值要和类中的成员变量挂上钩，对象相同–>成员变量相同—->hashCode值一定相同。
2. 如果两个对象的hashCode相同，它们并不一定相同，这里的对象相同指的是用eqauls方法比较。

2.代码实现

package com.ylw.jdk.map;

import java.util.ArrayList;
import java.util.List;


public class ExtArrayListMap {

    List tables = new ArrayList();

    public void put(Key key, Value value) {
        // 判断key是否已经重复
        Entry existEntry = getEntry(key);
        if (existEntry != null) {
            existEntry.value = value;
            return;
        }
        Entry entry = new Entry(key, value);
        tables.add(entry);
    }

    public Value get(String key) {
        for (Entry entry : tables) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }

    public void remove(Key key) {
        Entry existEntry = getEntry(key);
        if (existEntry != null) {
            tables.remove(existEntry);
        }
    }

    public Entry getEntry(Key key) {
        for (Entry entry : tables) {
            if (entry.key.equals(key)) {
                return entry;
            }
        }
        return null;
    }
    
}

class Entry {

    public Entry(Key key, Value value) {
        this.key = key;
        this.value = value;
    }

    Key key;
    Value value;

}

总结