1. MAP接口概述

1.1 MAP体系结构

  • Map：双列数据，存储key-value数据

    • HashMap：作为Map的主要实现类，线程不安全，效率高，可以存储null的键值对

      • LinkedhashMap：可以保证遍历map元素时按照添加时的顺序进行，原因是在原有HashMap结构的基础上添加了一对指针，分别指向前一个和后一个元素，对于频繁遍历操作，此类执行效率要高于HashMap
    • TreeMap：可以保证添加的key-value有序，根据key值进行排序，实现排序遍历。底层使用红黑树实现

    • HashTable：作为古老的实现类，线程安全，效率低，不可以存储null值

      • Properties：常用来处理配置文件，key和value都是String类型
  • HashMap底层在JDK1.7之前使用数组和链表实现，在JDK8之后使用数组、链表和红黑树实现。

典型面试题：

  1. HashMap的底层实现原理
  2. HashMap和HashTable的异同
  3. CurrentHashMap与HashTable的区别

1.2 对MAP结构的理解

  • Map与Collection并列存在。用于保存具有映射关系的数据
  • Map中的key和value都可以是任何引用类型的数据
  • Map中的key用Set存放，不允许重复，即同一个Map对象所对应的类，须重写hashCode()和equals()方法
  • 常用String类作为Map的“键”
  • key和value之间存在一对一关系，即通过指定的key总能找到唯一、确定的value
  • Map接口常用实现类：hashMap、TreeMap、LinkedHashMap和Properties。其中，HashMap是Map接口中使用频率最高的实现类

Map存储示意图

1.3 常用方法

  • Object put(Object key, Object value)：将指定键值对添加（或修改）当前map对象中
  • void putAll(Map m)：将m中所有的key-value值存放到当前Map中
  • Object remove(Object key)：移除指定key的key-value对，并返回value
  • void clear()：清空当前Map中的所有数据
@Test
public void test1() {
    Map map = new HashMap<>();
    map.put("AA", 123);
    map.put("BB", 456);
    map.put("CC", 123);
    map.put("AA", 789);// 修改操作
    System.out.println("添加：" + map);

    Map map1 = new HashMap();
    map1.put("AA", 111);
    map1.put("DD", 222);

    map.putAll(map1);
    System.out.println("添加集合：" + map);

    Object cc = map.remove("CC");
    System.out.println("移除：" + map);

    map.clear();// 清空集合，不等于把集合赋值为null
    System.out.println("清空：" + map);
}

运行结果：

添加：{AA=789, BB=456, CC=123}
添加集合：{AA=111, BB=456, CC=123, DD=222}
移除：{AA=111, BB=456, DD=222}
清空：{}
  • Object get(Object key)：获取指定key对应的value
  • boolean containsKey(Object key)：是否包含指定的key
  • boolean containsValue(Object value)：是否包含指定的value
  • int size()：返回Map中key-value对的个数
  • boolean isEmpty()：判断当前集合是否为空
  • boolean equals(Object obj)：判断当前Map和参数对象obj是否相等
@Test
public void test3() {
    Map map = new HashMap<>();
    map.put("AA", 123);
    map.put("BB", 456);
    map.put("CC", 123);
    System.out.println("map.get(\"AA\")：" + map.get("AA"));
    System.out.println("map.containsKey(\"AA\")：" + map.containsKey("AA"));
    System.out.println("map.containsValue(123)：" + map.containsValue(123));
    System.out.println("map.size()：" + map.size());
    System.out.println("map.isEmpty()：" + map.isEmpty());
}

运行结果：

map.get("AA")：123
map.containsKey("AA")：true
map.containsValue(123)：true
map.size()：3
map.isEmpty()：false
  • Set keySet()：返回所有key构成的Set集合
  • Collection values()：返回所有value构成的Collection集合
  • Set entrySet()：返回所有key-value对构成的Set集合
@Test
public void test4() {
    Map map = new HashMap<>();
    map.put("AA", 123);
    map.put("BB", 456);
    map.put("CC", 123);

    Set keySet = map.keySet();
    Collection values = map.values();
    Set entrySet = map.entrySet();

    Iterator iterator = keySet.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    for (Object value : values) {
        System.out.println(value);
    }

    for (Object o : entrySet) {
        System.out.println(o);
    }

}

运行结果：

AA
BB
CC
123
456
123
AA=123
BB=456
CC=123

2. HashMap

1.1 概述

  • HashMap是Map接口使用频率最高的类
  • 所有的key构成的集合时Set，是无序的、不可重复的。所以key所在的类要重写：equals()和hashCode()
  • 所有的value构成的集合时Collection，是无序的、可以重复的。所以，value所在的类要重写：equals()
  • 一个key-value构成一个entry
  • 所有的entry构成的集合是Set，是无序不可重复的
  • HashMap判断两个key是否相等的标准是：两个key通过equals()方法返回true，hashCode也相等
  • HashMap判断两个value相等的标准是：两个value通过equals()方法返回true

1.2 HashMap存储结构

1.2.1 JDK7及以前版本使用链地址法实现：

