数据结构——映射(Map)

一、概述

映射是一种快速的键查找数据结构体，可用于灵活地对其单个元素进行索引。与 MATLAB® 软件中仅允许通过整数索引获取元素的大多数数组数据结构体不同，映射的索引几乎可以是任何数值标量或字符向量。

 

指向映射元素的索引称为键。这些键以及与其相关的数据值都存储在映射内。映射的每个条目都包含一个唯一键及其相应的值。

定义

映射指的就是Map。它是由键值对（key，value）组成的集合。特点是：键具有唯一性，但是值可以重复。在scala中，Map也可分为不可变Map和可变Map。若添加重复key的新值，则新值覆盖旧值。不可变Map指的是元素、长度均不可变。

特点

• 存储键值(Key, Value)数据对的数据结构
• 根据键(Key)，寻找值(Value)
• 非常容易使用链表或二分搜索树进行实现
• Java中的HashMap和TreeMap底层分别基于哈希表和红黑树进行实现

二、代码实现

• 非常容易使用链表或二分搜索树进行实现

2.1 创建映射类接口

public interface Map<K, V> { /** * 添加元素 * @param key * @param value */ void add(K key, V value); /** * 删除元素，返回元素对应的value * @param key * @return */ V remove(K key); /** * 是否包含key * @param key * @return */ boolean contains(K key); /** * 修改元素key对应的value * @param key * @param value */ void set(K key, V value); /** * 获取key对应的value * @param key * @return */ V get(K key); /** * 映射的元素个数 * @return */ int getSize(); /** * 映射是否为空 * @return */ boolean isEmpty(); }

2.2 基于链表实现映射

