当使用Hash实现时，无序。
使用Tree实现时，有序。

3.Set and Map （集合与映射）

// 都可以使用链表和树实现，只要设置 Node 中增加key, Value 即可

Set：不允许出现重复元素

  • set实际上是一个接口， 实现了 Collection
  • image.png

主要有以下几个方法：

  1. // 获取元素个数
  2. int size()
  3. // 查看 Set 是否为空
  4. boolean isEmpty()
  5. // 查看 Set 是否包含元素
  6. boolean contains(Object o)
  7. // 添加元素
  8. void add(E e)
  9. // 删除元素
  10. void  remove(Object o)

HashSet实现：

public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable

  1. Set<Integer> set = new HashSet<>();// 创建Set，为 AbstractSet<E> 的子类
  2. private transient HashMap<E,Object> map; // 底层由HashMap实现

LinkedList实现：

  1. // 直接调用了 链表自己实现的方法
  2. public class LinkedListSet <E extends Comparable<E>> implements Set<E>{
  3.     private LinkedList<E> list;
  4.     public LinkedListSet(){
  5.         list = null;
  6.     }
  7.     // 获取元素个数
  8.     public int size(){
  9.         return list.getSize();
  10.     }
  11.     // 查看 Set 是否为空
  12.     public boolean isEmpty(){
  13.         return list.isEmpty();
  14.     }
  15.     // 查看 Set 是否包含元素
  16.     public boolean contains(E value){
  17.         return list.contains(value) != null;
  18.     }
  19.     // 添加元素
  20.     public void add(E e){
  21.         if(!list.contains(e)){
  22.             list.addFirst(e);
  23.         }
  24.     }
  25.     // 删除元素
  26.   public void remove(E e){
  27.         remove(e);
  28.   }
  29. }

BST实现：

  1. // 对于BST实现的 Set
  2. // 由于只有一个val, 所以实际操作和BST 相同
  3. public class BSTSet <E extends Comparable<E>> implements Set<E>{
  4.     private BSTSet<E> bstset;
  5.     public BSTSet(){
  6.         bstset = null;
  7.     }
  8.      // 获取元素个数
  9.     public int size(){
  10.         return bstset.getSize();
  11.     }
  12.     // 查看 Set 是否为空
  13.     public boolean isEmpty(){
  14.         return bstset.isEmpty();
  15.     }
  16.     // 查看 Set 是否包含元素
  17.     public boolean contains(E value){
  18.         return bst.contains(value) != null;
  19.     }
  20.     // 添加元素
  21.     public void add(E e){
  22.         if(!bst.contains(e)){
  23.             bst.add(e);
  24.         }
  25.     }
  26.     // 删除元素
  27.   public void remove(E e){
  28.         bst.remove(e);
  29.   }
  30. }

image.png

Map(键值对)：

Map实际上也是接口：
image.png

  1. Map<K,V>;
  2. // 主要的方法
  3. // 添加元素
  4. void add(K key , V value);
  5. V remove(K key);// 删除 对应 key
  6. boolean contains(K key); // 查看是否存在 key
  7. V get(K key);// 获取 key对应值
  8. void set(K key, V newValue); // 更新值
  9. int getSize();
  10. boolean isEmpty();

LinkedList 实现 Map

  1. // 在 Node 中分别存入 Map, Value
  2. public class LinkedList<K,V> implements Map<K,V>{
  3.     private class Node{
  4.         public K key;
  5.         public V value;
  6.         public Node next;
  8.         public Node(K key, V value, Node next){
  9.             this.key = key;
  10.             this.value = value;
  11.             this.next = next;
  12.         }
  14.         // 放入值可为 null, 但是需要有一个 key 对应
  15.         public Node(K key){
  16.             this(key, null, null);
  17.         }   
  18.     }
  20.     private Node dummyHead;
  21.     private int size;
  24.     public LinkedListMap() {
  25.         dummyHead = new Node(null,null,null);
  26.         size = 0;
  27.     }
  29.     @Override
  30.     public int getSize(){
  31.         return size;
  32.     }
  34.     @Override
  35.        public boolean isEmpty(){
  36.         return size == 0;
  37.     }
  40.     public Node getNode(K key){
  41.         Node res = dummyHead.next;
  42.         while(res!=null){
  43.             if(res.key.equals(key)){
  44.                 return res;
  45.             }
  46.             res = res.next;
  47.         }        
  48.         return null; 
  49.     }
  52.     @Override
  53.     public void add(K key, V val){
  54.         // 如果不存在 key, 直接加到头部(直接查找是否有对应Node)
  55.         // 如果存在，改变value
  56.         Node res = getNode(key);
  57.         if(res == null){
  58.             dummyHead.next = new Node(key, value, dummyHead.next);
  59.             size++;
  60.         }else{
  61.             res.value = val;
  62.         }   
  63.     }
  65.     @Override
  66.     public void set(K key, V val){
  67.         Node node = getNode(key);
  68.         if(node == null){
  69.             throw new IllegalArgumentException("map don't contains key");
  70.         }
  71.         node.value = val;
  72.     }
  74.     @Override
  75.     public V remove(K key){
  76.         Node node = getNode(key);
  77.         if(node == null){
  78.             throw new IllegalArgumentException("map don't contains key");
  79.         }
  80.         Node head = dummyhead;
  81.         for(int i = 0; i < size; i++){
  82.             if(head.next.key.equals(key)){
  83.                 break;
  84.             }
  85.             head = head.next;
  86.         }
  87.         head.next = node.next;
  88.         node.next = null;
  89.         size--;
  90.         return node.value;
  91.     }
  93.     @Override 
  94.     public boolean contains(K key){
  95.         return getNode(key) != null;
  96.     }
  98.     @Override
  99.     public V get(K key){
  100.         Node node = getNode(key);
  101.         if(node == null){
  102.             throw new IllegalArgumentException("map don't contains key");
  103.         }
  104.         return node == null ? null : node.value;
  105.     }
  106. }

