映射Map

桃扇骨 2021-09-23 22:20 615阅读 0赞

数学理解:

在这里插入图片描述
在这里插入图片描述

接口实现:

在这里插入图片描述

  1. package Map;
  2. public interface Map<K, V> {
  3. void add(K key, V value);
  4. V remove(K key);
  5. boolean contains(K key);
  6. V get(K key);
  7. void set(K key, V newValue);
  8. int getSize();
  9. boolean isEmpty();
  10. }

1、基于链表实现映射

  1. package Map;
  2. import Set.FileOperation;
  3. import java.util.ArrayList;
  4. public class LinkedListMap<K, V> implements Map<K, V> {
  5. private class Node{
  6. public K key;
  7. public V value;
  8. public Node next;
  9. public Node(K key, V value, Node next){
  10. this.key = key;
  11. this.value = value;
  12. this.next = next;
  13. }
  14. public Node(K key, V value){
  15. this(key, value, null);
  16. }
  17. public Node(){
  18. this(null, null, null);
  19. }
  20. @Override
  21. public String toString(){
  22. return key.toString() + " : " + value.toString();
  23. }
  24. }
  25. private Node dummyHead;
  26. private int size;
  27. public LinkedListMap(){
  28. dummyHead = new Node();
  29. size = 0;
  30. }
  31. @Override
  32. public int getSize(){
  33. return size;
  34. }
  35. @Override
  36. public boolean isEmpty(){
  37. return size == 0;
  38. }
  39. private Node getNode(K key){
  40. Node cur = dummyHead.next;
  41. while(cur != null){
  42. if(cur.key.equals(key))
  43. return cur;
  44. cur = cur.next;
  45. }
  46. return null;
  47. }
  48. @Override
  49. public boolean contains(K key){
  50. return getNode(key) != null;
  51. }
  52. @Override
  53. public V get(K key){
  54. Node node = getNode(key);
  55. return node == null ? null : node.value;
  56. }
  57. @Override
  58. public void add(K key, V value){
  59. Node node = getNode(key);
  60. if(node == null){
  61. dummyHead.next = new Node(key, value, dummyHead.next);
  62. size ++;
  63. }
  64. else
  65. node.value = value;
  66. }
  67. @Override
  68. public void set(K key, V newValue){
  69. Node node = getNode(key);
  70. if(node == null)
  71. throw new IllegalArgumentException(key + " doesn't exist!");
  72. node.value = newValue;
  73. }
  74. @Override
  75. public V remove(K key){
  76. Node prev = dummyHead;
  77. while(prev.next != null){
  78. if(prev.next.key.equals(key))
  79. break;
  80. prev = prev.next;
  81. }
  82. if(prev.next != null){
  83. Node delNode = prev.next;
  84. prev.next = delNode.next;
  85. delNode.next = null;
  86. size --;
  87. return delNode.value;
  88. }
  89. return null;
  90. }

2、基于二分搜索树实现映射

  1. package Map;
  2. import java.util.ArrayList;
  3. public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
  4. private class Node {
  5. public K key;
  6. public V value;
  7. public Node left, right;
  8. public Node(K key, V value) {
  9. this.key = key;
  10. this.value = value;
  11. left = null;
  12. right = null;
  13. }
  14. }
  15. private Node root;
  16. private int size;
  17. public BSTMap() {
  18. root = null;
  19. size = 0;
  20. }
  21. @Override
  22. public int getSize() {
  23. return size;
  24. }
  25. @Override
  26. public boolean isEmpty() {
  27. return size == 0;
  28. }
  29. // 向二分搜索树中添加新的元素(key, value)
  30. @Override
  31. public void add(K key, V value) {
  32. root = add(root, key, value);
  33. }
  34. // 向以node为根的二分搜索树中插入元素(key, value),递归算法
  35. // 返回插入新节点后二分搜索树的根
  36. private Node add(Node node, K key, V value) {
  37. if (node == null) {
  38. size++;
  39. return new Node(key, value);
  40. }
  41. if (key.compareTo(node.key) < 0)
  42. node.left = add(node.left, key, value);
  43. else if (key.compareTo(node.key) > 0)
  44. node.right = add(node.right, key, value);
  45. else // key.compareTo(node.key) == 0
  46. node.value = value;
  47. return node;
  48. }
  49. // 返回以node为根节点的二分搜索树中,key所在的节点
  50. private Node getNode(Node node, K key) {
  51. if (node == null)
  52. return null;
  53. if (key.equals(node.key))
  54. return node;
  55. else if (key.compareTo(node.key) < 0)
  56. return getNode(node.left, key);
  57. else // if(key.compareTo(node.key) > 0)
  58. return getNode(node.right, key);
  59. }
  60. @Override
  61. public boolean contains(K key) {
  62. return getNode(root, key) != null;
  63. }
  64. @Override
  65. public V get(K key) {
  66. Node node = getNode(root, key);
  67. return node == null ? null : node.value;
  68. }
  69. @Override
  70. public void set(K key, V newValue) {
  71. Node node = getNode(root, key);
  72. if (node == null)
  73. throw new IllegalArgumentException(key + " doesn't exist!");
  74. node.value = newValue;
  75. }
  76. // 返回以node为根的二分搜索树的最小值所在的节点
  77. private Node minimum(Node node) {
  78. if (node.left == null)
  79. return node;
  80. return minimum(node.left);
  81. }
  82. // 删除掉以node为根的二分搜索树中的最小节点
  83. // 返回删除节点后新的二分搜索树的根
  84. private Node removeMin(Node node) {
  85. if (node.left == null) {
  86. Node rightNode = node.right;
  87. node.right = null;
  88. size--;
  89. return rightNode;
  90. }
  91. node.left = removeMin(node.left);
  92. return node;
  93. }
  94. // 从二分搜索树中删除键为key的节点
  95. @Override
  96. public V remove(K key) {
  97. Node node = getNode(root, key);
  98. if (node != null) {
  99. root = remove(root, key);
  100. return node.value;
  101. }
  102. return null;
  103. }
  104. private Node remove(Node node, K key) {
  105. if (node == null)
  106. return null;
  107. if (key.compareTo(node.key) < 0) {
  108. node.left = remove(node.left, key);
  109. return node;
  110. } else if (key.compareTo(node.key) > 0) {
  111. node.right = remove(node.right, key);
  112. return node;
  113. } else { // key.compareTo(node.key) == 0
  114. // 待删除节点左子树为空的情况
  115. if (node.left == null) {
  116. Node rightNode = node.right;
  117. node.right = null;
  118. size--;
  119. return rightNode;
  120. }
  121. // 待删除节点右子树为空的情况
  122. if (node.right == null) {
  123. Node leftNode = node.left;
  124. node.left = null;
  125. size--;
  126. return leftNode;
  127. }
  128. // 待删除节点左右子树均不为空的情况
  129. // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
  130. // 用这个节点顶替待删除节点的位置
  131. Node successor = minimum(node.right);
  132. successor.right = removeMin(node.right);
  133. successor.left = node.left;
  134. node.left = node.right = null;
  135. return successor;
  136. }
  137. }

映射的时间复杂度

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,615人围观)

还没有评论,来说两句吧...

相关阅读

    相关 映射Map

    数学理解: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n