/** * @Author: huangyibo * @Date: 2022/2/15 20:39 * @Description: 基于链表实现映射 */ public class LinkedListMap<K, V> implements Map<K, V> { private class Node<K, V>{ public K key; public V value; public Node<K, V> next; public Node(K key, V value){ this.key = key; this.value = value; } @Override public String toString() { return key.toString() +" : " + value.toString(); } } private Node<K, V> dummyHead; private Integer size; public LinkedListMap(){ dummyHead = new Node<>(null, null); size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } /** * 获取key对应的node，不存在返回null * @param key * @return */ private Node<K, V> getNode(K key){ Node<K, V> 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<K, V> node = getNode(key); return node == null ? null : node.value; } @Override public void add(K key, V value) { Node<K, V> node = getNode(key); if(node != null){ //key已存在，则更新 node.value = value; return; } //key不存在，则新增 Node<K, V> newNode = new Node<>(key, value); dummyHead.next = newNode.next = dummyHead.next; size ++; } @Override public void set(K key, V value) { Node<K, V> node = getNode(key); if(node == null){ //不存在直接抛异常 throw new IllegalArgumentException(key + " doesn't exist!"); } //key已存在，则更新 node.value = value; } @Override public V remove(K key) { Node<K, V> prev = dummyHead; //循环判断key是否存在 while (prev.next != null) { if(prev.next.key.equals(key)){ break; } prev = prev.next; } //如果key存在，则进行删除 if(prev.next != null){ Node<K, V> delNode = prev.next; prev.next = delNode.next; delNode.next = null; size --; return delNode.value; } //key不存在，返回null return null; } }

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

/** * @Author: huangyibo * @Date: 2022/2/15 21:14 * @Description: 基于二分搜索树实现映射 */ public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> { //二分搜索树节点类 private class Node<K extends Comparable<K>, V>{ public K key; public V value; public Node<K, V> left; public Node<K, V> right; public Node(K key, V value){ this.key = key; this.value = value; this.left = null; this.right = null; } @Override public String toString() { return key.toString() +" : " + value.toString(); } } // 根节点 private Node<K, V> root; // 树容量 private Integer size; public BSTMap(){ root = null; size = 0; } @Override public boolean isEmpty() { return size == 0; } @Override public int getSize() { return size; } /** * 向二分搜索树添加新的元素(key,value) * @param key * @param value */ @Override public void add(K key, V value){ //向根节点添加元素e root = add(root, key, value); } /** * 向以node为根的二分搜索树中插入元素(key,value)，递归算法 * @param node * @param key * @param value * @return 返回插入新元素的二分搜索树的根 */ private Node<K, V> add(Node<K, V> node, K key, V value){ if(node == null){ size ++; return new Node<>(key, value); } //递归调用，元素添加到node.left if(key.compareTo(node.key) < 0){ node.left = add(node.left, key, value); }else if(key.compareTo(node.key) > 0){ //递归调用，元素添加到node.right node.right = add(node.right, key, value); }else { node.value = value; } //返回当前根节点 return node; } /** * 根据key从当前以当前node为根节点中寻找value, 不存在返回null * @param node * @param key * @return */ private Node<K, V> getNode(Node<K, V> node, K key){ //递归终止条件 if(node == null){ return null; } //待寻找key比当前节点key小，递归调用node.left if(key.compareTo(node.key) < 0){ return getNode(node.left, key); }else if(key.compareTo(node.key) > 0){ //待寻找key比当前节点key大，递归调用node.right return getNode(node.right, key); }else { //待寻找key和当前节点key相等，直接返回 return node; } } @Override public boolean contains(K key) { return getNode(root, key) != null; } @Override public void set(K key, V value) { Node<K, V> node = getNode(root, key); if(node == null){ //不存在直接抛异常 throw new IllegalArgumentException(key + " doesn't exist!"); } //key已存在，则更新 node.value = value; } @Override public V get(K key) { Node<K, V> node = getNode(root, key); return node == null ? null : node.value; } /** * 返回以node为根的二分搜索树的最小值所在的节点 * @param node * @return */ private Node<K, V> minimum(Node<K, V> node){ if(node.left == null){ return node; } return minimum(node.left); } /** * 删除以node为根的二分搜索树中的最小节点， * 返回删除节点后新的二分搜索树的根 * @param node * @return */ private Node<K, V> removeMin(Node<K, V> node){ if(node.left == null){ Node<K, V> rightNode = node.right; node.right = null; size --; return rightNode; } //递归调用node.left node.left = removeMin(node.left); return node; } /** * * @param e */ /** * 从二分搜索树中删除元素键为key的节点, 并返回value, 不存在返回null * @param key * @return */ @Override public V remove(K key){ Node<K, V> node = getNode(root, key); if(node == null){ //不存在直接返回null return null; } //存在 root = remove(root, key); return node.value; } /** * 删除以node为根的二分搜索树中键为key的节点，递归递归方式 * 返回删除节点后新的二分搜索树的根 * @param node * @param key * @return */ private Node<K, V> remove(Node<K, V> node, K key){ //节点为空，直接返回 if(node == null){ return null; } if(key.compareTo(node.key) < 0){ //待删除元素key小于当前节点的键，向左递归寻找 node.left = remove(node.left, key); return node; }else if(key.compareTo(node.key) > 0){ //待删除元素key大于当前节点的键，向右递归寻找 node.right = remove(node.right, key); return node; }else { //待删除节点左子树为空 if(node.left == null){ Node<K, V> rightNode = node.right; node.right = null; size --; return rightNode; } //待删除节点右子树为空 if(node.right == null){ Node<K, V> rightNode = node.left; node.left = null; size --; return rightNode; } //待删除节点左、右子树不为空 //找到比待删除节点大的最小节点，即待删除节点右子树最小节点 //用这个节点顶替待删除节点的位置 //找到比待删除节点大的最小节点，即待删除节点右子树最小节点 Node<K, V> successor = minimum(node.right); //删除比待删除节点大的最小节点，并将返回值给succeer的右孩子 successor.right = removeMin(node.right); //node.left赋值给successor.left successor.left = node.left; //node节点和二分搜索树脱离关系 node.left = node.right = null; return successor; } } }

参考： https://blog.csdn.net/love905661433/article/details/82984708

https://ww2.mathworks.cn/help/matlab/matlab_prog/overview-of-the-map-data-structure.html