Java集合框架--Map

发表于 2022-08-01 更新于 2022-08-04 本文字数： 15k 阅读时长 ≈ 14 分钟

Java集合框架–Map集合

Map概述

Map用于保存具有映射关系的数据，因此Map集合里保存着两组值，一组用于保存Map里的key，另外一组用于保存Map里的value，key和value都可以是任何引用类型的数据。Map的key不允许重复，即同一个Map对象的任何两个key通过equals方法比较总是返回false。
key和value之间存在单向一对一的关系，即通过指定的key，总能找到唯一的、确定的value。从Map中取出数据时，只要给出指定的key，就可以取出对应的value.
Map的实现类有HashMap、Hashtable、Properties、SortedMap等等。

HashMap

HashMap常用API

方法	描述
put(K key,V value)	添加键值对
get(Object key)	根据键获取值
keySet()	获取keySet
entrySet()	获取entrySet
clear()	清空
containsKey(Object key)	判断是否存在key
remove(Object key)	根据key删除键值对
remover(Object key,Object value)	根据key和value删除键值对
size()	获取元素个数
isEmpty()	判断map是否为空

下面，通过示例学习HashMap的方法：

package cn.bytecollege;

import java.util.HashMap;

public class HashMapDemo {
    public static void main(String[] args){
        HashMap<Integer,String> map = new HashMap<Integer,String>();
        //添加键值对
        map.put(1,"妲己");
        map.put(2,"亚瑟");
        map.put(3,"虞姬");
        map.put(4,"韩信");
        map.put(5,"蔡文姬");
        //根据键获取值
        System.out.println(map.get(3));
        //获取keySet
        for (Integer i : map.keySet()){
            System.out.println("key: " + i + " value: " + map.get(i));
        }
        //获取entrySet
        System.out.println(map.entrySet());
        //获取元素个数
        System.out.println(map.size());
        //判断是否存在key
        System.out.println(map.containsKey(5));
        //判断是否存在value
        System.out.println(map.containsValue("程咬金"));
        //判断map是否为空
        System.out.println(map.isEmpty());
        //根据key删除键值对
        map.remove(2);
        //根据key和value删除键值对
        map.remove(4,"韩信");
        System.out.println(map);
        //清空map
        map.clear();
        System.out.println(map);
    }
}

HashMap存放元素流程

HashMap元素存放是一个相对是复杂的过程，整个过程涉及到的有哈希表扩容，红黑树和链表的相互转换等过程，在本小节从源码查看整个过程。
在学习HashMap存放元素之前需要对HashMap中的几个关键成员变量进行了解。

//HashMap默认容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;;
//链表转换为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树转换为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//链表转换为红黑树时Hash表的容量阈值
static final int MIN_TREEIFY_CAPACITY = 64;
//保存HashMap的Hash表
transient Node<K,V>[] table;
//HashMap中元素个数
transient int size;

HashMap添加元素会调用put(K key,V value)方法，从源码可以看出在put()方法内部调用了putVal()方法。

public V put(K key, V value) {
    //调用putVal方法
    return putVal(hash(key), key, value, false, true);
}

继续查看putVal()方法，这个方法即HashMap存放元素的核心流程。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断哈希表是否为空
    if ((tab = table) == null || (n = tab.length) == 0)
        //扩容
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//判断tab[i]是否有元素
        //如果没有元素则直接存放
        tab[i] = newNode(hash, key, value, null);
    else {
         Node<K,V> e; K k;
         //判断和已有节点的key是否相等
         if (p.hash == hash &&
                 ((k = p.key) == key || (key != null && key.equals(k))))
             //如果key相等则替换
             e = p;
         //如果key不相等，判断哈希表已有的节点是不是红黑树
         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);
                     //如果链表长度大于等于7，则进制红黑树转换相关工作
                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                         treeifyBin(tab, hash);
                         break;
                     }
                 	 //如果key相等则在链表中替换
                     if (e.hash == hash &&
                         ((k = e.key) == key || (key != null && key.equals(k))))
                         break;
                     
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
    	//如果元素个数大于临界值则扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

在这个方法内整个过程可以描述如下：

