【JAVA高级&集合框架】浅谈Map

【JAVA高级&集合框架】浅谈Map

232 次访问
· JAVA基础&高级

概述

对 JAVA 的集合框架中的 Map 下的一些子类相关的原理以及应用进行复盘。

目录

主要内容

0x01：概述

Map: 双列数据，存储 key-value 对的数据

  • HashMap：作为 Map 的主要实现类；线程不安全的，效率高；存储 null 的 key 和 value

    • LinkedHashMap：

      保证在遍历map元素时，可以按照添加的顺序实现遍历。

      原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。

      对于频繁的遍历操作，此类执行效率高于HashMap。

  • TreeMap：保证按照添加的 key-value 对进行排序，实现排序遍历。此时考虑 key 的自然排序或定制排序

  • Hashtable：作为古老的实现类；线程安全的，效率低；不能存储 null 的 key 和 value

    • Properties：常用来处理配置文件。key 和 value 都是 String 类型

HashMap 的底层结构：

  • jdk7 及之前：数组+链表

  • jdk8：数组+链表+红黑树

Map的基础树如下图

0x02：对Map中的结构理解

  • Map中的 key 是无序的，不可重复的，使用 Set 储存所有的key

    • 在实际开发中，key的值可能是我们自定义的一个类型，所以要求 key 所在的类需要重写 equals() 和 hashCode() 方法

      以HashMap为例

  • Map中的 value 是无序的，可重复的，使用Collection储存所有的value

  • value所在类需要重写 equals()

  • Map中的 entry：无序的、不可重复的，使用Set储存所有的 entry 对象

    一个键值对：key-value构成了一个Entry对象

如下图所示

0x03：浅谈HashMap底层原理

我们先以 jdk7 为例

HashMap map =  new HashMap()

在实例化以后，底层创建了长度为 16 的以为数组 Entry[] table 如下代码

