纯数据结构Java实现(5/11)(Set&Map)
Set 和 Map 都是抽象或者高级数据结构，至于底层是采用树还是散列则根据需要而定。
- 可以细想一下 TreeMap/HashMap, TreeSet/HashSet 的区别即可
- 只定义操作接口(操作一致)，不管具体的实现，所以即便底层是 BST 亦可(只是效率不高)
(我还是直说了吧，如果不要求有序，尽量用 Hash 实现的吧)
集合(Set)
二分搜索树不存放重复元素，所以 BST 就是一个很好的用于实现集合的底层结构
常见应用
其实主要应用就一个: 去重。
比如把 ArrayList 里面的元素经过一个循环，然后放入 set 中查看不重复的元素有多少。
基于BST底层实现
具体实现，可以简单的包装一下 BST:
//先定义好接口
public interface Set<E> {
void add(E e);
void remove(E e);
boolean contains(E e);
int getSize();
boolean isEmpty();
}
//然后包装 BST 这个类
public class BSTSet<E extends Comparable<E>> implements Set<E> {
private BST<E> bst;
//构造函数
public BSTSet() {
bst = new BST<>();
}
@Override
public void add(E e) {
bst.add(e);
}
@Override
public void remove(E e) {
bst.remove(e);
}
@Override
public boolean contains(E e) {
return bst.contains(e);
}
@Override
public int getSize() {
return bst.getSize();
}
@Override
public boolean isEmpty() {
return bst.isEmpty();
}
}
可以看到其实就是封装了 BST 。
基于链表底层实现
和BST一样都是动态数据结构，链表实现SET有优势么？
简单比较:
- 链表中的元素，并不强制要求存储的时候要求元素有序
- 链表的 Node 内部类定义更加简单
因为链表本身不是完全支持 set 的相关操作，所以实现的时候，还是要做一些额外的处理，比如需要先确认一下容器内不存在相关元素再添加。
import linkedlist.LinkedList1;
public class LinkedListSet<E> implements Set<E> {
private LinkedList1<E> list;
public LinkedListSet() {
list = new LinkedList1<>();
}
@Override
public void add(E e) {
//不存在才添加
if (!list.contains(e)) {
list.addFirst(e); //O(1)，因为有头指针
}
}
@Override
public void remove(E e) {
list.removeElem(e);
}
@Override
public boolean contains(E e) {
return list.contains(e);
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("{ ");
res.append(list.toString());
res.append("} ");
return res.toString();
}
public static void main(String[] args) {
LinkedListSet<Integer> set = new LinkedListSet<>();
//添加一些元素 2, 3, 2, 5
set.add(2);
set.add(3);
set.add(2);
set.add(5);
set.add(5);
System.out.println(set); //{ 5->3->2->null}
}
}
当然也有基于 Hash 实现的，类似的也是这些接口。
复杂度分析
初步分析，主要差距应该在 查找是否存在 上
基于链表的是需要查找 O(n)，发现不存在了，才添加；而BST的版本则是 O(logN) 的效率。
即增加、删除、查找上，链表实现的都会慢于树实现的。
最差的情况，对数级别也可能会退化为线性的，比如本来有序的序列创建的 BST 集合实现:
- 准确来说 O(高度)，因为高度可能为 logN 或者 N。(别拿近乎有序的序列去创建BST)
更好的实现应该用自平衡的树，比如AVL或者红黑树，比如 java.util.TreeSet 就是用的红黑树实现。(不会出现退化现象，自己可以维护动态平衡)
但是所有的能力都有机制支撑，也就有相应的维护成本。
有序问题比较
基于链表的集合其实是无序的(底层不维护存储顺序)，存储的顺序和插入顺序相关
而基于 BST，AVL，RBTree 等 搜索树结构的集合则是有序集合，它会自动维护存储的顺序，和插入顺序无关。
无序集合就没用优势么？Hash表就是实现无序集合的非常好的方式。(支持随机存取，效率非常高)
- 基于搜索树实现: 有序集合中的元素具有顺序性
- 基于哈希表实现: 无序集合中的元素没有顺序性
一般认为基于搜索树的集合能力更大，但是时间效率不如hash表的实现。
映射(Map)
映射可能有多种，不过这里更多的关注的是1-1映射。有时候称为 Map，有时候称为字典，说白了，就是可以根据键快速存取值的一种结构。
(各种语言称呼不同)
底层实现: 实际上，映射(map)也是一个高层数据结构，所以底层实现也可以有多种实现。例如也可以用链表，BST去实现，结构大致如下:
// BST 实现
class Node {
K key;
V value;
Node left;
Node right;
}
// 链表实现
class Node {
K key;
V value;
Node next;
}
和上面实现的 set 基本类似，也就是说 set 可以看做一种特殊的 map；map 也可以看做特殊的 set。(但是一般更多的认为，把 set 视为一种特殊的 Map，即 Map<K, null>)
接口定义
一般 map 都具有下列基本的操作，代码如下:
public interface Map<K, V> {
void add(K key, V value);
V remove(K key);
int getSize();
boolean isEmpty();
boolean contains(K key);
V get(K key);
void set(K key, V newValue);
}
特别注意一下，这个接口支持两个泛型参数。
(常见数据结构的 5 种操作，这里一共有7种)
链表底层实现
内部封装一个链表时，此时因为 Node 已经改变，所以不能直接复用 LinkedList （重新定义 Node）
大概具体实现如下:
package map;
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, V value) {
this(key, value, null);
}
public Node() {
this(null, null, null);
}
@Override
public String toString() {
return key.toString() + ":" + value.toString();
}
}
//成员 (和单链表一样)
private int size;
private Node dummyHead;
public LinkedListMap() {
dummyHead = new Node(); //用户并不清楚 dummyNode 的存在
size = 0;
}
//私有函数 (拿到 key 所对应的 Node)
// contains 要用到
// 拿到 key 所对应的 value
private Node getNode(K key) {
//遍历，返回 key 所对应的 Node
Node cur = dummyHead.next;
while(cur != null) {
if(cur.key.equals(key)) {
return cur;
} else {
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 int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void add(K key, V value) {
//添加新的节点 (key 必须唯一)
if(!contains(key)) {
//直接在链表头部添加
dummyHead.next = new Node(key, value, dummyHead.next);
//特别注意: size++
size++;
} else {
//存在了就抛出异常 (你也可以去更新)
throw new IllegalArgumentException("要新增的 Key 已经存在了");
}
}
@Override
public void set(K key, V newValue) {
//找到 key 然后更新
Node node = getNode(key);
if(node != null) {
node.value = newValue;
} else {
//要更新的 key 不存在，抛出异常
throw new IllegalArgumentException("要更新的 Key 不已经");
}
}
@Override
public V remove(K key) {
//类似单链表里面删除 elem 逻辑
//从 dummyHead 开始找到相应节点的前一个节点
Node prev = dummyHead; //这里的 prev 其实代表的是找到的节点前一个节点
while(prev.next != null) {
if(prev.next.key.equals(key)) {
break;
}
prev = prev.next;
}
//找到了 break 的，还是自然结束的?
if(prev.next != null) {
//表明是找到的，break出来的
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;
}
//自然结束的，说明没有找到要删除的元素
return null;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("{");
for(Node curr = dummyHead.next; curr != null; curr = curr.next) {
res.append(curr.key + ":\"" + curr.value + "\"");
if(curr.next != null) {
res.append(", ");
}
}
res.append("}");
return res.toString();
}
}
简单测试如下:
public static void main(String[] args) {
Map<Integer, String> map = new LinkedListMap<>();
//放入一些元素
map.add(1, "one");
map.add(2, "two");
map.add(3, "three");
System.out.println(map); //{3:"three", 2:"two", 1:"one"}，和添加顺序一致
System.out.println(map.contains(3)); //true
System.out.println(map.getSize()); //3
System.out.println(map.get(1)); //one
}
BST底层实现
基于 bst 的 map 也不能直接复用 bst 的实现，这里要重新定义 Node 结构
且 Key 必须是可以比较的。
大致实现如下: (其中注意很多内部的辅助方法)
public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
//定义 Node
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 = 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;
}
// 其他函数和 BST 的实现保持一致
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
//返回操作后的子树 (根节点)
private Node add(Node root, K key, V value) {
if(root == null) {
//找到了相应插入的位置，那么返回 (上层调用会接收这个子树)
size++;
return new Node(key, value);
}
//找到相应需要插入的位置
if(key.compareTo(root.key) < 0) {
//左子树上递归查找相关位置
root.left = add(root.left, key, value);
} else if(key.compareTo(root.key) > 0) {
//右子树上递归查找需要插入的位置
root.right = add(root.right, key, value);
} else {
//已经存在了？抛异常，还是更新
throw new IllegalArgumentException("要添加的 Key 已经存在了");
}
return root; //返回操作完毕后的子树给上级 (这棵子树的 right 或者 left 已经添加了新元素)
}
//查询方法，一般需要借助，找到该节点的 私有方法
//返回 key 所在的节点
private Node getNode(Node root, K key) {
//以当前节点作为 root 开始查询
//还是用递归的写法
if(root == null) {
// 没有找到
return null;
}
if(key.compareTo(root.key) == 0) {
//找到了
return root;
} else if (key.compareTo(root.key) < 0) {
//在左子树上去找
return getNode(root.left, key);//返回从 root.left 这颗子树上的节点
} else {
return getNode(root.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 ? node.value : null;
}
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if(node != null) {
//存在，就更新
node.value = newValue;
} else {
throw new IllegalArgumentException("要更新的 Key 不存在");
}
}
//删除操作比较复杂 (这边需要使用融合技术，即找前驱或者后继元素)
//先写4个辅助函数 (找前驱的 getMax, 找后继的 getMin )
// 删除 max 并返回相应节点的 removeMax 或者 删除 min 并返回相应节点的 removeMin
private Node getMin(Node root) {
if(root.left == null) {
return root;
}
//其他情况一直在左子树上查找
return getMin(root.left);
}
//删除最小元素，然后返回这个子树 (根节点)
private Node removeMin(Node root) {
//最小元素一定在左子树上，让 root 的左子树接收即可
if(root.left == null) {
//左子树空了，这个时候需要把右子树嫁接到父节点上 (也就是返回给上级调用的 left)
//此时最小值就是当前这个节点 root
Node rightNode = root.right; //可能为空
root.right = null; //把当前这个节点置空
size--;
return rightNode;
}
//左子树不空，继续找
root.left = removeMin(root.left);
return root;
}
private Node getMax(Node root){
if(root.right == null) {
return root;
}
//否咋一直找右子树
return getMax(root.right);
}
//删除最大元素，然后返回这个子树 (根节点)
private Node removeMax(Node root) {
if(root.right == null) {
//此时 root 就是最大节点了
//把左子树嫁接到父节点吧 (即返回给上层调用)
Node leftNode = root.left; //可能为 null，但返回给上层调用的 right
root.left = null;
size--;
return leftNode;
}
//否则接续找
root = root.right;
return root;
}
//辅助函数写完，再来写真正的删除任意 key 的情况
@Override
public V remove(K key) {
Node node = getNode(root, key);
if(node != null) {
//存在采取删除
root = remove(key, root);
return node.value;
}
return null; //不存在，则删除不了，应该抛异常的，这里就返回 null 算了
}
//返回操作完毕的相关子树 (根节点)
private Node remove(K key, Node root) {
//要操作的子树为空的时候，表明已经到了树的叶子下了
if(root == null) {
return null;
}
//其他情况，则递归的在 相关左右子树上进行相关删除操作 (返回操作后的子树)
if(key.compareTo(root.key) < 0) {
//左子树上删除，然后子树给 root.left
root.left = remove(key, root.left);
} else if(key.compareTo(root.key) > 0) {
//右子树上删除，然后返回结果给 root.right
root.right = remove(key, root.right);
} else {
//找了要删除的节点 compare 相等的情况
// 这里还是要分情况处理一下: 左子树为空或者右子树为空，嫁接另一半子树
//如果左右子树都不为空，那么久需要处理融合问题
//简单的情况: 有一边子树空的情况
if(root.left == null) {
//嫁接右子树部分即可 (意思就是返回给上一级，自然有递归接收)
Node rightNode = root.right;
root.right = null;
size--;
return rightNode;
}
if(root.right == null) {
//嫁接左子树部分即可
Node leftNode = root.left;
root.left = null;
size--;
return leftNode;
}
//先找后继，即右子树上查找最接近的节点 (右子树上查找最小)
Node subcessorNode = getMin(root.right); //替代当前节点
subcessorNode.right = removeMin(root.right); //返回右子树操作后的子树 (根节点)
subcessorNode.left = root.left;
//置空这个要删除的节点
root.left = root.right = null;
return subcessorNode;
}
return root;
}
private void inOrder(Node root) {
//实现一个中序遍历方法
if(root == null) {
//以 root 为根的这颗子树空的, 不必打印直接返回
return;
}
inOrder(root.left);
System.out.print(root.key + ":" + root.value + " ");
inOrder(root.right);
}
@Override
public String toString() {
inOrder(root);
System.out.println();
return super.toString();
}
}
简单测试一下:
public static void main(String[] args) {
BSTMap<Integer, String> map = new BSTMap<>();
map.add(2, "two");
map.add(1, "one");
map.add(3, "three");
map.add(5, "five");
System.out.println(map.getSize());
System.out.println(map.contains(3));
System.out.println(map);
}
打印输入结果:
4
true
1:one 2:two 3:three 5:five
map.BSTMap@1a407d53
复杂度分析
还是增删查改中，只要涉及查找，比如先看看该元素是否存在的情况，那么链表就慢了。O(树高) VS O(n) 的差别，但是树高也可能会退化到 O(n)。(平均情况还是 O(logN))
同样的，要避免最差的情况，还是要借助 AVL 让树更加平衡一些。(减小高度)
有序性问题
有序和无序还是和其底层有关。
如果基于BST的底层实现，那么它是有能力维护存储顺序的(和你插入顺序无关)。
比较总结
一般认为 Map 和 Set 的底层实现并没有多大的区别。(一般可能都会用树，具体说就是红黑树去实现)
也就是说，基于 Map 的底层实现，更容易包装出 Set 的实现。(默认把Value设置null即可，此时去掉 get 和 set 方法)
Java 中 TreeMap, TreeSet 底层就是基于 AVL 实现的(实际上是红黑树);而HashMap和HashSet底层则是基于哈希表实现的。(但是使用的时候根本不必关心，因为上层接口是一致的)
BTW: 很多练习题中有几个技巧，查询到已经存在的，就从Set/Map中删除。(不多解释了)
不多言了，还是把代码仓库贴一下吧 gayhub。