1. MAP接口概述

1.1 MAP体系结构

  • Map:双列数据,存储key-value数据

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

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

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

典型面试题:

  1. HashMap的底层实现原理
  2. HashMapHashTable的异同
  3. CurrentHashMapHashTable的区别

1.2 对MAP结构的理解

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

Map存储示意图

1.3 常用方法

  • Object put(Object key, Object value):将指定键值对添加(或修改)当前map对象中
  • void putAll(Map m):将m中所有的key-value值存放到当前Map
  • Object remove(Object key):移除指定keykey-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():返回Mapkey-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 概述

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

1.2 HashMap存储结构

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

请输入图片描述

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

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

JDK8中HashMap存储结构

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

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

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

不建议修改,映射关系存储到HashMap中会存储keyhash值,这样就不用在每次查找时重新计算每一个EntryNodehash值了,因此如果已经putMap中的映射关系,一旦修改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_CAPACITYHashMap的默认容量,16
  • MAXIMUM_CAPACITYHashMap的最大支持容量,2^30
  • DEFAULT_LOAD_FACTORHashMap的默认加载因子
  • TREEIFY_THRESHOLDBucket中链表长度大于该默认值,转化为红黑树
  • UNTREEIFY_THRESHOLDBucket中红黑树存储的Node小于该值时转化为链表
  • MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量。(当桶中Node的数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY,此时应执行resize扩容操作。MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍)
  • table:存储元素的数组,长度总是2^n
  • entrySet::存储具体元素的集
  • size:HashMap中存储的键值对的数量
  • modCountHashMap扩容和结构改变的次数
  • threshold::扩容的临界值,即容量 * 填充因子
  • loadFactor:填充因子

3. LinkedHashMap

  • LinkedHashMapHashMap的子类
  • 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进行排序。此时不需要Mapkey实现Comparable接口
  • TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0

5. Hashtable

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

6. Properties

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

7. Collections工具类

  • Collections是一个操作SetListMap等集合的工具类
  • 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 日
如果觉得我的文章对你有用,请随意赞赏