请输入图片描述

  • HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时， 系统会创建一个长度为Capacity的Entry数组，这个长度在哈希表中被称为容量 (Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个 bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。
  • 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引 用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。 而且新添加的元素作为链表的head。
  • 添加元素的过程：向HashMap中添加entry1(key, value)，需要首先计算entry1中key的哈希值（根据key所在类的hashCode()计算得到），此时哈希值经过处理以后，得到在底层Entry[]数组中要存储的位置。如果位置i上没有元素，则entry1直接添加成功。如果位置i上已经存在entry2（或还有链表存在的entry3，entry4），则需要通过循环的方法，依次比较entry1中key和其它的entry。如果彼此hash值相同，则直接添加成功。如果hash值不同，继续比较二者是否equals。如果返回值为true，则使用entry1的value去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals()返回值都为false，则entry1仍可添加成功。entry1指向原有的entry元素。
  • 扩容机制：当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。当HashMap中的元素个数超过length * loadFactor时，就会进行数组扩容，loadFactor（DEFAULT_LOAD_FACTOR）的默认值是0.75。也就是说，当数组中的元素个数超过16 * 0.75 = 12时，就把数组的大小扩展为原来的二倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，因此如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效提高HashMap的性能。

1.2.2 JDK8发布以后使用数组+链表+红黑树实现：

JDK8中HashMap存储结构

当链表数量大于8时，结构转化为红黑树
  • 当实例化一个HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表中被称为容量（Capacity），在这个数组中可以存放元素的位置我们称为“桶（bucket）”，每个bucket都有自己的索引，系统可以根据索引快速查找bucket中的元素。
  • 每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。

  • 扩容和树形化：

    • 当HashMap中的元素个数超过length * loadFactor时，就会进行数组扩容，扩容机制与JDK7相同
    • 当HashMap中的其中一个链的对象个数达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，节点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于8个，也会把树再转换为链表。

关于映射关系的key是否可以修改？

不建议修改，映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node的hash值了，因此如果已经put到Map中的映射关系，一旦修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。

1.2.3 JDK8中的变化

  1. HashMap map = new HashMap();：默认情况下，先不创建长度为16的数组
  2. 当首次调用map.put()时，再创建长度为16的数组
  3. 数组为Node类型，在JDK7中成为Entry类型
  4. 形成链表结构时，新添加的key-value值在链表尾部（七上八下）
  5. 当数组指定索引位置的链表长度大于8时，且map中的数组的长度大于64，此索引的位置上所有key-value对使用红黑树进行存储

1.4 HashMap中的重要成员

  • DEFAULT_INITIAL_CAPACITY：HashMap的默认容量，16
  • MAXIMUM_CAPACITY：HashMap的最大支持容量，2^30
  • DEFAULT_LOAD_FACTOR：HashMap的默认加载因子
  • TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树
  • UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该值时转化为链表
  • MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY，此时应执行resize扩容操作。MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍）
  • table：存储元素的数组，长度总是2^n
  • entrySet：：存储具体元素的集
  • size：：HashMap中存储的键值对的数量
  • modCount：HashMap扩容和结构改变的次数
  • threshold：：扩容的临界值，即容量 * 填充因子
  • loadFactor：填充因子

3. LinkedHashMap

  • LinkedHashMap是HashMap的子类
  • 在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
  • 与LinkedHashSet类似，LinkedHashMap可以维护Map的迭代顺序：迭代顺序与key-value对的插入顺序一致
@Test
public void test2() {
    Map map = new HashMap();

    map.put(123, "AA");
    map.put(345, "BB");
    map.put(1, "CC");

    System.out.println(map);
}

运行结果：

{1=CC, 345=BB, 123=AA}
@Test
public void test2() {
    Map map = new LinkedHashMap();

    map.put(123, "AA");
    map.put(345, "BB");
    map.put(1, "CC");

    System.out.println(map);
}

运行结果：

{123=AA, 345=BB, 1=CC}

4. TreeMap

  • TreeMap存储key-value数据时，需要根据key-value对进行排序。TreeMap可以保证所有key-value对处于有序状态。
  • TreeSet底层使用红黑树结构存储数据

  • TreeMap的排序：

    • 自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则会抛出ClassCastException异常
    • 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中所有key进行排序。此时不需要Map的key实现Comparable接口
  • TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0

5. Hashtable

  • Hashtable是Map的古老实现类，JDK1.0中就提供了。不同于HashMap，HashTable是线程安全的
  • Hashtable的实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用
  • 与HashMap不同，Hashtable不允许使用null作为key和value
  • 与HashMap一样，Hashtable也不能保证其中key-value对的顺序
  • Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。

6. Properties

  • properties类是HashTable的子类，该对象用于处理属性文件
  • 由于属性文件里的key、value都是字符串类型，所以Properties里的key和value都是字符串类型
  • 存取数据时，建议使用setProperty(String key, String value)方法和getProperty(String key)方法。

7. Collections工具类

  • Collections是一个操作Set、List和Map等集合的工具类
  • Collection中提供了一系列静态方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

7.1 排序操作：

  • reverse(List)：反转List中元素的顺序
  • shuffle(List)：对List集合元素进行随机排序
  • sort(List)：根据元素的自然顺序对指定List集合元素按升序排序
  • sort(List, Comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序操作
  • swap(List, int, int)：将指定list集合中的i处元素和j处元素进行交换

7.2 查找、替换

  • Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
  • Object max(Collection, Comparator)：根据Comparator指定的顺序，返回给定集合中的最大元素
  • Object min(Collection)：根据元素的自然顺序，返回给定集合中的最小元素
  • Object min(Collection, Comparator)：根据Comparator指定的顺序，返回给定集合中的最小元素
  • int frequency(Collection, Object)：返回指定集合中指定元素的出现次数
  • void copy(List desc, List src)：将src中的内容复制到dest中，
  • boolean replaceAll(List list, Object oldVal, Object newVal)：使用新值替换List对象的所有旧值
List dest = Arrays.asList(new Object[List.size()]);
Collections.copy(dest, list);
使用copy()方法时应使用如上方式初始化目标列表

7.3 同步控制

Collections类中提供了多个synchronizedXxx()方法，该方法可将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题

最后修改：2021 年 04 月 08 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