純數據結構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。