/**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

向 map 存入数据

map.put("key1","value1")

存入数据的过程如下：

1、在向map存入数据时，首先会调用 key1 所在类的 hashCode() 计算key1哈希值，此哈希值经过某种算法计算以后，得到在 Entry 数组中的存放位置，如下

public V put(K key, V value) {
    //省略....
    int hash = hash(key);
    //通过hash计算得到一个数组的索引坐标
    int i = indexFor(hash, table.length);
    //省略...
}

上述代码摘自 JDK7 中的 HashMap源码

2、如果此位置上的数据为空，此时的 key1-value1 添加成功。（情况1）

3、如果此位置上的数据不为空 (意味着此位置上存在一个或多个数据 (以链表形式存在) , 则开始比较 key1 和已经存在的一个或多个数据的哈希值

  • 如果 key1 的哈希值与已经存在的数据的哈希值都不相同，此时 key1-value1 添加成功 （情况2）
  • 如果key1的哈希值和已经存在的某一个数据 (key2-value2) 的哈希值相同，继续比较：调用 key1 所在类的equals(key2) 方法，比较：
    • 如果 equals() 返回 false: 此时 key1-value1 添加成功。（情况3）
    • 如果 equals() 返回 true: 使用 value1 替换 value2。

源码如下

//摘自JDK7中的HashMap源码中的部分代码实现
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    //通过hash计算得到一个数组的索引坐标
    int i = indexFor(hash, table.length);
    //如果计算得出的位置不为空，呈现为链表的结构，开始遍历
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //情况2、3
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    //如果此位置上的数据为空，直接添加 （情况1）
    addEntry(hash, key, value, i);
    return null;
}

补充：关于 “情况2” 和 “情况3”：此时 key1-value1 和原来的数据以链表（单向）的方式存储。

/**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization).  This version needn't worry about resizing the table.
 *
 * Subclass overrides this to alter the behavior of HashMap(Map),
 * clone, and readObject.
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //将当前的数据作的内存地址储存到自身的next中，实现单向链表的方式储存
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

在不断的添加过程中，会涉及到扩容问题，当超出临界值 (且要存放的位置非空) 时，扩容。

  • 默认的扩容方式：扩容为原来容量的 2 倍，并将原有的数据复制过来。部分源码如下

    /**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket.  It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //扩容至原来的两倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

而 “jdk8” 相较于 “jdk7” 在底层实现方面的不同，以下列出常见的

  • new HashMap(): 底层没有马上创建一个长度为 16 的数组，而是在首次调用 put() 方法时，底层创建长度为16的数组

    HashMap 空参的构造方法，相较于 JDK7 中的实现

    /**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

    而 JDK8 中，在调用 put 时，会先调用 putVa() 方法，再由 putVal 内部进行一些逻辑判断，发现当前为首次调用，则再进行调用 resize() 对数组进行初始化，长度为 16。

  • jdk8 底层的数组是：Node[]，而非Entry[]

  • jdk7底层结构只有：数组+链表。而 jdk8 中底层结构：数组+链表+红黑树。

    • 形成链表时，”七上八下“（ jdk7: 新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
    • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64 时，此时此索引位置上的所数据改为使用 "红黑树" 存储。

HashMap源码中的重要常量

  • DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16

  • DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75

    • 为什么是 0.75 ？

      提前扩容的原因：在数组中预留一些空的索引位置，可以使链表和树形结构出现的数量更少，并且还要兼顾数组索引位置的利用率，所以 “加载因子” 定为 0.75 可以使得到一个恰好的扩容临界值，同时兼顾上述的两者。

  • threshold：扩容的临界值， 容量 * 填充因子 ：16 * 0.75 => 12

  • TREEIFY_THRESHOLD：Bucket 中链表长度大于该默认值，转化为红黑树: 8

  • MIN_TREEIFY_CAPACITY：桶中的 Node 被树化时最小的 hash 表容量: 64

拓展

看到这里，我们在回到 HashSet 的源码实现中去看，向 HashSet 存入数时将写入的值存到了 HashMap 中的 key 的位置

而 Value 的位置则使用一个常量进行填充，常量的值为一个空的 Object 对象常量，并且是静态的（只会被创建一次，所有的value都指向同一个），如下代码

所以由此可知，HashSet 实际的底层是使用 HashMap 来进行储存实际上底层是使用 HashMap 去储存的。

0x04：浅谈LinkedHashMap的底层原理

LinkedHashMap 是 HashMap 的子类

在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序，并重写了 HashMap 中的 newNode 方法，如下代码

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

在 LinkedHashMap 新增了一个类 Entry ，并继承了 HashMap.Node ，增加了双向链表的特性，如下代码

/**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

与 LinkedHashSet 类似， LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序 与 Key-Value 对的插入顺序一致

0x05：Map接口常用的方法

添加、删除、修改操作：

  • Object put(Object key,Object value)：

    将指定key-value添加到(或修改)当前map对象中

  • void putAll(Map m) :

    将m中的所有key-value对存放到当前map中

  • Object remove(Object key)：

    移除指定key的key-value对，并返回value

  • void clear()：

    清空当前map中的所有数据

测试代码

@Test
public void test3(){
    Map map = new HashMap();
    //添加
    map.put("AA",123);
    map.put(45,123);
    map.put("BB",56);
    //修改
    map.put("AA",87);

    System.out.println(map);

    Map map1 = new HashMap();
    map1.put("CC",123);
    map1.put("DD",123);

    map.putAll(map1);

    System.out.println(map);

    //remove(Object key)
    Object value = map.remove("CC");
    System.out.println(value);
    System.out.println(map);

    //clear()
    map.clear();//与map = null操作不同
    System.out.println(map.size());
    System.out.println(map);
}

输出结果

{AA=87, BB=56, 45=123}
{AA=87, BB=56, CC=123, DD=123, 45=123}
123
{AA=87, BB=56, DD=123, 45=123}
0
{}

Process finished with exit code 0

元素查询的操作：

  • Object get(Object key)：

    获取指定key对应的value

  • boolean containsKey(Object key)：

    是否包含指定的key

  • boolean containsValue(Object value)：

    是否包含指定的value

  • int size()：

    返回map中key-value对的个数

  • boolean isEmpty()：

    判断当前map是否为空

  • boolean equals(Object obj)：

    判断当前map和参数对象obj是否相等

测试代码

@Test
public void test4(){
    Map map = new HashMap();
    map.put("AA",123);
    map.put(45,123);
    map.put("BB",56);
    // Object get(Object key)
    System.out.println(map.get(45));
    //containsKey(Object key)
    boolean isExist = map.containsKey("BB");
    System.out.println(isExist);

    isExist = map.containsValue(123);
    System.out.println(isExist);

    map.clear();

    System.out.println(map.isEmpty());

}

输出结果

123
true
true
true
Process finished with exit code 0

元视图操作的方法：

  • Set keySet()：

    返回所有key构成的Set集合

  • Collection values()：

    返回所有value构成的Collection集合

  • Set entrySet()：

    返回所有key-value对构成的Set集合

@Test
public void test5(){
    Map map = new HashMap();
    map.put("AA",123);
    map.put(45,1234);
    map.put("BB",56);

    //遍历所有的key集：keySet()
    Set set = map.keySet();
    Iterator iterator = set.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }
    System.out.println();
    //遍历所有的value集：values()
    Collection values = map.values();
    for(Object obj : values){
        System.out.println(obj);
    }
    System.out.println();
    //遍历所有的key-value
    //方式一：entrySet()
    Set entrySet = map.entrySet();
    Iterator iterator1 = entrySet.iterator();
    while (iterator1.hasNext()){
        Object obj = iterator1.next();
        //entrySet集合中的元素都是entry
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "---->" + entry.getValue());

    }
    System.out.println();
    //方式二：
    Set keySet = map.keySet();
    Iterator iterator2 = keySet.iterator();
    while(iterator2.hasNext()){
        Object key = iterator2.next();
        Object value = map.get(key);
        System.out.println(key + "=====" + value);
    }
}

输出结果

AA
BB
45

123
56
1234

AA---->123
BB---->56
45---->1234

AA=====123
BB=====56
45=====1234

Process finished with exit code 0

0x06：TreeMap

TreeMap 存储 Key-Value 对时， 需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。

并且 TreeMap 底层使用红黑树结构存储数据

TreeMap 的 Key 的排序：

  • 自然排序： TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出ClasssCastException
  • 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口

TreeMap自然排序

//自然排序
@Test
public void test1(){
    TreeMap map = new TreeMap();
    User u1 = new User("Tom",23);
    User u2 = new User("Jerry",32);
    User u3 = new User("Jack",20);
    User u4 = new User("Rose",18);

    map.put(u1,98);
    map.put(u2,89);
    map.put(u3,76);
    map.put(u4,100);

    Set entrySet = map.entrySet();
    Iterator iterator1 = entrySet.iterator();
    while (iterator1.hasNext()){
        Object obj = iterator1.next();
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "---->" + entry.getValue());

    }
}

输出结果

User{name='Tom', age=23}---->98
User{name='Rose', age=18}---->100
User{name='Jerry', age=32}---->89
User{name='Jack', age=20}---->76

Process finished with exit code 0

TreeMap定制排序

//定制排序
@Test
public void test2(){
    TreeMap map = new TreeMap(new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof User && o2 instanceof User){
                User u1 = (User)o1;
                User u2 = (User)o2;
                return Integer.compare(u1.getAge(),u2.getAge());
            }
            throw new RuntimeException("输入的类型不匹配！");
        }
    });
    User u1 = new User("Tom",23);
    User u2 = new User("Jerry",32);
    User u3 = new User("Jack",20);
    User u4 = new User("Rose",18);

    map.put(u1,98);
    map.put(u2,89);
    map.put(u3,76);
    map.put(u4,100);

    Set entrySet = map.entrySet();
    Iterator iterator1 = entrySet.iterator();
    while (iterator1.hasNext()){
        Object obj = iterator1.next();
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "---->" + entry.getValue());

    }
}

输出结果

User{name='Rose', age=18}---->100
User{name='Jack', age=20}---->76
User{name='Tom', age=23}---->98
User{name='Jerry', age=32}---->89

Process finished with exit code 0

TreeMap 判断两个key相等的标准：两个 key 通过compareTo()方法或者compare()方法返回0。

0x07：Hashtable

Hashtable 是个古老的 Map 实现类， JDK1.0 就提供了。不同于HashMap，Hashtable 是线程安全的。

Hashtable 实现原理和 HashMap 相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。

  • 与 HashMap 不同， Hashtable 不允许使用 null 作为 key 和 value
  • 与 HashMap 一样， Hashtable 也不能保证其中 Key-Value 对的顺序

Hashtable 判断两个 key 相等、两个 value 相等的标准， 与HashMap一致。

由于目前实际开发中 Hashtable 用得较少，所以这里就不进行详细的探究。

0x08：Properties处理配置文件

Properties 类是 Hashtable 的子类，该对象用于处理属性文件

由于属性文件里的 key、 value 都是字符串类型，所以 Properties 里的 key和 value 都是字符串类型

存取数据时，建议使用 setProperty(String key,String value)方法和 getProperty(String key) 方法，如下举例

新建一个 jdbc.properties 文件，写入下面的内容

username=lcyee
password=abc123

编写测试代码

//Properties:常用来处理配置文件。key和value都是String类型
public static void main(String[] args)  {
    FileInputStream fis = null;
    try {
        Properties pros = new Properties();

        fis = new FileInputStream("jdbc.properties");
        pros.load(fis);//加载流对应的文件

        String name = pros.getProperty("username");
        String password = pros.getProperty("password");

        System.out.println("username = " + name + ", password = " + password);
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        if(fis != null){
            try {
                fis.close();
            } catch (IOException e) {
                e.printStackTrace();
            }

        }
    }

}

输出结果

username = lcyee, password = abc123

Process finished with exit code 0

0x09：Collections工具类

  • reverse(List)：

    反转 List 中元素的顺序

  • shuffle(List)：

    对 List 集合元素进行随机排序

  • sort(List)：

    根据元素的自然顺序对指定 List 集合元素按升序排序

  • sort(List，Comparator)：

    根据指定的 Comparator 产生的顺序对 List 集合元素进行排序

  • swap(List，int， int)：

    将指定 list 集合中的 i 处元素和 j 处元素进行交换

  • Object max(Collection)：

  • 根据元素的自然顺序，返回给定集合中的最大元素

  • Object max(Collection，Comparator)：

    根据 Comparator 指定的顺序，返回给定集合中的最大元素

  • Object min(Collection)

  • Object min(Collection，Comparator)

  • int frequency(Collection，Object)：

    返回指定集合中指定元素的出现次数

  • void copy(List dest,List src)：

    将src中的内容复制到dest中

  • boolean replaceAll(List list，Object oldVal，Object newVal)：

    使用新值替换 List 对象的所有旧值

这里我们重点举例 copy 方法

@Test
public void test2(){
    List list = new ArrayList();
    list.add(123);
    list.add(43);
    list.add(765);
    list.add(-97);
    list.add(0);

    //报异常：IndexOutOfBoundsException("Source does not fit in dest")
    // List dest = new ArrayList();
    //  Collections.copy(dest,list);
    
    //正确的：
    List dest = Arrays.asList(new Object[list.size()]);
  System.out.println(dest.size());//list.size();
    Collections.copy(dest,list);
    System.out.println(dest);
}

从上述代码可以看出，如果我们需要使用 Collections.copy() 方法对 List 进行从 A 向 B 的复制操作，需要 A 和 B 都持有对等的大小， 通过 Arrays.asList(new Object[list.size()]); 的方式，向 B 中创建于 A 对等数量的空对象，然后再进行复制操作。

同步控制

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

//返回的list1即为线程安全的List
List list1 = Collections.synchronizedList(list);

我们从 Collections 的源码中可以看到大量的使用了 synchronized 关键字

0xFF：拓展

CurrentHashMap 与 Hashtable 的异同

为了在高并发的常见下操作Map获得更高的执行效率，所以引入了 CurrentHashMap ，其实现了分段锁的技术。

总结

  • 巩固了 HashMap 的部分实现原理以及其扩容方案的实现。
  • 并且了解了 HashMap 与其他的实现类例如 TreeMap、Hashtable的一些区别。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://codeyee.com/archives/java-map.html

【JAVA高级&泛型】知识点整理