1 Map集合类型

1.1 Map

• 特点：存储的键值对映射关系，根据key可以找到value
• Map中所有的Key集合可以看做Set集合，无序、唯一
• Map中所有Value的集合无序、不唯一
• Set集合的底层就是Map，所以Set和Map的类型一致，也有HashMap、LinkedHashMap、TreeMap三种

1.2 HashMap

• 采用Hashtable哈希表存储结构
• 优点：添加速度快 查询速度快 删除速度快
• 缺点：key无序

1.3 LinkedHashMap

• 采用哈希表存储结构，同时使用链表维护次序
• key有序（添加顺序）

1.4 TreeMap

• 采用二叉树（红黑树）的存储结构
• 优点：key有序 查询速度比List快
• 缺点：查询速度没有HashMap快

2 Map接口方法摘要

3 HashMap源码分析

• JDK1.7及其之前，HashMap底层是一个table数组+链表实现的哈希表存储结构
• 在JDK1.8中有一些变化，当链表的存储数据个数大于等于8的时候，不再采用链表存储，而采用红黑树存储结构。这么做主要是查询的时间复杂度上，链表为O(n)，而红黑树一直是O(logn)。如果冲突多，并且超过8，采用红黑树来提高效率
  

• 链表的每个节点就是一个Entry，其中包括：键key、值value、键的哈希码hash、执行下一个节点的引用next四部分

static class Entry<K, V> implements Map.Entry<K, V> {
     final K key; //key
     V value;//value
     Entry<K, V> next; //指向下一个节点的指针
     int hash;//哈希码
}

3.1 HashMap基本属性

//JDK1.7
public class HashMap<K, V> implements Map<K, V> {
    //哈希表主数组的默认长度
    static final int DEFAULT_INITIAL_CAPACITY = 16; 
    //默认的装填因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f; 
    //主数组的引用
    transient Entry<K, V>[] table; 
    int threshold;//界限值  阈值 主数组长度×装填因子
    final float loadFactor;//装填因子
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(int initialCapacity, float loadFactor) {
        this.loadFactor = loadFactor;//0.75
        threshold = (int) Math.min(capacity * loadFactor, 
                 MAXIMUM_CAPACITY + 1);//16*0.75=12
        table = new Entry[capacity];
      ....
    }
 }

3.2 HashMap的put方法

调用put方法添加键值对。哈希表主要通过三个步骤添加数据：

1. 第一步计算哈希码，注意计算哈希码时不仅调用了key的hashCode()，还进行了更复杂处理，目的是尽量保证不同的key尽量得到不同的哈希码
2. 第二步根据哈希码计算存储位置，这里使用了位运算提高效率。同时也要求主数组长度必须是2的幂
3. 第三步添加Entry
   正常情况：添加到链表的第一个位置，而不是链表末尾
   发现了相同的key已经存在的情况：就使用新的value替代旧的value，并且返回旧的value

public class HashMap {
    public V put(K key, V value) {
       //如果key是null，特殊处理
        if (key == null) return putForNullKey(value);
        //1.计算key的哈希码hash 
        int hash = hash(key);
        //2.将哈希码代入函数，计算出存储位置  y= x%16；
        int i = indexFor(hash, table.length);
        //如果已经存在链表，判断是否存在该key，需要用到equals()
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如找到了,使用新value覆盖旧的value，返回旧value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                V oldValue = e.value;// the United States
                e.value = value;//America
                e.recordAccess(this);
                return oldValue;
            }
        }
        //添加一个结点
        addEntry(hash, key, value, i);
        return null;
    }
    final int hash(Object k) {
        int h = 0;
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    static int indexFor(int h, int length) {
    //作用就相当于y = x%16,采用了位运算，效率更高
        return h & (length-1);
    }
}

3.3 HashMap的get方法

其实是根据key找Entry，再从Entry中获取value即可

public V get(Object key) {
    //根据key找到Entry（Entry中有key和value）
    Entry<K,V> entry = getEntry(key);
    //如果entry== null,返回null，否则返回value
    return null == entry ? null : entry.getValue();
}

3.4 HashMap的扩容

void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果达到了门槛值，就扩容，容量为原来容量的2位 16---32
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    //添加节点
    createEntry(hash, key, value, bucketIndex);
}

4 TreeMap源码分析

TreeMap每个节点的结构

static final class Entry<K,V> implements Map.Entry<K,V> {
   K key;
   V value;
   Entry<K,V> left;
   Entry<K,V> right;
   Entry<K,V> parent;
   boolean color = BLACK;
}

4.1 TreeMap基本属性

public class TreeMap<K, V> implements NavigableMap<K, V> {
    private final Comparator<? super K> comparator;//外部比较器
    private transient Entry<K, V> root = null; //红黑树根节点的引用
    private transient int size = 0;//红黑树中节点的个数
    public TreeMap() {
        comparator = null;//没有指定外部比较器
    }
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;//指定外部比较器
    }
}

4.2 TreeMap的put和get方法

添加原理

• 从根节点开始比较
• 添加过程就是构造二叉平衡树的过程，会自动平衡
• 平衡离不开比较：外部比较器优先，然后是内部比较器。如果两个比较器都没有，就抛出异常
• 查找方法与添加方法的原理基本相同

public V put(K key, V value) {
    Entry<K,V> t = root;
    //如果是添加第一个节点，就这么处理
    if (t == null) {
        //即使是添加第一个节点，也要使用比较器
        compare(key, key); // type (and possibly null) check
        //创建根节点
        root = new Entry<>(key, value, null);
        //此时只有一个节点
        size = 1;
        return null;
    }
    //如果是添加非第一个节点，就这么处理
    int cmp;
    Entry<K,V> parent; 
    Comparator<? super K> cpr = comparator;
    //如果外部比较器存在，就使用外部比较器
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;//在左子树中查找
           else if (cmp > 0)                
                t = t.right; //在右子树查找
            else
               //找到了对应的key，使用新的value覆盖旧的value                 
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //如果外部比较器没有，就使用内部比较器
       ....
    }
    //找到了要添加的位置，创建一个新的节点，加入到树中
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)  
        parent.left = e;
    else
        parent.right = e;       
    size++;
    return null;
}

public V get(Object key) {
    //根据key（cn）找Entry（cn--China）
    Entry<K,V> p = getEntry(key);
    //如果Entry存在，返回value：China
    return (p==null ? null : p.value);
}

final Entry<K, V> getEntry(Object key) {
    //如果外部比较器存在，就使用外部比较器
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    //如果外部比较器不存在，就使用内部比较器
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K, V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            //如果找到了，就返回Entry
            return p;
    }
    //如果没有找到，就返回null
    return null;
}