编程是一种艺术

因为热爱，所以不辞幸苦

切换

07-映射

nobility 发布于 2020-04-16 1349 次阅读

映射

存储键值对数据的容器，即一个key对应一个value，并且键是唯一的
- 有序映射：在集合中元素存储是有顺序的，比如基于二分搜索树的集合
- 无序映射：在集合中元素存储是无顺序的，比如基于哈希表实现的集合
可根据键寻找到值，其实就是将原来只能存储一个数据的节点扩充，可以存储为两个数据（一个是key，一个是value）即可
由于集合的实现方式不仅是一种，所以写成接口的形式，方便多种实现

/**
 * @InterfaceName: Map
 * @Description: 自定义映射接口
 */
public interface Map<K, V> {
  /**
   * @MethodName: set
   * @Description: 向映射中添加或修改键值对
   * @Param key: 键
   * @Param value: 值
   * @Return void
   */
  void set(K key, V value);

  /**
   * @MethodName: get
   * @Description: 根据键获取值
   * @Param key: 键
   * @Return V
   */
  V get(K key);

  /**
   * @MethodName: remove
   * @Description: 根据键删除键值对，并返回值
   * @Param k: 键
   * @Return V
   */
  V remove(K key);

  /**
   * @MethodName: contains
   * @Description: 判断该映射中是否包含该键
   * @Param k: 键
   * @Return boolean
   */
  boolean contains(K key);

  /**
   * @MethodName: getSize
   * @Description: 获取映射中的元素个数
   * @Return int
   */
  int getSize();

  /**
   * @MethodName: isEmpty
   * @Description: 判断映射是否为空
   * @Return boolean
   */
  boolean isEmpty();
}

基于二分搜索树实现的映射

由于需要将节点能存储的数据由一个扩充到两个，需要重新实现一下二分搜索树，但是其中的方法可以修改之前二分搜索树的，因为只是对键的操作

由前面的经验，链表中大部分方法中都会用到遍历得到相应的节点信息，所以封装成一个私有方法用来复用

/**
 * @ClassName: BSTMap
 * @Description: 基于二分搜索树的自定义映射
 */
