基于数组或链表实现 Map

关注

发布于: 2021 年 03 月 22 日

程序员常用的 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

基于链表实现首先我们需要定义一个 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;}}

复制代码

get 方法的实现思路是遍历链表，然后比较每个 Node 中的 key 是否相等，如果相等就返回 value，否则返回 null

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

复制代码

put 方法的实现思路也是遍历链表，然后比较每个 Node 的 key 值是否相等，如果相等那么覆盖掉 value，如果未查找到有 key 相等的 node，那么就新建一个 Node 放到链表的开头

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

复制代码

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

@Overridepublic 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

@Overridepublic 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

@Overridepublic 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，需要插入并且移动数组

@Overridepublic 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 是否存在，如果不存在就直接返回，如果存在需要移动数组

@Overridepublic 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

最后（点关注，不迷路）

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后，写作不易，请不要白嫖我哟，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源

发布于: 2021 年 03 月 22 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/3cd08d093dec854060c04ba02】。文章转载请联系作者。

Silently9527

关注

公众号：贝塔学JAVA 2018.05.09 加入

Simple Programmer, Make the complex simple

发布

暂无评论

创作场景

基于数组或链表实现 Map

前言

Map API 的定义

基于链表实现 Map

基于数组实现 Map

最后（点关注，不迷路）

Silently9527

评论