判断底层hash表是否为空，如果为空则先扩容
如果不为空，根据存放元素的key计算在hash表中的位置
判断在计算出位置处是否有元素，如果没有元素则直接放入hash表，并直接跳转到第9步
如果计算出位置有元素判断key是否相等，如果相等则直接赋值
如果计算出位置有元素并且判断key不相等，判断此处的节点是否是红黑树，如果是红黑树则以树的方式插入
如果计算处位置有元素并且判断key不相等，并且此处节点不是红黑树，那么这个节点处的数据结构一定是链表，则遍历链表准备插入。
遍历链表如果新增元素和链表中元素key相等则替换，如果新增元素和链表中已有元素key都不相等，则在已有元素末尾链表插入。
如果链表长度大于8，判断hash表容量是否大于64，如果大于64则转换成红黑树，并以红黑树的方式插入元素。
添加元素后判断元素个数是否大于扩容阈值，如果大于则扩容。

这9步完整的描述了HashMap添加元素的流程，描述如图：

HashMap扩容流程

在上一小节中我们了解了HashMap添加元素的详细流程，在HashMap添加元素的过程中涉及到一个很重要的操作，那就是扩容。因为如果在HashMap内添加元素，当HashMap内部数组无法装载更多元素时，就需要扩大数组长度，以便放入更多元素，由于Java中数组是无法自动扩容的，这就需要创建一个新的数组替代已有的数组，在本小节内将详细了解HashMap的扩容机制。

