本篇主要内容：映射Map及其实现，Map的应用，Map与Set的对比
映射Map
数据结构里的所谓映射是键值对的数据组织方式，每一个键对应一个值{key，value}，接触过Python语言的会发现这和Python中的字典dict很类似。
映射作为一种高级数据结构在实际中有很多应用，比如统计单词词频{单词：词频}，存储会员信息{会员ID：会员信息}等等。
映射其实和集合是有一定联系的，这会在本篇最后做简要讨论。同集合一样，映射也可以使用不同的底层数据结构来实现，本篇将和集合的实现一样，用链表和二分搜索树两种方式来实现映射Map，首先创建Map接口：
'''Map.java'''
public interface Map<K,V> {
void add(K key, V value);
V remove(K key);
boolean contains(K key);
V get(K key);
void set(K key, V value);
int getSize();
boolean isEmpty();
}
从接口可以看到我们要实现的Map要实现增删查改的功能。
基于链表方式的Map
这里需要说明的是，由于Map是键值对方式的存储，上篇文章中使用的链表类节点只能存储一个值，所以不再适用，不过稍微修改链表节点加入键值（K key，V value）就可使之满足Map要求：
'''LinkedListMap.java'''
public class LinkedListMap<K,V> implements Map<K,V> {
private class Node{
//链表节点是内部类而且私有，用户不需知道底层如何,屏蔽实现细节
public K key;
public V value;
public Node next;
public Node(K key, V value, Node next){
this.key = key;
this.value = value;
this.next = next;
}
public Node(K key){
this(key, null, null);
}
public Node(){
this(null, null,null);
}
@Override
public String toString(){
return key.toString()+" : "+value.toString();
}
}
private Node dummyhead;
private int size;
//映射构造函数
public LinkedListMap(){
dummyhead = new Node();
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
//增删改查
private Node getNode(K key){
//辅助函数
Node cur = dummyhead.next;
while(cur != null){
if(cur.key.equals(key))
return cur;
cur = cur.next;
}
return null;
}
@Override
public boolean contains(K key){
return getNode(key) != null;
}
@Override
public V get(K key){
Node node = getNode(key);
return node == null ? null : node.value;
}
@Override
public void add(K key, V value){
//key不能相同,相同则更新
Node node = getNode(key);//查看当前映射中是否有key
if(node == null){
dummyhead.next = new Node(key,value,dummyhead.next);
size ++;
}else
node.value = value;//更新
}
@Override
public void set(K key, V newValue){
Node node = getNode(key);
if(node == null)
throw new IllegalArgumentException(key + "doesn't exist!");
else
node.value = newValue;
}
@Override
public V remove(K key){
Node prev = dummyhead;
while(prev.next!=null){
if(prev.next.key.equals(key))
break;
prev = prev.next;
}
if(prev.next!=null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
return delNode.value;
}
return null;
}
}
基于BST实现的Map
同样，基于BST实现Map时，BST节点我们也做了一定的改进，节点是键值对（K key，V value），而且由于BST实际是一种有序的组织方式，所以键值对中的key要求必须是可以比较的：
public class BSTMap<K extends Comparable<K>,V>implements Map<K,V> {
private class Node {
//二分搜索树作为内部私有类，节点对用户是屏蔽的,用户不必知道节点如何
public K key;
public V value;
public Node left, right;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
public BSTMap(){
root = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
@Override
//添加操作
public void add(K key,V value){
root = add(root,key,value);
}
private Node add(Node node, K key, V value){
//向以Node为根的二分搜索树Map插入(key,value),递归
//返回插入新节点后二分搜索树的根
if(node == null){
size ++;
return new Node(key, value);
}
//以上是递归终止条件,下是递归调用
if(key.compareTo(node.key)<0)
node.left = add(node.left,key,value);
else if(key.compareTo(node.key)>0)
node.right = add(node.right,key,value);
else
node.value = value;
return node;
}
//辅助函数，返回以node为根节点的BST中，key所在的节点
private Node getNode(Node node,K key){
if(node == null)
return null;
if(key.compareTo(node.key) == 0)
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left,key);
else
return getNode(node.right,key);
}
@Override
public boolean contains(K key){
return getNode(root,key) != null;
}
@Override
public V get(K key){
Node node = getNode(root,key);
return node == null ? null : node.value;
}
@Override
public void set(K key,V newValue){
Node node = getNode(root,key);
if(node == null)
throw new IllegalArgumentException(key + "doesn't exist");
node.value = newValue;
}
//删除操作辅助函数
private Node minimum(Node node){
//返回以node为根的BST的最小值所在节点
if(node.left == null)
return node;
return minimum(node.left);
}
private Node removeMin(Node node){
//删除以node为根的BST的最小节点，返回删除节点后新的BST的根
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}else{
node.left = removeMin(node.left);
return node;
}
}
@Override
public V remove(K key){
Node node = getNode(root, key);
if(node != null) {
root = remove(root, key);
return node.value;
}
else
return null;
}
//递归
private Node remove(Node node,K key){
if(node == null)
return null;
if(key.compareTo(node.key)<0){
node.left = remove(node.left,key);
return node;
}else if(key.compareTo(node.key)>0){
node.right = remove(node.right,key);
return node;
}else{
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}else if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}else{
Node successor = minimum(node.right);//在右子树找最小值节点，即是当前待删除节点的前驱
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
}
}
可以看到基于BST实现的Map中最难的操作是删除操作，为了实现删除操作我们写了几个辅助函数，不过这里的逻辑和BST中删除的逻辑是一致的，可以直接复用之前BST类的代码，只需做几处修改即可，BST中比较的是节点值的大小，而BSTMap中比较的是键值对中的键。
链表Map和BSTMap的性能对比
显然这两种实现方式是有性能差异的，在上篇集合的实现中，我们比较了两种方式实现集合的各种操作的时间复杂度，其实映射和集合中的各种操作本质是一样的，所以对于映射，时间复杂度的分析和集合相同。
| 操作\方式 | 链表Map | BSTMap |
|---|---|---|
| 增 | O(n) | O(h) |
| 删 | O(n) | O(h) |
| 改 | O(n) | O(h) |
| 查 | O(n) | O(h) |
平均而言BSTMap的时间复杂度是，这是远远优于链表方式的。
接下来测试一下这两种方式的性能，以一个统计词频的例子来测试，让他们来统计一下Little Prince这本书中一些单词出现的频率：
'''Main.java'''
import java.util.ArrayList;
public class Main {
private static double testMap(Map<String, Integer>map,String filename){
long startTime = System.nanoTime();
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile(filename, words)) {
System.out.println("Total words: " + words.size());
for (String word : words) {
if (map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);//初始化词频为1
}
System.out.println("Total different words: "+map.getSize());
System.out.println("Frequency of Prince: " + map.get("prince"));
System.out.println("Frequency of Rose: " + map.get("rose"));
System.out.println("Frequency of Love: " + map.get("love"));
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
String filename = "little-prince.txt";
System.out.println("Little Prince词频统计：");
System.out.println("链表方式：");
LinkedListMap<String, Integer> linkedListMap = new LinkedListMap<>();
double time1 = testMap(linkedListMap,filename);
System.out.println("Time consuming:"+time1);
System.out.println("\n\n二分搜索树方式；");
BSTMap<String, Integer> bstMap = new BSTMap<>();
double time2 = testMap(bstMap,filename);
System.out.println("Time consuming:"+time2);
}
}
运行结果：
词频统计
可以看到，BSTMap的用时显然是少于链表Map方式的。
集合与映射的对比应用
来看一道LeetCode上的算法设计题目：
LeetCode349
这是一个求交集的任务，数组中元素是唯一的，所以可以使用集合这种数据结构，这里使用的是java标准库中的集合TreeSet，它是基于平衡二叉树实现的：
import java.util.ArrayList;
import java.util.TreeSet;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
TreeSet<Integer> set = new TreeSet<>();
for(int num:nums1)
set.add(num);
ArrayList<Integer> list = new ArrayList<>();
for(int num:nums2){
if(set.contains(num)){
list.add(num);
set.remove(num);
}
}
int res[] = new int[list.size()];
for(int i=0;i<list.size();i++)
res[i] = list.get(i);
return res;
}
}
提交，获得通过！
再来看一道与上题极其类似的题目：
LeetCode350
与上题不同的是，这里的数组中有带重复元素，而且交集中也带有重复元素，所以唯一元素集合不能再使用，于是我们考虑映射（java标准库中的映射TreeMap也是基于平衡二叉树的），对每一个数字进行频率统计，这样再求交集：
import java.util.ArrayList;
import java.util.TreeMap;
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int num:nums1){
if(!map.containsKey(num))
map.put(num,1);//add
else
map.put(num,map.get(num)+1);//set
}
ArrayList<Integer> list = new ArrayList<>();
for(int num:nums2){
if(map.containsKey(num)){
list.add(num);
map.put(num,map.get(num)-1);
if(map.get(num)==0)
map.remove(num);
}
}
int res[] = new int[list.size()];
for(int i=0;i<list.size();i++)
res[i] = list.get(i);
return res;
}
}
提交，获得通过！
这里需要指出的是，实际上我们也可以修改Set的实现方式，使之支持带有重复元素的集合。而且Set与Map也是可以互相实现的，Set实现Map只需要将每个节点定义为键值对{key，value}即可，而Map实现Set只需要只在key中存储元素即可，value中全部存null。不过实际中考虑到空间和性能，往往还是单独实现Set和Map。
