Java Collection | Set 3 (Map)

今天我们来谈谈 Map 接口，先看看 Oracle 官方文档对其解释：

public interface Map

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.

The Map interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map’s collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

Source: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

由以上这段话，我们可以看出它具有如下几个特点：

它储存键 (key) 值 (value) 对，不允许有重复的 key，每一个 key 对应一个特定的值
Map 接口不继承于 Collection 接口
Map 接口中，有些实现类允许储存 null (HashMap 和 LinkedHashMap)，有些不允许(TreeMap)

Set 接口提供了三种 view 的方法:

Set<Map.Entry<K,V>>	    entrySet()
//Returns a Set view of the mappings contained in this map.
Set<K>	     keySet()
//Returns a Set view of the keys contained in this map.
Collection<V>	     values()
//Returns a Collection view of the values contained in this map.

代码示例如下

import java.util.*;
public class MapDemo{
    public static void main(String[] args){
	Map<String, Integer> hm = new HashMap<>();
	hm.put("Placebo", new Integer(1));
	hm.put("New Order", new Integer(2));
	hm.put("Queen", new Integer(3));
	hm.put("The Doors", new Integer(4));
	System.out.println(hm);  // {New Order=2, Queen=3, Placebo=1, The Doors=4}
	// Return Set view
	Set<Map.Entry<String, Integer>> set1 = hm.entrySet();
	for (Map.Entry<String, Integer> temp : set1){   // New Order: 2
            System.out.print(temp.getKey() + ": ");	// Queen: 3
	    System.out.println(temp.getValue());	// Placebo: 1
	}						// The Doors: 4
	// Returns a Set view of the keys contained in this map.
	Set<String> set2 = hm.keySet();
	System.out.println(set2);    // [New Order, Queen, Placebo, The Doors]
    }
}

Image Source：https://i.stack.imgur.com/FbGNV.png

Map 接口有很多实现类，在此我们主要关注其中的三种 HashMap, LinkedHashMap TreeMap, 下面来一一讨论

HashMap

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Source: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

首先，我们先来了解一下什么是 HashMap。要了解 HashMap，得先从 Array 开始说起

大家都知道 Array 是用来存储元素最基本得一种数据结构，它的最大特点是“索引”
这意味着我们可以根据索引在常数时间内根据索引获取，修改元素。 O(1)
Array 在内存中的存储方式是连续的，每一个 cell 是相邻排列的
这表明我们在创造 Array 时，就必须要规定 size，不然内存就不知道要分配多少空间给该 Array
这也就是 Array 的一大缺点
当 initial 很大的 capacity 又用不到时，内存会被浪费
当 initial 了很小的 capacity 又不够时，再添加元素时就会很麻烦

讲完了 Array 的优缺点，再来看看我们前些天讨论的 LinkedList
LinkedList 的优点是 size 不固定，想添加多少个元素都可以
因为 LinkedList 的每个 node 在内存中是离散的
它们靠指向下一个 node 的指针就可以找到下一个元素
不需要像 Array 那样排列在一起
当需要添加元素时，内存就会找到任意一块空的 memory 来供其使用
当然，没有“索引”这个概念也为 LinkedList 带来了缺点
这意味着每次我们想要查找元素时，都要 traverse 整个 list
时间复杂度为 O(n)

这时，我们就要考虑，有没有一种数据结构，能同时满足 Array 和 LinkedList 的优点呢
这种数据结构就是 HashTable
它既能根据提供的 Key 在 O(1) 时间内查找元素，需要扩容的时候也能 resize
它的内部结构是怎样的呢，这里有个 YouTube 视频讲的很清楚了
简单点来说，它就是一个 array of nodes, 每个 node 包括四个 fields：
key, hashcode, value, pointer
它底层使用了一种叫 hashing 的算法
传入 key，返回某个特定的值，我们把该值称为 hashcode
相当于数组中的 index，再根据该 hashcode，把 value 传到对应位置的 array 中
如果恰好又两个不同的 key，经过 hashing 算法后返回了同一个hashcode 怎么办？
这个时候就要用到 node 中的第四个 field 了：pointer
这两个 hashcode 一样的 key，都把自己的 value 存放到同一个 array 的 cell
此时这个 cell 就相当于 linkedlist 了

这时我们就要分析它的时间复杂度了
当我们想查找某个元素时，最坏的情况是，所有的 key 都有相同的 hashcode
即所有的 value 都以 linkedlist 的形式存放在了同一个 cell 中
此时需要 traverse 整个 linkedlist，时间复杂度为 O(n)
在 Java8 中，对该情形做了改进
当 linkedlist 元素超过8个时，linkedlist 会被转化成平衡树
时间复杂度从 O(n) 降到 O(lgn)

