内容简介:映射(Map)是用于存取键值对的数据结构,一个键只能对应一个值且键不能重复。基本方法接口:
映射(Map)是用于存取键值对的数据结构,一个键只能对应一个值且键不能重复。
基本方法接口:
/** * className Map * description TODO * * @author ln * @version 1.0 * @date 2019/5/18 15:51 */ 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(); } 复制代码
基于链表的映射实现
/** * className LinkedListMap * description TODO * * @author ln * @version 1.0 * @date 2019/5/18 15:54 */ 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; } /** * 辅助函数 * 根据key的值返回节点的引用 * @param key * @return */ 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 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 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; } @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 set(K key, V newValue) { Node node = getNode(key); if (node == null){ throw new IllegalArgumentException(key + "doesn't exist!"); } node.value = newValue; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } } 复制代码
基于二分搜索树的映射实现
/** * className BSTMap * description TODO * * @author ln * @version 1.0 * @date 2019/5/20 16:09 */ 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; this.left = null; this.right = null; } } private Node root; private int size; public BSTMap(){ root = null; size = 0; } /** * 辅助函数 * 返回以node为根的二分搜索树中,key所在的节点 * @param node * @param key * @return */ 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 { return getNode(node.right, key); } } @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 { node.value = value; } return node; } /** * 返回以node为根的二分搜索树的最小值所在的节点 * @param node * @return */ private Node minimum(Node node){ if (node.left == null){ return node; } return minimum(node.left); } /** * 删除以node为根的二分搜索树的最小节点 * 返回删除节点后新的树的根 * @param node * @return */ 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; } @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); 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; 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.right = node.left = null; return successor; } } @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; } @Override public void set(K key, V newValue) { Node node = getNode(root, key); if (node == null){ throw new IllegalArgumentException(key + "doesn't exist!"); } node.value = newValue; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } } 复制代码
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- java – 在O(1)中使用getKey(B)的一对一映射数据结构(A,B)?
- MyBatis从入门到精通(十一):MyBatis高级结果映射之一对多映射
- MyBatis从入门到精通(九):MyBatis高级结果映射之一对一映射
- 【mybatis xml】数据层框架应用--Mybatis(三)关系映射之一对一关系映射
- Hibernate 关系映射整理
- SpringMVC——请求映射
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。