Java集合_Map接口(HashMap、TreeMap实现类)源码剖析

本场 Chat 分享主要介绍 Java 中的 Map 集合中的 HashMap、TreeMap。将从源码进行分析，避免一些人只听其说，不知其理，从而让读者深层次的理解 HashMap 的底层原理与实现。

本场 Chat 内容将涉及如下：

• Map 接口及常用方法；
• Map 接口及其子接口；
• HashMap 在 JDK7 中实现原理；
• LinkedHashMap 的底层实现原理；
• HashMap 在 JDK8 中相较于 JDK7 在底层实现方面的不同；
• TreeMap 的实现；
• 使用 Properties 读取配置文件。

Map(双列集合框架) 1、Map 接口及实现类概述

Map 接口：存储的是一对一对的数据：key-value

• HashMap:主要实现类；线程不安全的，效率高；允许添加 null 的 key 或 null 的 value
• LinkedHashMap：是 HashMap 的子类，可以实现照添加的顺序实现遍历。（因为使用了一对双向链表记录添加元素的先后顺序），对于频繁的遍历操作，建议使用此类。
• TreeMap：可以照元素 key 的指定的属性的大小实现遍历。底层使用红黑树实现。
• Hashtable：古老实现类；线程安全的，效率低；不允许添加 null 的 key 或 null 的 value
• Properties:常用来处理属性文件。key 和 value 都是 String 类型。    

2、常用实现类结构

​​​​​​​​

3、关于对 Map的理解

1. Map 中的 key 是无序的、不可重复的。key 构成的集合是 Set --->需要重写必要的 hashCode()和 equals()。

2. Map 中的 value 是无序的、可重复的。value 构成的集合是 Collection --->需要重写必要的 equals()。Map 中的一个键值对构成一个 entry。

3. Map 中的 entry 是无序的、不可重复的。entry 构成的集合是 Set。

   如图：

4、常用方法

增：put(Object key,Object value)删：remove(Object key)改：put(Object key,Object value)查：get(Object key)长度：size()遍历：keySet() 、 values()、entrySet()  

5、内部结构实现原理

很重要，必须要掌握。

5.1 HashMap 在 jdk7 中实现原理：

HashMap map = new HashMap();//Entry[] table = new Entry[16];...map.put(key1,value1);// key1,value1 会封装在一个 entry 对象中。将此对象存放到 table 数组中  将 key1,value1 添加到 table 中，首先根据 key1 所在类的 hashCode()方法，计算 key1 的哈希值 1，然后使用某种算法，得到哈希值 2。 哈希值 2 再使用 indexFor()方法得到其在底层 table 数组中的存放位置：index。（064 时，将此索引位置上的元素修改为使用红黑树进行存储。

形成链表时，新添加的元素在链表的结尾。 

5.3 LinkedHashMap 的底层实现原理

LinkedHashMap 的底层实现：在 HashMap 底层结构的基础上，添加了双向链表。

底层实现：

//LinkedHashMap 的内部类 Entry，定义如下：static class Entry extends HashMap.Node {      Entry before, after;//双向链表结构      Entry(int hash, K key, V value, Node next) {          super(hash, key, value, next);      }}

主要定义一个静态类，创建了一个 before 前置节点和一个 after 后置节点。

5.4 TreeMap 的实现

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable

Java 的 TreeMap 是集合框架中的一个实现类，TreeMap 继承了 AbstractMap。

• TreeMap 实现了 NavigableMap 接口，提供了多种方便的查找功能；
• TreeMap 实现了 Cloneable 接口，可以克隆；
• TreeMap 实现了 Serialiable 接口，可以序列化。

TreeMap 常用方法：

• public V put(K key, V value) 添加一对键值对

• public V remove(Object key) 删除对应的键值对

• public void clear() 删除所有元素

• public Map.Entry ceilingEntry(K key) 返回 map 中键值不小于参数 key 的最小键值对应的键值对，如果没有则返回 null

• public final boolean containsKey(Object key) 判断是否含有某一键值

• public boolean containsValue(Object value) 判断是否含有某一 value

• public V replace(K key, V value) 修改一对键值对

• public Comparator