Map

Map接口

public interface Map<K,V> {
    void add(K key,V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key,V value);
    int getSize();
    boolean isEmpty();
}

链表实现

// 平均时间复杂度O(n)
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){
      this(key,null,null);
    }
    public Node() {
      this(null,null,null);
    }
    @Override
    public String toString() {
      return key.toString() + ":" + value.toString();
    }
  }

  private Node dummyHead;
  private int size;

  public LinkedListMap() {
    dummyHead = new Node();
    size = 0;
  }

  @Override 
  public int getSize() {
    return size;
  }
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
  private Node getNode(K key) {
    Node cur = dummyHead.next;
    while(cur != null) {
      if(cur.key.equals(key)){
        return cur;
      }
      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 void add(K key, V value) {
    Node node = getNode(key);
    if(node == null) {
      // 头插法
      dummyHead.next = new Node(key,value,dummyHead.next);
      size ++;
    } else {
      node.value = value;
    }
  }
  @Override
  public void set(K key, V value) {
    Node node = getNode(key);
    if(node == null) {
      throw new IllegalArgumentException(key + "doesn't exist !");
    }
    node.value = value;
  }
  @Override
  public V remove(Key key) {
    Node prev = dummyHead;
    // 寻找删除节点的前驱
    while(prev.next != null) {
      if(prev.next.key.equals(key)){
        break;
      }
      prev = prev.next;
    }
    if(prev.next != null) {
      Node delNode = prev.next;
      prev.next = delNode.next;
      delNode.next = null;
      return delNode.value;
    }
    return null;
  }
}

二分搜索树实现Map

// 平均时间复杂度O（logn）
public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
  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 = null;
      right = null;
    }
  }

  private Node root;
  private int size;

  public BSTMap() {
    root = null;
    size = 0;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public boolean contains(K key) {
    return getNode(root, key) != null;
  }

  // 添加元素
  @Override
  public void add(K key, V value) {
    root = add(root, key, value);
  }

  // 向以node为根的二分搜索树种插入元素E
  private Node add(Node node, K key, V value) {
    // 当我们递归到null的时候就一定要创建一个节点
    if (node == null) {
      size++;
      return new Node(key, value);
    }
    if (key.compareTo(node.key) < 0) {
      node.left = add(node.left, key, value);
    } else if (key.compareTo(node.key) > 0) {
      node.right = add(node.right, key, value);
    } else {
      node.value = value;
    }
    return node;
  }

  private Node getNode(Node node, K key) {
    if (node == null) {
      return null;
    }
    if (key.compareTo(node.key) < 0) {
      return getNode(node.left, key);
    } else if (key.compareTo(node.key) > 0) {
      return getNode(node.right, key);
    } else {
      return node;
    }
  }

  @Override
  public V get(K key) {
    Node node = getNode(root, key);
    return node == null ? null : node.value;
  }

  @Override
  public void set(K key, V value) {
    Node node = getNode(root, key);
    if (node == null) {
      throw new IllegalArgumentException(key + "doesn't exist !");
    }
    node.value = value;
  }

  public V remove(K key) {
    Node node = getNode(root, key);
    if (node != null) {
      root = remove(root, key);
      return node.value;
    }
    return null;
  }

  private Node remove(Node node, K key) {
    if (node == null) {
      return null;
    }
    if (key.compareTo(node.key) < 0) {
      node.left = remove(node.left, key);
      return node;
    } else if (key.compareTo(node.key) > 0) {
      node.right = remove(node.right, key);
      return node;
    } else {
      // 3种情况
      if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
      }
      if (node.right == null) {
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
      }
      // 在BST上有实现的方法
      Node successor = minimum(node.right);
      // 这里我们进行了删除size进行了减操作
      successor.right = removeMin(node.right);
      successor.left = node.left;
      node.left = node.right = null;
      return successor;
    }
  }
}