public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
  private class Node {
    Node left, right;  //指向左子树和右子树的指针
    K key; //存储键值对的键
    V value;  //存储键值对的值

    /**
     * @MethodName: Node
     * @Description: 创建节点
     * @Param element: 传入的数据
     */
    public Node(K key, V value) {
      this.key = key;
      this.value = value;
      this.left = null;
      this.right = null;
    }

  }

  private Node root;  //存储根节点
  private int size; //记录树中元素个数

  /**
   * @MethodName: getNode
   * @Description: 根据键和获取在子树中该键所在的节点
   * 由前面的经验，链表中大部分方法中都会用到遍历得到相应的节点信息所以封装成一个私有方法用来复用
   * @Param node: 指定的左树
   * @Param key: 指定的键
   * @Return BSTMap<K, V>.Node
   */
  private Node getNode(Node node, K key) {
    if (node == null) { //若遍历到末端
      return null;  //什么也不做，返回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;  //返回找到的节点
    }
  }

  /**
   * @MethodName: set
   * @Description: 向映射中添加或修改键值对具体实现
   * @Param key: 键
   * @Param value: 值
   * @Return void
   */
  @Override
  public void set(K key, V value) {
    this.root = this.set(root, key, value);
    //将节点添加到以根节点为根的子树中
    //之后根节点指针指向这颗已经插入元素的树
  }

  private Node set(Node node, K key, V value) {
    if (node == null) { //若遍历到树的末端
      this.size++;  //插入元素时将元素个数加1
      return new Node(key, value);
      //返回插入节点的子树，这里子树就是叶子节点，即新节点本身
    }

    if (key.compareTo(node.key) < 0) {
      //若要插入的元素小于当前节点，就应该将该元素插入到左子树中
      node.left = set(node.left, key, value);
      //返回的已插入元素，并以左孩子节点为根的子树
      //之后将该子树挂到当前节点左指针上
    } else if (key.compareTo(node.key) > 0) {
      //若要插入的元素小于当前节点，就应该将该元素插入到右子树中
      node.right = set(node.right, key, value);
      //返回的已插入元素，并以右孩子节点为根的子树
      //之后将该子树挂到当前节点右指针上
    } else { //若要插入元素与当前节点相等
      node.value = value; //修改该节点的键值
    }
    return node;
    //返回以该节点为根的子树
  }

  /**
   * @MethodName: get
   * @Description: 根据键获取值操作具体实现
   * @Param key: 键
   * @Return V
   */
  @Override
  public V get(K key) {
    Node node = this.getNode(this.root, key);  //查找到该键在该树中对应的节点
    return node == null ? null : node.value; //若查找到会返回节点的键值，找不到返回null
  }

  /**
   * @MethodName: minimum
   * @Description: 返回以该节点为根的子树中最小的节点
   * @Param node: 以该节点为根的子树
   * @Return BST<E>.Node
   */
  private Node minimum(Node node) {
    if (node.left == null) { //若该节点左孩子为空，说明已经到达树的末端
      return node;  //该节点就是最小的节点，直接返回该节点即可
    }
    return this.minimum(node.left); //返回以该节点左孩子节点为根的子树中最小的节点
  }

  /**
   * @MethodName: remove
   * @Description: 删除指定以该节点为根的子树中的元素，并返回这颗删除指定元素的子树
   * @Param node: 指定的子树
   * @Param element: 指定的删除元素
   * @Return BST<E>.Node
   */
  private Node remove(Node node, K key) {
    if (node == null) { //若遍历到末端，即空子树，该元素一定不可能在这颗空的子树中
      return null;  //所以什么也不用做直接返回该空节点，返回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 {  //若要删除元素等于当前节点元素，该节点就是要删除节点
      if (node.left == null) {
        //若当前要删除节点没有左子树，则删除当前节点和删除最小节点操作一致
        Node rightNode = node.right;
        node.right = null;
        this.size--;
        return rightNode;
      }
      if (node.right == null) {
        //若当前要删除节点没有右子树，则删除当前节点和删除最大节点操作一致
        Node leftNode = node.left;
        node.left = null;
        this.size--;
        return leftNode;
      }
      //若当前节点既有左子树，又有右子树

      //使用后继
      Node successor = this.minimum(node.right);  //找到后继节点，准备将后继节点替换删除节点
      //后继就是离当前节点元素最近，且比当前元素大的节点（刚刚比当前节点元素大的元素节点）
      //同时也是当前节点的右子树中的最小值
      //successor.right = this.removeMin(node.right); //后继节点右子树指向删除该后继节点的子树
      successor.right = remove(node.right,successor.key); //也可以使用递归调用，来获取删除后继节点的子树，进而减少一个删除最小值的函数
      successor.left = node.left; //后继节点左子树指向原来节点的左子树
      node.left = node.right = null;  //将原来节点与该树脱离关系，方便垃圾回收机制回收
      return successor; //返回删除该元素的子树

      /*
      //使用前驱
      Node precursor = this.maximum(node.left); //找到前驱节点，准备将前驱节点替换删除节点
      //前驱就是离当前节点元素最近，且比当前元素小的节点（刚刚比当前节点元素小的元素节点）
      //同时也是当前节点的左子树中的最大值
      precursor.left = this.removeMax(node.left); //前驱节点左子树指向删除该前驱节点的子树
      precursor.right = node.right; //前驱节点右子树指向原来节点的右子树
      node.left = node.right = null;  //将原来节点与该树脱离关系，方便垃圾回收机制回收
      return precursor; //返回删除该元素的子树
      */
    }
  }

  /**
   * @MethodName: remove
   * @Description: 根据键删除键值对，并返回值操作的具体实现
   * 该方法依赖删除子树中任意节点，删除子树中任意节点依赖删除子树中最小（大）节点
   * 删除子树中最小（大）节点依赖找到最小（大）节点
   * @Param key: 键
   * @Return V
   */
  @Override
  public V remove(K key) {
    Node node = this.getNode(this.root, key); //先获取key对应的节点
    if (node != null) {  //若找到节点
      this.root = this.remove(this.root, key);  //就删除节点
      //删除以根节点为根的子树中的该元素
      //之后将根节点指针指向这颗已经删除该元素的树
      return node.value;  //返回删除节点对应的键值
    }
    return null;  //未找到该节点，就返回null，什么也不做
  }

  /**
   * @MethodName: contains
   * @Description: 判断该映射中是否包含该键操作具体实现
   * @Param key: 键
   * @Return boolean
   */
  @Override
  public boolean contains(K key) {
    return this.getNode(this.root, key) != null; //若找到该节点不会返回空，就会返回true
  }

  /**
   * @MethodName: getSize
   * @Description: 获取映射中的元素个数操作具体实现
   * @Return int
   */
  @Override
  public int getSize() {
    return this.size;
  }

  /**
   * @MethodName: isEmpty
   * @Description: 判断映射是否为空操作具体实现
   * @Return boolean
   */
  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }
}

基于链表实现的映射

由于需要将节点能存储的数据由一个扩充到两个，需要重新实现一下链表，但是其中的方法可以修改之前二分搜索树的，因为只是对键的操作

由前面的经验，链表中大部分方法中都会用到遍历得到相应的节点信息，所以封装成一个私有方法用来复用

/**
 * @ClassName: LinkedListMap
 * @Description: 基于链表结构实现的自定义映射
 */
public class LinkedListMap<K, V> implements Map<K, V> {
  private class Node { //私有的内部类，不希望暴漏给外部使用，使用该类创建节点对象并进行链表的组装
    private K key; //存储键值对的键
    private V value;  //存储键值对的值
    private Node next;  //存储下一个节点

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，指定键值对和下一个节点
     * @Param data: 数据
     * @Param next: 下一个节点
     */
    public Node(K key, V value, Node next) {
      this.key = key;
      this.value = value;
      this.next = next;
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，只指定键值对，下一个节点为null，即最后一个节点
     * @Param data:
     */
    public Node(K key, V value) {
      this(key, value, null);
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，此时键值对和下一个节点都是null，即最后一个节点并且键值对也是null
     */
    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return this.key.toString() + ":" + this.value.toString(); //只打印数据，屏蔽掉节点指针
    }
  }

