纯数据结构Java实现(5/11)(Set&Map)
- 2019 年 10 月 3 日
- 筆記
纯数据结构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。