BST(二分搜索树)实现Map

  1. // 根据 key 存在排序
  2. // 二分搜索树，左子节点val < 父节点 val < 右子节点 val
  3. public class BSTMap <K extend Comparable<K>, V> implements Map<K ,V>{
  4.     private class Node{
  5.         public K key;
  6.         public V value;
  7.         public Node left, right;
  9.         public Node(K key, V value. Node left, Node right){
  10.             this.key = key;
  11.             this.value = value;
  12.             this.left = left;
  13.             this.left = right;
  14.         }
  16.         // 放入值可为 null, 但是需要有一个 key 对应
  17.         public Node(K key){
  18.             this(key, null, null, null);
  19.         }   
  20.     }
  22.     private Node root;
  23.     private int size;
  25.     public BSTMap(){
  26.         root  = null;
  27.         size = 0;
  28.     }
  30.     @Override
  31.     public int getSize(){
  32.         return size;
  33.     }
  35.     @Override
  36.     public boolean isEmpty(){
  37.         return size == 0;
  38.     }
  40.     @Override
  41.     public V get(K key){
  42.         Node res = getNode(key);
  43.         return res == null ? null : res.value;
  44.     }
  46.     @Override
  47.     public boolean contains(K key){
  48.         return getNode(key) != null;
  49.     }
  51.     // 使用递归方式
  52.     public Node getNode(K key){
  53.         return getNode(root, key);
  54.     }
  56.     private Node getNode(Node node, K key){
  57.         if(node == null){
  58.             return null;
  59.         }
  60.         if(node.key.compareTo(key) < 0){
  61.             return getNode(node.left, key);
  62.         }else if(node.key.compareTo(key) > 0){
  63.             return getNode(node.right, key);
  64.         }
  65.         return node;
  66.     }
  68.     @Override
  69.     public void add(K key, V value){
  70.         Node res = getNode(key);
  71.         if(res == null){
  72.             root = add(root, key, value);
  73.             size++;
  74.         }else{
  75.             res.value = value;
  76.         }
  77.     }
  79.     private Node add(Node node, K key, V value){
  80.         if(node == null){
  81.             return new Node(key, value, null, null);
  82.         }
  84.         if(node.key.compareTo(key) > 0){
  85.             node.right = add(node.right, key, value);
  86.         }else{
  87.             node.left = add(node.left, key, value);
  88.         }
  89.         return node;
  90.     }
  92.     @Override
  93.     // 二分搜索树，删除某一结点后，采用前缀或者后缀
  94.     // 前缀， 把左子树中最大值交换
  95.     // 后缀，把右子树中最小值交换
  96.     public V remove(K key){
  97.            Node res = getNode(key);
  98.         if(res == null){
  99.             throw new IllegalArgumentException("map don't contains key");
  100.         }
  101.         root = remove(root, key);
  102.         return res.value;
  103.     }
  105.     // 获取Node下 最大值
  106.     // 当仅有root 节点的时候，最大值为 root
  108.     public Node findMax(Node node){
  109.         // 获取左子树中最右那个Node
  110.         Node res = node;
  111.         while(res.right != null){
  112.             res = res.right;
  113.         }
  114.         return res;
  115.     }
  117.     // 删除Node下最大值,即删除最右的子节点
  118.     public Node removeMax(Node node){
  119.         Node res = node;
  120.         while(node.right != null){
  121.             node = node.right;
  122.         }
  123.         node = null;
  124.         size--;
  125.         return node;
  126.     }
  128.     // 若节点是否为叶子节点
  129.     // 若非叶子节点，这里使用前缀法，获取左子树中最大值，进行交换
  130.     private Node remove(Node node, K key){
  131.         if(node.key.compare(key) < 0){
  132.             node.left = remove(node.left, key);
  133.             return node;
  134.         }else if(node.key.compareTo(key) > 0){
  135.             node.right = remove(node.right, key);
  136.                return node;
  137.         }else{
  138.              // 为叶子节点
  139.             if(node.left == null){
  140.                 Node accessor = node.right;
  141.                    node.right = null;
  142.                 size--;
  143.                 return accessor;
  144.             }else if(node.right == null){
  145.                 Node accessor = node.left;
  146.                 node.left = null;
  147.                 size--;
  148.                 return accessor;
  149.             }else{
  150.                 // 左右子节点均存在
  151.                 Node accessor = findMax(node);
  152.                 accessor.right = node.right;
  153.                 accessor.left = removeMax(node.left);
  154.                 node.left = null;
  155.                 node.right = null;
  156.                 return accessor;
  157.             }                                  
  158.         }  
  159.     }
  161.     @Override
  162.     public void set(K key, V newValue){
  163.         if(!contains(key)){
  164.             throw new IllegalArgumentException("map don't contains key");
  165.         }
  166.        Node res = getNode(key);
  167.        res.value = newValue;
  168.     }
  172. }

image.png