关于java:基于数组或链表实现Map

程序员罕用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin

微信公众号：贝塔学 Java

前言

JAVA 中的 Map 次要就是将一个键和一个值分割起来。尽管 JAVA 中曾经提供了很多 Map 的实现，为了学习并把握罕用的数据结构，从本篇开始我将本人实现 Map 的性能，本篇次要是通过数组和链表两种形式实现，之后提供二叉树，红黑树，散列表的版本实现。通过本人手写各个版本的 Map 实现，把握每种数据结构的优缺点，能够在理论的工作中依据须要抉择适宜的 Map。

Map API 的定义

在开始之前，咱们须要先定义出 Map 的接口定义，后续的版本都会基于此接口实现

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;
    }
}

这个接口是最简略的一个 Map 定义，置信这些办法对于 java 程序员来说不会生疏；

基于链表实现 Map

1. 基于链表实现首先咱们须要定义一个 Node 节点，示意咱们须要存储的 key、vlaue

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;
    }

}

1. get 办法的实现思路是遍历链表，而后比拟每个 Node 中的 key 是否相等，如果相等就返回 value，否则返回 null

@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();}

1. put 办法的实现思路也是遍历链表，而后比拟每个 Node 的 key 值是否相等，如果相等那么笼罩掉 value，如果未查找到有 key 相等的 node，那么就新建一个 Node 放到链表的结尾

@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);
}

1. delete 办法实现同样也须要遍历链表，因为咱们的是单向链表，删除某个节点有两种思路，第一种，在遍历链表的时候记录下以后节点的上一个节点，把上一个节点的 next 指向以后节点 next; 第二种，当遍历到须要删除的节点时，把须要删除节点的 next 的 key、value 齐全复制到须要删除的节点，把 next 指针指向 next.next，比方：first – > A -> B -> C -> D -> E -> F -> G -> NULL, 要删除 C 节点，就把 D 节点齐全复制到 c 中，而后 C -> E，变相删除了 C

@Override
public void delete(K 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;
        }
    }
}

剖析下面基于链表实现的 map，每次的 put、get、delete 都须要遍历整个链表，十分的低效，无奈解决大量的数据，工夫复杂度为 O(N)

基于数组实现 Map

基于链表的实现十分低效，因为每次操作都须要遍历链表，如果咱们的数据是有序的，那么查找的时候咱们能够应用二分查找法，那么 get 办法会放慢很多

为了体现出咱们的 Map 是有序的，咱们须要从新定义一个有序的 Map

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

该定义要求 key 必须实现接口Comparable，rank 办法如果 key 值存在就返回对应在数组中的下标，如果不存在就返回小于 key 键的数量

• 在基于数组的实现中，咱们会定义两个数组变量分部寄存 keys、values；
• rank 办法的实现：因为咱们整个数组都是有序的，咱们能够二分查找法（能够查看《老哥是时候来温习下数据结构与算法了》），如果存在就返回所在数组的下表，如果不存在就返回 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;
}

• get 办法实现：基于 rank 办法，判断返回的 keys[index]与 key 进行比拟，如果相等返回 values[index]，不相等就返回 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;
}

• put 办法实现：基于 rank 办法，判断返回的 keys[index]与 key 进行比拟，如果相等间接批改 values[index]的值，如果不相等示意不存在该 key，须要插入并且挪动数组

@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++;
}

• delete 办法实现：通过 rank 办法判断该 key 是否存在，如果不存在就间接返回，如果存在须要挪动数组

@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--;
}

基于数组实现的 Map，尽管 get 办法采纳的二分查找法，很快 O(logN)，然而在解决大量数据的状况下效率仍然很低，因为 put 办法还是太慢；下篇咱们将基于二叉树来实现 Map，持续改良晋升效率

文中所有源码已放入到了 github 仓库 https://github.com/silently9527/JavaCore

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源????