摘要

映射的数据结构可以用链表、AVL 树或者红黑树中的任何一种来实现,对外实现对映射序列中元素的增、删、改和查等操作。所以通晓链表、AVL 树或者红黑树的底层实现逻辑之后,在顶层实现其他的数据存储序列都能很快的切入和掌握。

映射,英文为 Map,在有些编程语言中也叫做字典(dictionary)。

Map中存储着一对对的 key-value 键值对,每一个 key 在 Map 中是唯一的。Map 可以直接使用之前学习的链表、AVL 树和红黑树等来实现。

先定义一下 Map 的接口

public interface Map<K, V> {
   
     
  // 元素数量
	int size();
  // Map 是否是空
	boolean isEmpty();
  // 加入 key-value 键值对
	V put(K key, V value);
  // 获取为 key 的 K-V 键值对
	V get(K key);
  // 移除为 key 的 K-V键值对
	V remove(K key);
  // Map 中是否包含 key 值
	boolean containsKey(K key);
  // Map 中是否包含 value 值
	boolean containsValue(V value);
}

这里使用红黑树实现映射结构。不熟悉红黑树的可以看前几期介绍红黑树的文章,这里不再详细介绍。

在红黑树中定义的范型是 E,在 Map 中需要更改为 <K, V>。即将红黑树中的 Node<E> 都更改为 Node<K, V>

定义的接口里面,前面 6 个函数直接使用红黑树的函数来实现。最后的 containsValue(V:) 函数需要提出来单独实现。

在Map 中的每个 key 都是唯一确定的,并且在红黑树中的 K-V 键值对都是以 key 来比较调整的。所以若想看 Map 是否包含某一个 value 值,就需要去遍历红黑树来实现。

可以使用广度搜索的方式来遍历红黑树,实现广度搜索的底层逻辑就是遍历队列:

public boolean containsValue(V value) {
   
     
  if (root == null) return false;
	// 创建队列,队列的特性:先入先出(FIFO)
  Queue<Node<K, V>> queue = new LinkedList<>();
  // 先入队 root 节点
  queue.offer(root);
  // 循环条件
  while (!queue.isEmpty()) {
   
     
    // 出队节点,并比较 value 值
    Node<K, V> node = queue.poll();
    if (valEquals(value, node.value)) return true;
		
    // 分别入队左右节点
    if (node.left != null) {
   
     
      queue.offer(node.left);
    }
    if (node.right != null) {
   
     
      queue.offer(node.right);
    }
  }
  return false;
}

到这里,已经实现完 Map 的所有函数,熟悉红黑树的结构,就可以很快实现 Map 结构。

使用红黑树实现的 Map,有两个特点

1、 Key必须具备可比较性;
2、 元素的分布是有顺序的;

接下来简单提一下在 JAVA 中如何实现比较两个元素的,这里就是比较两个 key 。在 JAVA 中导入比较的标准工具库(import java.util.Comparator),然后在构造函数的地方定义可以穿入比较对象的参数:

// K 是范型
TreeMap(Comparator<K> comparator) {
   
     
  this.comparator = comparator;
}

下面就可以使用传递进来的 comparator 来实现两个 key 的比较:

// 返回的是 int 值,若 -1, e1 < e2; 0, e1 == e2; 1, e1 > e2
private int compare(K e1, K e2) {
   
     
  if (comparator != null) return comparator.compare(e1, e2);

  return ((Comparable<K>)e1).compareTo(e2);
 }

这个比较方式最大的好处就是可以在外部来定义 comparator 的比较规则。比如在外部可以这样调用:

new Comparator<Int>() {
   
     
		@Override
		public int compare(Int o1, Int o2) {
   
     
				return o2 - o1;
		}
}

上面代码就是创建一个 comparator 对象,在对象中定义比较的规则,即若 return 的值是 1,则是 o2 > o1,和上面的 k 比较恰好相反。