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

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

概述

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

目录

主要内容

0x01:概述

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

  • HashMap:作为 Map 的主要实现类;线程不安全的,效率高;存储 nullkeyvalue

    • LinkedHashMap

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

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

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

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

  • Hashtable:作为古老的实现类;线程安全的,效率低;不能存储 nullkeyvalue

    • Properties:常用来处理配置文件。keyvalue 都是 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 作为 keyvalue
  • HashMap 一样, Hashtable 也不能保证其中 Key-Value 对的顺序

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

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

0x08:Properties处理配置文件

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

由于属性文件里的 keyvalue 都是字符串类型,所以 Properties 里的 keyvalue 都是字符串类型

存取数据时,建议使用 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 与其他的实现类例如 TreeMapHashtable的一些区别。

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

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