IDEA plug-ins commonly used by programmers: github.com/silently952…

Wechat official account: Beta learning Java

preface

A Map in JAVA is basically about associating a key with a value. Although JAVA has provided a lot of Map implementation, in order to learn and master the common data structure, I will implement the Map function by myself from the beginning of this article, this article mainly through the array and linked list two ways to achieve, then provide binary tree, red black tree, hash table version implementation. By writing each version of the Map, you can master the advantages and disadvantages of each data structure and select a suitable Map according to actual work needs.

Map API definition

Before we start, we need to define the Map interface definition, which will be implemented in subsequent versions

public interface Map<K, V> {
    void put(K key, V value);

    V get(K key);

    void delete(K key);
    
    int size();

    Iterable<K> keys();

    default boolean contains(K key) {
        return get(key) != null;
    }

    default boolean isEmpty() {
        return size() == 0;
    }
}

Copy the code

This interface is the simplest Map definition, and these methods will be familiar to Java programmers;

Implement Map based on linked list

  1. First, we need to define a Node that represents the key and vlaue that we need to store
class Node { K key; V value; Node next; public Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; }}Copy the code
  1. The get method iterates through the list and compares the keys in each Node for equality, returning value if they are equal and null otherwise
@Override public V get(K key) { return searchNode(key).map(node -> node.value).orElse(null); } public Optional<Node> searchNode(K key) { for (Node node = root; node ! = null; node = node.next) { if (node.key.equals(key)) { return Optional.of(node); } } return Optional.empty(); }Copy the code
  1. The put method traverses the list and compares whether each Node has the same key. If the key is equal, the value is overwritten. If no Node with the same key is found, a new Node is created and placed at the beginning of the list
@Override
public void put(K key, V value) {
    Optional<Node> optionalNode = searchNode(key);

    if (optionalNode.isPresent()) {
        optionalNode.get().value = value;
        return;
    }
    this.root = new Node(key, value, root);
}

Copy the code
  1. The delete method also needs to traverse the linked list, because our list is one-way, there are two ways to delete a node. The first way is to record the last node of the current node when traversing the linked list, and point the next of the last node to the next of the current node. Second, when traversing the node to be deleted, copy the key and value of the next node to be deleted to the node to be deleted, and point the next pointer to next. Next, for example: First -> A -> B -> C -> D -> F -> G -> NULL
@override public void delete(key) {// for (Node Node = first, preNode = null; node ! = null; preNode = node, node = node.next) { // if (node.key.equals(key)) { // if (Objects.isNull(preNode)) { // first = first.next; // } else { // preNode.next = node.next; For (Node Node = first; node ! = null; node = node.next) { if (node.key.equals(key)) { Node next = node.next; node.key = next.key; node.value =next.value; node.next = next.next; }}}Copy the code

Analysis of the above map based on linked list shows that every PUT, GET and DELETE need to traverse the whole linked list, which is very inefficient and cannot process a large amount of data, and the time complexity is O(N).

Implement Map based on array

The implementation based on the list is very inefficient, because every operation needs to traverse the list. If our data is ordered, we can use binary lookup, and the GET method will be much faster

To show that our Map is ordered, we need to redefine an ordered Map

public interface SortedMap<K extends Comparable<K>, V> extends Map<K, V> {
    int rank(K key);
}
Copy the code

The definition requires that key implement the interface Comparable. The rank method returns the corresponding subscript in the array if key exists, or the number of keys less than key if it does not

  • In our array-based implementation, we define two array variables to store keys and values in parts.
  • Since the entire array is ordered, we can use binary search (see “it’s time to review the data structure and algorithm”), if there is an array return table, if there is no return 0
@Override
public int rank(K key) {
    int lo = 0, hi = size - 1;
    while (lo <= hi) {
        int mid = (hi - lo) / 2 + lo;
        int compare = key.compareTo(keys[mid]);
        if (compare > 0) {
            lo = mid + 1;
        } else if (compare < 0) {
            hi = mid - 1;
        } else {
            return mid;
        }
    }
    return lo;
}
Copy the code
  • Get method implementation: based on rank method, judge return keys[index] and key comparison, if equal values[index], return null
@Override
public V get(K key) {
    int index = this.rank(key);
    if (index < size && key.compareTo(keys[index]) == 0) {
        return values[index];
    }
    return null;
}

Copy the code
  • Put method implementation: Based on the rank method, judge the returned keys[index] and key comparison, if the value is equal to directly modify the value of values[index], if the value is not equal, the key does not exist, need to insert and move the array
@Override
public void put(K key, V value) {
    int index = this.rank(key);
    if (index < size && key.compareTo(keys[index]) == 0) {
        values[index] = value;
        return;
    }

    for (int j = size; j > index; j--) {
        this.keys[j] = this.keys[j--];
        this.values[j] = this.values[j--];
    }
    keys[index] = key;
    values[index] = value;
    size++;
}
Copy the code
  • Delete method implementation: through the rank method to determine whether the key exists, if it does not directly return, if it does need to move the array
@Override public void delete(K key) { int index = this.rank(key); if (Objects.isNull(keys[index]) || key.compareTo(keys[index]) ! = 0) { return; } for (int j = index; j < size - 1; j++) { keys[j] = keys[j + 1]; values[j] = values[j + 1]; } keys[size - 1] = null; values[size - 1] = null; size--; }Copy the code

Although the binary search method adopted by GET method is O(logN) fast, the efficiency of Map based on array is still very low in the case of processing a large amount of data, because the PUT method is still too slow. In the next chapter, we will implement Map based on binary tree and continue to improve efficiency

All source code has been put into github repository github.com/silently952…

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