We often use TreeMap or HashMap in the Java standard library. Their underlying implementation is red-black tree and hash table respectively. In this paper, we define our own mapping Map interface, and use our own data structure linked list, binary search tree and AVL tree to implement this Map interface.

1. Map interface

The mapping Map interface is shown below, and the function of the method is described in the annotation.

Public interface Map<K, V> {// Add a key-value pair to the mapping void add(K key, V value); Boolean contains(K key); V get(K key); Void set(K key, V newValue); V remove(K key); V remove(K key); // Return the number of key-value pairs in the mapping int getSize(); Boolean isEmpty(); }Copy the code

2, linked list implementation Map Map

The Map of the list implementation is shown below. Because the list we implemented in Data Structures 02 had only one generic type, but the implementation required two generic types K and V to Map this data structure, we re-implemented the list using two generic types. However, the re-implemented list added one more generic type. The underlying principle and implementation method are exactly the same as the linked list implemented in Data Structure 02. We will not explain more here. If you do not understand, you can go to see data Structure 02.

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; } @Override public int getSize(){ return size; } @Override public boolean isEmpty(){ return size == 0; } 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 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 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 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 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; }}Copy the code

3, binary search tree implementation of the Map Map

Binary search tree to realize the mapping of the Map as shown below, because we are the realization of data JieGouPian 05 binary search tree is only a generic, but need to Map the data structure of two generic K and V, therefore we use two kinds of generic implements a binary search tree again, but to achieve binary search tree in addition to a generic, The underlying principle and implementation method and data structure 05 binary search tree is completely consistent, we will not explain more here, there are not understand can go to see data structure 05;

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; } } private Node root; private int size; public BSTMap(){ root = null; size = 0; } @Override public int getSize(){ return size; } @Override public boolean isEmpty(){ return size == 0; } @override public void add(K key, V value){root = add(root, key, value); } // Insert the element (key, value) into the binary search tree with node as the root. 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 = value; return 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 // if(key.compareTo(node.key) > 0 return getNode(node.right, key); } @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; } private node minimum(node node){if(node. Left == null) return node; return minimum(node.left); 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; } // Return the root of the binary search tree. Private node remove(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{// key.compareTo(node.key) == 0 // 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; } // If the left and right subtrees of the Node to be deleted are not empty // Find the minimum Node that is bigger than the right subtree of the Node to be deleted // Use this Node to replace the location of the Node to be deleted. successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; }}}Copy the code

4. AVL tree implementation Map

The AVL tree implementation Map is shown below. We defined two generics when implementing AVL tree, so we do not need to re-implement AVL tree when implementing AVL tree mapping Map, so the mapping Map we implement is a layer of ENCAPSULATION of AVL tree API; For those not familiar with AVL trees, see Data Structures 07.

public class AVLMap<K extends Comparable<K>, V> implements Map<K, V> { private AVLTree<K, V> avl; public AVLMap(){ avl = new AVLTree<>(); } @Override public int getSize(){ return avl.getSize(); } @Override public boolean isEmpty(){ return avl.isEmpty(); } @Override public void add(K key, V value){ avl.add(key, value); } @Override public boolean contains(K key){ return avl.contains(key); } @Override public V get(K key){ return avl.get(key); } @Override public void set(K key, V newValue){ avl.set(key, newValue); } @Override public V remove(K key){ return avl.remove(key); }}Copy the code