  private Node dummyHead; //头节点指针，永远指着头（虚拟头）
  private int size; //映射中的元素个数

  /**
   * @MethodName: LinkedListMap
   * @Description: 创建一个空映射
   */
  public LinkedListMap() {
    this.dummyHead = new Node();  //创建链表时创建一个虚拟头节点
    this.size = 0;
  }

  /**
   * @MethodName: getNode
   * @Description: 根据键获取该键所在的节点
   * 由前面的经验，链表中大部分方法中都会用到遍历得到相应的节点信息所以封装成一个私有方法用来复用
   * @Param key:
   * @Return LinkedListMap<K, V>.Node
   */
  private Node getNode(K key) {
    Node cur = this.dummyHead.next; //存储当前节点的指针，从第二个节点开始遍历，跳过虚拟头节点
    while (cur != null) { //若当前节点已经为null，说明当前节点指针已经指到了末尾
      if (key.equals(cur.key)) { //若与用户指定元素相同
        return cur; //返回当前节点
      }
      cur = cur.next; //指针后移
    }
    return null;  //未找到返回null
  }

  /**
   * @MethodName: set
   * @Description: 向映射中添加或修改键值对具体实现
   * @Param key: 键
   * @Param value: 值
   * @Return void
   */
  @Override
  public void set(K key, V value) {
    Node node = this.getNode(key);  //查找到该键对应的节点
    if (node != null) { //若节点已存在
      node.value = value; //修改键的值
    } else {  //未查找到该节点
      this.dummyHead.next = new Node(key, value, this.dummyHead.next);
      //创建新节点插入到链表头部
      this.size++;  //添加节点后将映射元素个数加1
    }
  }

  /**
   * @MethodName: get
   * @Description: 根据键获取值操作具体实现
   * @Param key: 键
   * @Return V
   */
  @Override
  public V get(K key) {
    Node node = this.getNode(key);  //查找到该键对应的节点
    return node == null ? null : node.value; //若查找到会返回节点的键值，找不到返回null
  }

  /**
   * @MethodName: remove
   * @Description: 根据键删除键值对，并返回值操作的具体实现
   * @Param k: 键
   * @Return V
   */
  @Override
  public V remove(K key) {
    Node perv = this.dummyHead; //用来存储上一个节点的指针
    while (perv.next != null) { //若上一个节点的下一个节点，也就是当前节点，不为空说明没有遍历到底
      if (key.equals(perv.next.key)) { //若当前节点是用户要删除的节点，就不再让指针后移
        break;
      }
      perv = perv.next; //指针后移
    }
    if (perv.next != null) {  //若当前指针指向有元素，则是要删除元素
      // 否则就是遍历到末尾也没有找到要删除元素，即删除元素不存在，不用删除
      Node delNode = perv.next; //要删除的节点
      perv.next = delNode.next;  //将前一个节点的next指向要删除节点next所指向的节点，即跳过
      delNode.next = null;   //将要删除节点的指向置为空，会与链表完全脱离，垃圾回收机制会快速回收
      this.size--;  //删除后需要将链表元素个数减1
      return delNode.value; //将删除元素的键值返回
    } else { //若未找到要删除的元素
      return null;  //返回null
    }
  }

  /**
   * @MethodName: contains
   * @Description: 判断该映射中是否包含该键操作具体实现
   * @Param k: 键
   * @Return boolean
   */
  @Override
  public boolean contains(K key) {
    return this.getNode(key) != null; //若找到该节点不会返回空，就会返回true
  }

  /**
   * @MethodName: getSize
   * @Description: 获取映射中的元素个数操作具体实现
   * @Return int
   */
  @Override
  public int getSize() {
    return this.size;
  }

  /**
   * @MethodName: isEmpty
   * @Description: 判断映射是否为空操作具体实现
   * @Return boolean
   */
  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    Node cur = this.dummyHead.next; //存储当前节点的指针，从第头节点开始遍历
    while (cur != null) { //若当前节点已经为null，说明当前节点指针已经指到了末尾
      sb.append(cur + "-> ");
      cur = cur.next; //当前节点指针后移
    }
    return "LinkedList{" +
        "linked=[" + sb +
        "]}";
  }
}

上一篇文章

06-集合

下一篇文章

08-堆

查看评论 - NOTHING

Comments NOTHING

暂无评论

取消回复

Markdown Supported while Forbidden

你是我一生只会遇见一次的惊喜 ...

戳我呀 OωO 嘿嘿嘿ヾ(≧∇≦*)ゝ

bilibili~	Tieba	(=・ω・=)

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies

bili_smilies