映射
是一种可以存储(键、值)数据对的数据结构(key、value)，键跟值一一对应，通过键来寻找或删除对应的值，分为有序映射 (基于搜索树的实现) 和无序映射 (基于哈希表和链表的实现) ，有序即映射中的键具有顺序性。通常无序映射是基于哈希表 (HashMap) 来实现的，因为基于链表实现的映射的性能太差。
映射代码实现
首先，我们先定义一个映射需要用到的接口方法，因为映射的底层实现可以是多样的，只要实现了接口方法的，都可以称为映射。
映射接口定义
public interface Map<K, V> {
/**
* 添加一个键值对，如果 key 存在，则直接更新值
*/
void add(K key, V value);
/**
* 根据键来移除该键值对
*/
V remove(K key);
/**
* 是否有包含该键的键值对
*/
boolean contains(K key);
/**
* 获取 key 对应的 value
*/
V get(K key);
/**
* 修该键值对
*/
void set(K key, V newValue);
/**
* 返回键值对的数量
*/
int getSize();
/**
* 映射是否为空
*/
boolean isEmpty();
}
底层为二分搜索树的映射
public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
private Node root;
private int size;
// 向二分搜索树中添加新的元素(key, value)
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
/**
* 向以node为根的二分搜索树中插入元素(key, value)，递归算法
* 返回插入新节点后二分搜索树的根
*/
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
// 不存在，添加一个节点
return new Node(key, value);
}
if (node.key.compareTo(key) < 0) {
node.right = add(node.right, key, value);
} else if (node.key.compareTo(key) > 0) {
node.left = add(node.left, key, value);
} else {
// 存在，更新值
node.value = value;
}
return node;
}
@Override
public V remove(K key) {
Node node = getNode(root, key);
if (node == null) {
// 节点不存在，返回 null
return null;
} else {
root = remove(root, key);
return node.value;
}
}
private Node remove(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
} else {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
Node successor = minimum(node.right);
successor.left = node.left;
successor.right = removeMin(node.right);
node.left = node.right = null;
return successor;
}
return node;
}
/**
* 向以 node 为根的树中删除最小元素
* 返回删除节点后的树的根
*/
private Node removeMin(Node node) {
// 找到要删除的节点
if (node.left == null) {
// 找到该节点的右节点(不用管是否为null)
Node retNode = node.right;
// 将要删除的节点的右节点置为 null
node.right = null;
// 维护数量
size--;
// 返回右节点
return retNode;
}
node.left = removeMin(node.left);
return node;
}
/**
* 向以 node 为根的树中找最小元素并返回
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
/**
* 向以 node 为根的树中查询 key ,递归算法
*/
private boolean contains(Node node, K key) {
if (node == null) {
return false;
}
if (key.compareTo(node.key) < 0) {
return contains(node.left, key);
} else if (key.compareTo(node.key) > 0) {
return contains(node.right, key);
} else {
return true;
}
}
@Override
public boolean contains(K key) {
// if (key == null) {
// return false;
// } else {
// return contains(root, key);
// }
return getNode(root, key) != null;
}
@Override
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
/**
* 向以 node 为根的树中查询 key 对应的节点,递归算法
*/
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else if (key.compareTo(node.key) > 0) {
return getNode(node.right, key);
} else {
return node;
}
}
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
// 不存在该键值对，无法修改，抛出异常
throw new IllegalArgumentException(key + " does not exist!");
} else {
// 存在键值对，直接更新值
node.value = newValue;
}
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
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;
}
}
}
底层为链表的映射
public class LinkedListMap<K, V> implements Map<K, V> {
// 虚拟头节点
private Node dummyHead;
private int size;
public LinkedListMap() {
dummyHead = new Node(null, null);
}
@Override
public void add(K key, V value) {
Node node = getNode(key);
// 不存在该键值对
if (node == null) {
// 在链表头添加一个节点
dummyHead.next = new Node(key, value, dummyHead.next);
size++;
} else {
// 存在键值对，直接更新值
node.value = value;
}
}
@Override
public V remove(K key) {
Node prevNode = dummyHead;
while (prevNode.next != null) {
Node delNode = prevNode.next;
if (delNode.key.equals(key)) {
prevNode.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;
} else {
prevNode = prevNode.next;
}
}
return null;
}
@Override
public boolean contains(K key) {
return getNode(key) != null;
}
@Override
public V get(K key) {
Node curNode = getNode(key);
return curNode == null ? null : curNode.value;
}
/**
* 获取当前 KEY 对应的 Node
*/
private Node getNode(K key) {
Node curNode = dummyHead.next;
while (curNode != null) {
if (curNode.key.equals(key)) {
return curNode;
}
curNode = curNode.next;
}
return null;
}
@Override
public void set(K key, V newValue) {
Node curNode = getNode(key);
if (curNode == null) {
// 不存在该键值对，无法修改，抛出异常
throw new IllegalArgumentException(key + " does not exist!");
} else {
// 存在键值对，直接更新值
curNode.value = newValue;
}
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("LinkedListMap: ");
for (Node node = dummyHead.next; node != null; node = node.next) {
res.append(node + "->");
}
res.append("NULL");
return res.toString();
}
private class Node {
public K key;
public V value;
public Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
public Node(K key, V value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
@Override
public String toString() {
return key.toString() + " : " + value.toString();
}
}
}
时间复杂度分析
O(logn) 级别的复杂度比 O(n) 级别的要快很多。
LinkedListMap 的时间复杂度分析
void add(K key, V value) ， O(n) 级别
V remove(K key) ， O(n) 级别
boolean contains(K key) ， O(n) 级别
BSTMap 的时间复杂度分析
void add(K key, V value) ， O(logn) 级别
V remove(K key) ， O(logn) 级别
boolean contains(K key) ， O(logn) 级别
BSTMap 和 LinkedListMap 的性能比较
public class MapMain {
public static void main(String[] args) {
String fileName = "F:\\java_projects\\data_structure\\Map\\src\\pride-and-prejudice.txt";
Map<String,Integer> linkedListMap = new LinkedListMap<>();
BSTMap<String, Integer> bstMap = new BSTMap<>();
System.out.println("linkedListMap need time = " + testMap(linkedListMap, fileName));
System.out.println("pride show num of times = " + linkedListMap.get("pride"));
System.out.println();
System.out.println("bstMap need time = " + testMap(bstMap, fileName));
System.out.println("pride show num of times = " + bstMap.get("pride"));
System.out.println();
/**
* 测试映射的运行时间
*/
private static double testMap(Map<String,Integer> map, String fileName) {
long startTime = System.nanoTime();
ArrayList<String> words = new ArrayList<>();
boolean isSuccesss = FileOperation.readFile(fileName, words);
if (isSuccesss) {
System.out.println("Pride and Prejudice Total words : " + words.size());
for (String word : words) {
if (map.contains(word)) {
map.set(word, map.get(word) + 1);
} else {
map.add(word,1);
}
}
System.out.println("Pride and Prejudice Total different words : " + map.getSize());
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
}
运行结果：
Pride and Prejudice Total words : 125901
Pride and Prejudice Total different words : 6530
linkedListMap need time = 19.359294327
pride show num of times = 53
Pride and Prejudice Total words : 125901
Pride and Prejudice Total different words : 6530
bstMap need time = 0.171941341
pride show num of times = 53
总结：BSTMap 的性能比 LinkedListMap 好很多，因些 BSTMap 是 O(logn) 级别的，LinkedListMap 是 O(n) 级别的。
LeetCode 的题目解答
350.两个数组的交集II
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
解题代码如下：
public static int[] intersect(int[] nums1, int[] nums2) {
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
// 将第一个数组的数据放到 Map 中
for (int i : nums1) {
if (treeMap.containsKey(i)) {
// 存在，数量加1
treeMap.put(i, treeMap.get(i) + 1);
} else {
// 不存在，数量设为1
treeMap.put(i, 1);
}
}
ArrayList<Integer> list = new ArrayList<>();
for (int i : nums2) {
if (treeMap.containsKey(i)) {
list.add(i);
// 如果包含了元素，移除元素
treeMap.put(i, treeMap.get(i) - 1);
// 元素的数量为0，移除键值对
if (treeMap.get(i) == 0) {
treeMap.remove(i);
}
}
}
// 把交集数据放到数组里面并返回
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}