final Node<K,V>[] resize() {
    //获取原有hash表
    Node<K,V>[] oldTab = table;
    //获取原容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //获取原阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果原容量大于0
    if (oldCap > 0) {
        //如果原容量已经大于最大容量则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果原容量的2倍小于最大容量，并且原容量小于默认容量10，就将扩容阈值修改为原阈值的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
        }
    //如果当前hash表没有数据，则使用初始化的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //如果是第一次添加元素则使用默认容量16，扩容阈值为16*0.75=12
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //创建新的hash表
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //遍历hash表开始扩容
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果原数据不为空，则将原数据复制到新数组
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果链表只有一个节点，则直接复制
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //如果元数据是红黑树
                else if (e instanceof TreeNode)
                    //进行红黑树相关操作
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //链表复制操作
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

纵观整个代码HashMap扩容时会存在以下几种情况：

调用无参构造器时，实例化的HashMap底层数组是null，当第一次调用put()方法时进行扩容，初始容量为16。
调用有参构造指定了容量和负载因子时，会根据指定的正整数找到不小于指定容量的2的次幂，将这个数赋值给扩容阈值（threshold），当第一次put()方法时，会将阈值赋值给容量，并计算新的阈值=容量x负载因子。
如果不是第一次扩容，则容量变为原容量的2倍，阈值也变为原来的2倍。

Java 7 和Java 8中HashMap的区别
Java8中对HashMap进行了相关的调整，主要体现在以下几个方面：

Java7中HashMap数据结构采用了数组+链表，而Java8中采用了数组+链表+红黑树，当链表长度大于8并且容量大于64时，会将链表转换成红黑树（注意，如果此时如果链表长度已经是8，但是数组长度并没有到64时会先进行扩容）。当红黑树节点个数小于等于6时会退化成链表。
Java7中链表使用的是头插法，但是使用头插法在多线程环境下有概率出现环形链表死循环的问题，在Java8中链表采用了尾插法以及使用了红黑树，避免了出现链表死循环的问题。

HashMap的遍历方式

HashMap的遍历在开发中属于必备技能，HashMap的遍历方式有很多种，但是总的来说只有三种：

获取keySet()后遍历keySet()获取到key然后通过key获取value
获取entrySet()后遍历entrySet()，相比于第一种写法稍显复杂，但是能更好的体现Map中的数据结构
使用Lambda表达式遍历，相比前两种是最简洁的方式，但是代码可读性略差在HashMap的遍历中，应该综合考虑性能、效率等因素做出合适的选择。下面通过实例学习HashMap的遍历。

package cn.bytecollege

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * 本例将演示HashMap遍历的方法
 * @author MR.W
 *
 */
public class ForeachHashMap {
	public static void main(String[] args) {
		Map<String,String> map = new HashMap<>();
		
		map.put("张三", "计算机科学与技术");
		map.put("李四", "软件工程");
		map.put("王五", "网络工程");
		
		//第一种：获取keySet()并遍历
		Set<String> set = map.keySet();
		//获取迭代器
		Iterator<String> it = set.iterator();
		while(it.hasNext()) {
			String key = it.next();
			String value = map.get(key);
			System.out.println(key+"==================="+value);
		}
		for (; it.hasNext();) {
			String key = it.next();
			String value = map.get(key);
			System.out.println(key+"==================="+value);
		}
		for (String key : set) {
			String value = map.get(key);
			System.out.println(key+"==================="+value);
		}
		//第二种：获取Entry
		Set<Map.Entry<String, String>> entrySet = map.entrySet();
		//使用迭代器
		Iterator<Map.Entry<String, String>> entryIt = entrySet.iterator();
		
		while (entryIt.hasNext()) {
			Map.Entry<String, String> entry = entryIt.next();
			String key = entry.getKey();
			String value = entry.getValue();
			System.out.println(key+"==================="+value);
		}
		
		for (; entryIt.hasNext();) {
			Map.Entry<String, String> entry = entryIt.next();
			String key = entry.getKey();
			String value = entry.getValue();
			System.out.println(key+"==================="+value);
		}
		
		for (Entry<String, String> entry : entrySet) {
			String key = entry.getKey();
			String value = entry.getValue();
			System.out.println(key+"==================="+value);
		}
		//第三种：Lambda表达式
		map.forEach((key,value)->System.out.println(key+"==================="+value));
	}
}

运行结果如下图所示：

HashMap和Hashtable

HashMap 和 Hashtable 都是 Map 接口的典型实现类，它们之间的关系完全类似于 ArrayList 和 Vector的关系∶ Hashtable 是一个古老的 Map 实现类，它从 JDK 1.0起就已经出现了，当它出现时，Java还没有提供Map 接口，所以它包含了两个烦琐的方法，即 elements() 类似于 Map接口定义的 values()方法）和 keys() 类似于 Map 接口定义的 keySet()方法。
除此之外，Hashtable 和 HashMap 存在三点典型区别。

Hashtable 是一个线程安全的 Map接口实现，但 HashMap 是线程不安全的实现，所以 HashMap 比 Hashtable 的性能高一点;但如果有多个线程访问同一个 Map 对象时，使用 Hashtable 实现类会更好。
Hashtable 不允许使用 null 作为 key 和 value，如果试图把 null 值放进 Hashtable 中，将会引发 NullPointerException 异常; 但 HashMap 可以使用 null 作为 key 或 value。
HashMap数组初始长度为16，扩容后长度是原长度的2倍，Hashtable初始长度为11，扩容后的长度是原长度的2n+1

LinkedHashMap

HashMap也有一个LinkedHashMap子类;LinkedHashMap 也使用双向链表来维护 key-value 对的次序（其实只需要考虑 key 的次序），该链表负责维护 Map 的迭代顺序，迭代顺序与 key-value 对的插入顺序保持一致。 
LinkedHashMap 可以避免对 HashMap、Hashtable 里的 key-value 对进行排序（只要插入 key-value对时保持顺序即可），同时又可避免使用 TreeMap 所增加的成本（TreeMap的内容将会在下一小节学习）。 LinkedHashMap 需要维护元素的插入顺序，因此性能略低于 HashMap 的性能;但因为它以链表来维护内部顺序，所以在迭代访问 Map 里的全部元素时将有较好的性能，下面通过示例学习LinkedHashMap。

package cn.bytecollege;

import java.util.LinkedHashMap;
import java.util.Set;
/**
 * 本例将演示LinkedHashMap
 * @author MR.W
 */
public class LinkedHashMapDemo {
	public static void main(String[] args) {
		
		LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
		map.put("语文", 90);
		map.put("数学", 100);
		map.put("英文", 82);
		
		Set<String> set = map.keySet();
		for (String key : set) {
			System.out.println(key+"================"+map.get(key));
		}
	}
}

使用Properties读写文件

Properties 类是 Hashtable 类的子类，该对象在处理属性文件时特别方便（Windows 操作平台上的 ini 文件就是一种属性文件）。Properties 类可以把 Map 对象和属性文件关联起来，从而可以把Map 对象中的 key-value 对写入属性文件中，也可以把属性文件中的”属性名=属性值”加载到 Map 对象中。由于属性文件里的属性名、属性值只能是字符串类型，所以 Properties 里的 key、 value 都是字符串类型。该类提供了如下三个方法来修改 Properties 里的 key、value 值。

String getProperty(String key)∶获取 Properties 中指定属性名对应的属性值，类似于 Map 的 get（Object key）方法。
String getProperty(String key，String defaultValue)∶该方法与前一个方法基本相似。该方法多一个功能，如果 Properties 中不存在指定的 key 时，则该方法指定默认值。
Object setProperty(String key， String value)∶设置属性值，类似于Hashtable 的 put() 方法。除此之外，它还提供了两个读写属性文件的方法。
void load(InputStream inStream)∶ 从属性文件（以输入流表示）中加载 key-value 对，把加载到的 key-value 对追加到 Properties 里（Properties 是 Hashtable 的子类，它不保证 key-value 对之间的次序）。
void store(OutputStream out， String comments)∶将 Properties 中的 key-value 对输出到指定的属性 文件（以输出流表示）中。 上面两个方法中使用了InputStream 类和 OutputStream 类，它们是 Java IO 体系中的两个基类，关于流的内容在后续章节讲解。下面通过示例先演示基本用法。

package cn.bytecollege;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Properties;

/**
 * 本例将演示Properties类
 * @author MR.W
 *
 */
public class PropertiesDemo {
	public static void main(String[] args) throws FileNotFoundException, IOException {
		//--------------------读取数据--------------------------//
		Properties properties = new Properties();
		properties.load(new FileInputStream(new File("data.properties")));
		
		String username = properties.getProperty("username");
		String password = properties.getProperty("password");
		
		System.out.println(username);
		System.out.println(password);
		//--------------------写数据--------------------------//
		Properties properties2 = new Properties();
		properties2.setProperty("token", "123431");
		properties2.store(new FileOutputStream(new File("data.properties")), "token");
		
	}
}

上面的示例分别演示了Properties读写配置文件，在JDBC中将会使用配置文件配置数据库连接信息。

SortedMap和TreeMap

Map 接口也派生出一个 SortedMap 子接口，SortedMap 接口也有一个 TreeMap 实现类。 TreeMap 就是一个红黑树数据结构，每个 key-value 对即作为红黑树的一个节点。TreeMap 存储 key-value 对（节点）时，需要根据 key 对节点进行排序。TreeMap 可以保证所有的 key-value 对处于有序状态。TreeMap 也有两种排序方式。

自然排序∶TreeMap的所有key 必须实现 Comparable 接口，而且所有的 key 应该是同一个类的 对象，否则将会抛出 ClassCastException 异常。
定制排序∶ 创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对 TreeMap 中的所有key进行排序。采用定制排序时不要求 Map 的 key 实现 Comparable 接口。 类似于 TreeSet 中判断两个元素相等的标准，TreeMap 中判断两个 key 相等的标准是∶ 两个 key 通过 compareTo()方法返回 0，TreeMap 即认为这两个 key 是相等的。

如果使用自定义类作为 TreeMap 的 key，且想让 TreeMap 良好地工作，则重写该类的 equals()方法和 compareTo（方法时应保持一致的返回结果∶ 两个 key 通过 equals()方法比较返回 true 时，它们通过 compareTo()方法比较应该返回 0。如果 equals()方法与 compareTo()方法的返回结果不一致， TreeMap与 Map 接口的规则就会冲突。
TreeMap 中也提供了一系列根据 key 顺序访问 key-value 对的方法。

Map.Entry firstEntry()∶ 返回该 Map 中最小 key 所对应的 key-value 对，如果该Map为空，则返回 null。
Object firstKey()∶返回该 Map 中的最小 key值，如果该 Map为空，则返回 null。
Map.Entry lastEntry()∶ 返回该 Map 中最大 key 所对应的 key-value 对，如果该 Map为空或不存 在这样的 key-value 对，则都返回 null。
Object lastKey()∶ 返回该 Map 中的最大 key 值，如果该 Map 为空或不存在这样的 key，则都返回nulI。
Map.Entry higherEntry(Object key)∶ 返回该 Map 中位于key 后一位的 key-value 对（即大于指定 key 的最小 key 所对应的 key-value 对）。如果该 Map 为空，则返回 null。
Object higherKey(Object key)∶返回该 Map 中位于key 后一位的 key 值（即大于指定 key 的最小 key 值）。如果该 Map 为空或不存在这样的 key-value 对，则都返回 null。
Map.Entry lowerEntry(Object key)∶ 返回该 Map 中位于key 前一位的 key-value 对（即小于指定 key 的最大 key 所对应的 key-value 对）。如果该 Map 为空或不存在这样的 key-value 对，则都返回 null。
Object lowerKey(Object key)∶返回该Map 中位于key前一位的 key 值（即小于指定 key 的最大 key 值）。如果该 Map 为空或不存在这样的 key，则都返回 null。

package cn.bytecollege;

import java.util.TreeMap;

public class MapDemo {
    public static void main(String[] args) {
        TreeMap<Integer,String> map = new TreeMap<Integer,String>();
        map.put(1,"刘能");
        map.put(2,"谢广坤");
        map.put(3,"赵四");
        map.put(4,"王大拿");
        map.put(5,"宋晓峰");
        //返回该 Map 中最小 key 所对应的 key-value 对，如果该Map为空，则返回 null。
        System.out.println(map.firstEntry());
        //返回该 Map 中的最小 key值，如果该 Map为空，则返回 null。> Map.Entry lastEntry（）∶ 返回该 Map 中最大 key 所对应的 key-value 对，如果该 Map为空或不存在这样的 key-value 对，则都返回 null。
        System.out.println(map.firstKey());
        //返回该 Map 中的最大 key 值，如果该 Map 为空或不存在这样的 key，则都返回nulI。
        System.out.println(map.lastKey());
        //返回该 Map 中位于key 后一位的 key 值（即大于指定 key 的最小key 值）。如果该 Map 为空或不存在这样的 key-value 对，则都返回 nul 。
        System.out.println(map.higherKey(3));
        //返回该 Map 中位于key 后一位的 key-value 对（即大于指定key 的最小 key 所对应的 key-value 对）。如果该 Map 为空，则返回 null。
        System.out.println(map.higherEntry(3));
        //返回该Map 中位于key前一位的 key 值（即小于指定 key 的最大key 值）。如果该 Map 为空或不存在这样的 key，则都返回 null。
        System.out.println(map.lowerKey(2));
        //返回该 Map 中位于key 前一位的 key-value 对（即小于指定key 的最大 key 所对应的 key-value 对）。如果该 Map 为空或不存在这样的 key-value 对，则都返回 null。
        System.out.println(map.lowerEntry(2));
    }
}

各Map性能分析

对于 Map 的常用实现类而言，虽然 HashMap 和 Hashtable 的实现机制几乎一样，但由于Hashtable是一个古老的、线程安全的集合，因此 HashMap 通常比 Hashtable 要快。
 TreeMap 通常比 HashMap、Hashtable 要慢（尤其在插入、删除 key-value 对时更慢），因为 TreeMap底层采用红黑树来管理 key-value 对（红黑树的每个节点就是一个 key-value 对）。 使用 TreeMap 有一个好处∶ TreeMap 中的 key-value 对总是处于有序状态，无须专门进行排序操作。当 TreeMap 被填充之后，就可以调用 keySet() ，取得由key 组成的 Set，然后使用 toArray()方法生成 key的数组，接下来使用 Arrays 的 binarySearch() 方法在已排序的数组中快速地查询对象。
 对于一般的应用场景，程序应该多考虑使用 HashMap，因为 HashMap 正是为快速查询设计的（HashMap 底层其实也是采用数组来存储 key-value 对）。但如果程序需要一个总是排好序的 Map 时，则可以考虑使用TreeMap。 LinkedHashMap 比 HashMap 慢一点，因为它需要维护链表来保持 Map中 key-value 时的添加顺序。