作者:鱼仔
博客首页: https://codeease.top
公众号:Java鱼仔

（一）Map方法概述

首先先看一下官方对Map接口的解释，《Java Platform SE 8》:

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

Map是一个通过键值对保存的对象，一个map只能由一个key，但是一个key可以有多个value。

1.1 Map的几个常用方法

通过代码展示一下Map中常用的方法：

public class MapTest {
    public static void main(String[] args) {
        Map map=new HashMap();
        //添加 put(key,value)
        map.put("a1",1);
        map.put("a2",1);
        map.put(null,1);
        System.out.println(map);
        //删除 remove(key)
        map.remove("a2");
        System.out.println(map);
        //是否包含 key value
        //containsKey(key)  containsValue(value)
        System.out.println(map.containsKey("a1"));
        System.out.println(map.containsValue("1"));
        //获取数据 get(key)
        System.out.println(map.get("a1"));
        //获取大小 size()
        System.out.println(map.size());
        //是否为空 isEmpty()
        System.out.println(map.isEmpty());
        //获取所有的关系 entrySet()
        System.out.println(map.entrySet());
        //获取所有的key keySet()
        System.out.println(map.keySet());
        //获取所有的value values()
        System.out.println(map.values());
    }
}

（二）HashMap的特点

HashMap底层是一个哈希表，以数组加链表的形式存储值。HashMap具有以下特点：

1. HashMap允许key和value为空
2. HashMap是线程不安全的
3. HashMap的初始容量为16，负载因子大小为0.75
4. 在jdk7.0中，底层是数组加链表；在jdk8.0中，底层是数组加链表加红黑树（这一点在后面会重点讲一下）

（三）HashMap的源码分析

通过代码断点的方法逐个添加元素，单步观察代码执行步骤，首先进入HashMap的构造方法：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

该构造方法把负载因子设置为0.75，负载因子的意思是当存入的数据大于总容量的0.75倍时，就扩容。构造方法结束后进入put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put方法直接返回putVal()方法，putVal方法的第一个参数是根据key计算的一个哈希值，可以看一下这个hash方法：通过hash运算和异或操作得到hash值并返回

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

接下来就进入了比较重要的putVal方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //查看此时table的容量（即哈希表数组部分的长度），如果为空（第一次进入），则进入resize()方法
    //resize()是个初始化或扩容方法，初始化成16或扩容2倍
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据此时数组的长度n和计算的hash值算出索引
    //计算出的索引一定在0~n-1之间
   //如果该索引位置没有元素，则直接将元素添加进入
   if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
   //如果该索引位置存在元素，执行以下代码块    
   else {
        Node<K,V> e; K k;
        //如果该元素和要保存的元素相同，则覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果不相同，并且是树状结构，则按树状结构的方式添加元素
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //如果是链状结构，则按照链表的方式添加元素
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判断容量是否超过临界值，如果超过了就2倍扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

源码分析：

HashMap中维护了Node类型的数组table，当HashMap创建对象时，设置负载因子为0.75，table还是null。

当第一次添加元素时，将table的容量设置为16，临界值设置为12

每次添加元素调用putVal方法：

1. 将key的hash值和table容量-1进行与运算，得到索引值
2. 判断该存放位置上是否有元素，如若没有元素则直接放上去；如果该索引位置已存在元素，则继续判断
3. 如果该位置的元素和添加元素相等，则直接覆盖，如果不相等，则继续判断是链表结构还是树状结构，按照相对应的方式添加。 如果添加的数量大于临界值，执行resize方法对容量双倍扩容。并打乱顺序重新排列。

（四）HashMap在JDK1.7和JDK1.8中的区别

前面一直提到树状结构和红黑树，这是HashMap在JDK1.7和JDK1.8之间最大的区别。数组+链表的结构下，如果一个索引后跟着的链表数量很多时，会很影响查找效率，因此在JDK1.8中，HashMap当满足某种条件（链表长度大于8，table容量大于64）时，会将链表转化为红黑树结构，提高效率。 截取一段源码：当链表长度大于等于（TREEIFY_THRESHOLD - 1）时，这个值是7，进入treeifyBin方法。链表长度大于等于7，再加上数组上的一个元素，一共是8个元素。

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

进入treeifyBin方法：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果进入treeifyBin但是table的容量小于64，则执行resize扩容并重新打乱
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //链表长度大于8，table容量大于64，转化成红黑树
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

如果进入treeifyBin但是table的容量小于64，则执行resize扩容并重新打乱。所以并非容量大于临界容量才会扩容。

第二个差异是插入元素时的变化，JDK1.7中是用头插法的方式插入元素，在JDK1.8中这个插入方式变成了尾插法。这个变化的原因是用头插法插入元素存在链表循环的风险。

JDK1.7和JDK1.8区别总结：

1. 初始化对象时，JDK1.7直接初始化对象容量为16，JDK1.8仅仅初始化负载因子为0.75
2. table类型：JDK1.7是Entry（映射key和value），JDK1.8是Node类型（为了红黑树）
3. 底层结构：JDK1.7数组+链表，JDK1.8数组+链表+红黑树（链表长度大于8，table容量大于64）

（五）HashMap和HashTable的对比

HashMap和HashTable的处境有点像Vector和ArrayList，HashTable现在很少使用，就用一个表格来总结它和HashMap的区别

	地层结构	版本	线程安全（同步）	允许null
HashMap	哈希表	1.2	不安全	允许键值为null
HashTable	哈希表	1.0	安全	不允许键值为null

（六）TreeMap的介

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

根据官方文档的介绍，TreeMap底层是一个红黑树，map是根据keys进行自然排序或者定制排序。

自然排序和定制排序的用法和TreeSet类似。

使用自然排序：需要在类中继承Comparable接口，并重写compareTo方法。

public class Book implements Comparable{
    private String name;
    private float price;
    public Book(String name, float price){
        this.name=name;
        this.price=price;
    }
    //.........
    @Override
    public int compareTo(Object o) {
        Book book= (Book) o;
        return Double.compare(book.price,this.price);
    }
}

使用定制排序：需要在创建TreeMap对象时传入一个Comparator接口，并实现里面的compare方法。

TreeMap map=new TreeMap(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        Book book1= (Book) o1;
        Book book2= (Book) o2;
        return Double.compare(book1.getPrice(),book2.getPrice());
    }
});

（七）总结

HashMap绝对是Map中的重点，也是据我所知面试中问到最多的集合知识。因此有条件的话打开源码自己单步调试一遍。HashTable、TreeMap就算没有看过代码但是也要了解各自的特点。