数据结构篇|映射(Map)
1.简介
Map是以(key,value)键值对的形式存在的，可以通过查找key来获取value，生活中也会有很多使用场景，比如查字典时通过词找到词的含义，以及通过身份证号找到对应的人的信息。
- 实现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 newValue);
int getSize();
boolean isEmpty();
}
Map分别具有以上功能，所以就创建一个接口将对应的功能在接口中进行创建即可。
- 基于链表实现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, Node next){
this(key,null,next);
}
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;
}
}
创建一个类并实现Map接口，在LinkedListMap中需要有一个节点，节点中包含key和value和一个Node类型的next指针，如果用户在初始化时传入三个参数，就将它们各自赋值，如果传入两个参数，就将value设置为null，如果不传入话就默认进行初始化。再重写以下toString()方法，在方法中将key和value的toString()返回。然后在LinkedListMap内部再添加一个虚拟头节点和一个size变量计数，并在构造方法中将它们初始化。
- getSize()和isEmpty()方法
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
这两个方法只需直接将size返回和对size进行判断即可
- 辅助函数getNode()
private Node getNode(K key){
Node cur = dummyHead.next;
while (cur != null){
if (cur.key.equals(key)){
return cur;
}
cur = cur.next;
}
return null;
}
这个函数主要会用在后面要实现的一些操作上，可以让后面的操作逻辑更简单。将需要获取的key传入，方法内部首先会创建一个Node类型的cur，它是虚拟头节点之后的第一个元素，再循环进行查找，直到cur为空则循环结束，在循环中如果cur.key与传入的key相同的话就将cur返回，否则将cur向后移动，直至循环结束还没有找到的话就返回null。
- contains()和get()
@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;
}
contains()方法是查看map中是否包含传入的key的，如果key这个节点不为空，则返回true否则返回false。get()方法是根据key获取节点的值，根据getNode函数可以获得key对应的这个节点，然后判断node是否等于空即可，如果不为空则返回node对应的值。
- add方法
@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;
}
}
add方法需要传入键和值，根据键获取对应的节点，如果节点为空，就将节点添加在链表头，然后对size进行维护。否则就将value进行更新。
- set方法
@Override
public void set(K key, V newValue) {
Node node = getNode(key);
if (node != null) {
node.value = newValue;
} else {
throw new IllegalArgumentException("Not found" + key);
}
}
set方法与add方法类似，都是传入键和值向map中进行添加。首先获取key对应的节点，如果节点不为空，将value进行更新，否则抛出异常。
- remove方法
@Override
public V remove(K 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;
size--;
return delNode.value;
}
return null;
}
删除方法需要传入需要删除的元素的key，然后返回对应的value。具体的实现首先需要创建一个prev节点，它的位置在虚拟头节点的位置。然后循环判断prev.next是否为空，如果不为空就判断prev.next.key的值与传入的key是否相等，如果相等就结束循环，否则继续向后移动。跳出循环后key就保存在了prev.next，如果prev.next不为空，就将待删除的元素保存在delNode中，然后执行删除即可，不要忘记维护一下size，最后将delNode的值进行返回。如果没有找到对应的key则返回null。
- 基于二分搜索树实现Map
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;
}
@Override
public String toString() {
return key.toString() + ":" + value.toString();
}
}
private Node root;
private int size;
public BSTMap() {
root = null;
size = 0;
}
}
创建BSTMap类，因为是基于二分搜索树所以key要具有可比较性，然后再实现Map接口。BSTMap需要拥有节点，其中包含键-值和指向左右子树的指针。再继续添加一个根节点和一个计数变量size，在BSTMap被初始化时，将根节点设置为空，size设置为0。
- getSize()和isEmpty()方法
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
这两个方法直接使用size变量做操作即可，就不再介绍了。
- add()方法
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
private Node add(Node node, K key, V value) {
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 { //key.compareTo(node.key) == 0
//将node.value进行更新
node.value = value;
}
return node;
}
创建供用户使用的方法add()，这里只需要传入key-value，在方法内部进行从根节点开始的递归调用并将根节点返回。下面就来编写递归方法，首先需要判断传入的node是否为空，如果为空就将新节点进行添加。否则用用户传入的key和二分搜索树的key进行比较，如果小于0，则向左子树进行递归调用，如果大于0，就向右子树进行递归调用，这里需要注意要将方法返回值接住。如果两种条件都不满足，就将节点的值进行更新。最后将node进行返回。
- getNode()方法
//返回以node为根节点的二分搜索树中，可以所在的节点
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) == 0) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else { //key.compareTo(node.right) > 0
return getNode(node.right, key);
}
}
这是一个辅助函数，用于获取对应的key的节点。如果传入的node为空，就说明不存在该节点，那么就返回null即可。如果key相同就返回对应的node，否则按条件向左或向右进行递归调用。
- contains()和get()方法
@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 ? null : node.value;
}
第一个方法用于查找是否含有对应的key，在这里只需调用getNode()方法查看该key是否存在即可，get()方法是获取key对应的节点，如果不存在就返回空，否则返回node对应的值。
- set()方法
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node != null) {
node.value = newValue;
} else {
throw new IllegalArgumentException("Not found " + key);
}
}
set()方法首先获取key对应节点，判断节点是否为空，如果不为空就将值进行更新，否则抛出异常。
- minimum()方法
//返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
这个方法是获取key最小的节点，所以只需一直向左递归即可，直到为空为止。
- removeMin()
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
此方法是删除最小节点，所以也是一直向左子树递归，条件符合了就执行删除操作即可。然后将返回的节点与node的左子树连接，最终将node返回。
- remove()
@Override
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);
}else if (key.compareTo(node.key) > 0){
node.right = remove(node.right, key);
}else {
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;
}
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
return node;
}
终于到了正题——删除对应的元素，首先调用getNode()方法，查看key这个元素是否存在。如果存在就递归调用remove()即可，否则返回null。接下来实现remove()的重载方法，这里需要传入开始的节点和要删除的元素的key。在方法中首先要判断以下传入的node是否为空，如果为空就返回null。如果不为空就与元素的key进行比较，按照条件向左或向右子树递归，如果都不符合那就是相同了，说明找了到要删除的元素。首先判断node的左子树是否为空，如果为空保存它的右子树的根节点然后执行删除，然后判断右子树是否为空，如果为空保存它的左子树的根节点然后执行删除。如果都不为空的话就找到node右子树的最小节点进行保存，这里命名为successor，然后将successor的右子树与删除完最小节点的树根相连，再将successor的左子树与node的左子树相连，此时就完成了换位操作，就可以将node的左右子树都设置为空即可，并将successor返回，然后把根节点也进行返回，并将值赋给root节点。这步做到了将删除节点的二分搜索树的根返回。然后根据要求将传入的node的值进行返回。这样也就完成了删除节点操作。