HashMap 的内部结构就是使用的 HashTable
我们来看看 HashMap 的构造器

HashMap()
/*Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).*/
HashMap(int initialCapacity)
/*Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).*/
HashMap(int initialCapacity, float loadFactor)
/*Constructs an empty HashMap with the specified initial capacity and load factor.*/
HashMap(Map<? extends K,? extends V> m)
/*Constructs a new HashMap with the same mappings as the specified Map.*/

HashMap 常用方法示例

import java.util.*;
public class HashMapDemo{
    public static void main(String[] args){
	HashMap<String, Integer> map = new HashMap<>();
	map.put("Kurt Cobain", 1);
	map.put("Jim Morrison", 2);
	map.put("Peter Hook", 3);
	map.put("Slash", 4);
	// {Jim Morrison=2, Peter Hook=3, Slash=4, Kurt Cobain=1}
	System.out.println(map);  
	System.out.println(map.size());    // 4
	if (map.containsKey("Kurt Cobain")){
	    System.out.println(map.get("Kurt Cobain"));   // 1
	}
	System.out.println(map.isEmpty());   // false
	System.out.println(map.containsValue(5)); // false
	map.remove("Slash");
	map.replace("Kurt Cobain", 1, 7);
	System.out.println(map.size());     // 3
	System.out.println(map.get("Kurt Cobain"));    // 7
	// keySet() method returns all the keys in HashMap
	Set<String> temp1 = map.keySet();
	System.out.println(temp1);  // [Jim Morrison, Peter Hook, Kurt Cobain]
	// values() method return all the values in HashMap
	Collection<Integer> temp2 = map.values();
	System.out.println(temp2); // [2, 3, 7]
	// entrySet() returns all the keys with their values present in Hashmap
	Set<Map.Entry<String, Integer>> temp3 = map.entrySet();
	System.out.println(temp3);  // [Jim Morrison=2, Peter Hook=3, Kurt Cobain=7]
    } 
}

LinkedHashMap

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

Source: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

LinkedHashMap 有如下特点：

LinkedHashMap 本质上和 HashMap 没有太大区别，除了可以 organize element in insertion order 以外
底层采用了 Doubly Linked List 来组织 HashMap
可以允许有一个 null 作为 key，多个 null 作为value

常用方法示例

import java.util.*;
public class LinkedHashMapDemo{
    public static void main(String[] args){
	LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
	map.put("whatever", 1);
	map.put("nevermind", 2);
	map.put("somehow", 3);
	map.put("pale blue eyes", 4);
	// {whatever=1, nevermind=2, somehow=3, pale blue eyes=4}
	System.out.println(map);
	System.out.println(map.size());   // 4
	System.out.println(map.isEmpty());   // false
	System.out.println(map.containsKey("nevermind")); // true
	System.out.println(map.containsValue(5));   // false
	System.out.println(map.remove("somehow")); // 3
	// {whatever=1, nevermind=2, pale blue eyes=4}
	System.out.println(map);
    }
}

TreeMap

TreeMap 可以看作为 HashMap 的 sorted 版本
TreeMap 实现了红黑树(red-black tree), HashMap 实现了 hashing
TreeMap 方法和操作基本与 HashMap 一致，在此不过多虚数，我们来看一个应用

给定一个数组，返回每个元素出现的次数
Example:
input: array[] = {1, 1, 2, 3, 4, 1, 2, 3}
output:
Frequency of 1 is 3
Frequency of 2 is 2
Frequency of 3 is 2
Frequency of 4 is 1

注意 TreeMap 可以 sort element，所以返回的元素时＝是从小到大排序的

import java.util.*;
public class TreeMapDemo{
    public static void main(String[] args){
	int[] array = {1, 1, 2, 3, 4, 1, 2, 3};
	frequency(array);
    }
    public static void frequency(int[] array){
	TreeMap<Integer, Integer> map = new TreeMap<>();
		
	for (int i = 0; i < array.length; i++){
 	    Integer count = map.get(array[i]); 
	    if (count == null){
		map.put(array[i], 1);
	    }
	    else{
		map.put(array[i], ++count);
	    }
 	}
 	for (Map.Entry m : map.entrySet()){
 	    System.out.println("Frequency of " + m.getKey() + " is " + m.getValue());	
 	}
    }
}

关于 Map 接口的讨论就到这里
以上内容如有疏漏或不足之处，欢迎与我讨论
邮箱：entropy714@gmail.com
微信：cobain0714