容器四（Map 接口）

HashMap 和 HashTable

Map 接口中的常用方法

HashMap 底层实现

Hashmap 基本结构

存储数据过程 put(key,value)

取数据过程 get(key)

扩容问题

JDK8 将链表在大于 8 情况下变为红黑二叉树

Map 就是用来存储“键(key)－值(value) 对”的。 Map 类中存储的“键值对”通过键来标识，所以“键对象”不能重复。

Map 接口的实现类有 HashMap、TreeMap、HashTable、Properties 等。

Map 接口中常用的方法
方法	说明
Object put(Object key, Object value)	存放键值对
Object get(Object key)	通过键对象查找得到值对象
Object remove(Object key)	删除键对象对应的键值对
boolean containsKey(Object key)	Map 容器中是否包含键对象对应的键值对
boolean containsValue(Object value)	Map 容器中是否包含值对象对应的键值对
int size()	包含键值对的数量
boolean isEmpty()	Map 是否为空
void putAll(Map t)	将 t 的所有键值对存放到本 map 对象
void clear()	清空本 map 对象所有键值对

HashMap 和 HashTable

HashMap 采用哈希算法实现，是 Map 接口最常用的实现类。由于底层采用了哈希表存储数据，我们要求键不能重复，如果发生重复，新的键值对会替换旧的键值对。 HashMap 在查找、删除、修改方面都有非常高的效率。

Map 接口中的常用方法

import java.util.HashMap;
import java.util.Map;

public class TestMap {
    public static void main(String[ ] args) {
        Map<Integer, String> m1 = new HashMap<Integer, String>();
        Map<Integer, String> m2 = new HashMap<Integer, String>();
        m1.put(1, "one");
        m1.put(2, "two");
        m1.put(3, "three");
        m2.put(1, "一");
        m2.put(2, "二");
        System.out.println(m1.size());
        System.out.println(m1.containsKey(1));
        System.out.println(m2.containsValue("two"));
        m1.put(3, "third"); //键重复了，则会替换旧的键值对
        Map<Integer, String> m3 = new HashMap<Integer, String>();
        m3.putAll(m1);
        m3.putAll(m2);
        System.out.println("m1:" + m1);
        System.out.println("m2:" + m2);
        System.out.println("m3:" + m3);
    }
}

HashTable 类和 HashMap 用法几乎一样，底层实现几乎一样，只不过 HashTable 的方法添加了 synchronized 关键字确保线程同步检查，效率较低。

HashMap 与 HashTable 的区别

HashMap: 线程不安全，效率高。允许 key 或 value 为 null。

HashTable: 线程安全，效率低。不允许 key 或 value 为 null。

HashMap 底层实现

HashMap 底层实现采用了哈希表，这是一种非常重要的数据结构。

数据结构中由数组和链表来实现对数据的存储，他们各有特点。

(1) 数组：占用空间连续。寻址容易，查询速度快。但是，增加和删除效率非常低。

(2) 链表：占用空间不连续。寻址困难，查询速度慢。但是，增加和删除效率非常高。

能结合数组和链表的优点（即查询快，增删效率也高），也就是“哈希表”。

哈希表的本质就是“数组+链表”。

Hashmap 基本结构

HashMap 源码，有如下两个核心内容：

其中的 Node[K, V ] table 就是 HashMap 的核心数组结构，我们也称之为“位桶数组”。

Node[K, V ] 源码为：

一个 Node 对象存储了：

key：键对象 value：值对象
next:下一个节点
hash: 键对象的 hash 值

显然每一个 Node 对象就是一个单向链表结构

画出 Node[ ]数组的结构（这也是 HashMap 的结构）：

存储数据过程 put(key,value)

HashMap 如何存储数据呢？其核心是如何产生 hash 值，该值用来对应数组的存储位置。

测试 hash 算法

public class TestMap {
    public static void main(String[ ] args) {
        int h = 25860399;
        int length = 16;//length为2的整数次幂,则h&(length-1)相当于对length取模
        myHash(h, length);
    }

    /**
     *
     * @param h 任意整数
     * @param length 长度必须为2的整数幂
     * @return
     */
    public static int myHash(int h,int length){
        System.out.println(h&(length-1));
        //length为2的整数幂情况下，和取余的值一样
        System.out.println(h%length);//取余数
        return h&(length-1);
    }
}

能发现直接取余(h%length)和位运算(h&(length-1))结果是一致的。事实上，为了获得更好的散列效果，JDK 对 hashcode 进行了两次散列处理（核心目标就是为了分布更散更均匀）

当添加一个元素（key-value）时，首先计算 key 的 hash 值，以此确定插入数组中的位置，但是可能存在同一 hash 值的元素已经被放在数组同一位置了，这时就添加到同一 hash 值的元素的后面，他们在数组的同一位置，就形成了链表，同一个链表上的 Hash 值是相同的，所以说数组存放的是链表。 JDK8 中，当链表长度大于 8 时，链表就转换为红黑树，这样又大大提高了查找的效率。