JAVA中的Map主要就是将一个键和一个值联系起来。虽然JAVA中已经提供了很多Map的实现，为了学习并掌握常用的数据结构，从本篇开始我将自己实现Map的功能，本篇主要是通过数组和链表两种方式实现，之后提供二叉树，红黑树，散列表的版本实现。通过自己手写各个版本的Map实现，掌握每种数据结构的优缺点，可以在实际的工作中根据需要选择适合的Map。

Map API的定义

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

1. public interface Map<K, V> { 
2.     void put(K key, V value); 
3.  
4.     V get(K key); 
5.  
6.     void delete(K key); 
7.      
8.     int size(); 
9.  
10.     Iterable<K> keys(); 
11.  
12.     default boolean contains(K key) { 
13.         return get(key) != null; 
14.     } 
15.  
16.     default boolean isEmpty() { 
17.         return size() == 0; 
18.     } 
19. } 

这个接口是最简单的一个Map定义，相信这些方法对于java程序员来说不会陌生;

基于链表实现Map

基于链表实现首先我们需要定义一个Node节点，表示我们需要存储的key、vlaue

1. class Node { 
2.     K key; 
3.     V value; 
4.     Node next; 
5.  
6.     public Node(K key, V value, Node next) { 
7.         this.key = key; 
8.         this.value = value; 
9.         this.next = next; 
10.     } 
11.  
12. } 

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

1. @Override 
2. public V get(K key) { 
3.     return searchNode(key).map(node -> node.value).orElse(null); 
4. } 
5.  
6. public Optional<Node> searchNode(K key) { 
7.     for (Node node = root; node != null; node = node.next) { 
8.         if (node.key.equals(key)) { 
9.             return Optional.of(node); 
10.         } 
11.     } 
12.     return Optional.empty(); 
13. } 

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

1. @Override 
2. public void put(K key, V value) { 
3.     Optional<Node> optionalNode = searchNode(key); 
4.  
5.     if (optionalNode.isPresent()) { 
6.         optionalNode.get().value = value; 
7.         return; 
8.     } 
9.     this.root = new Node(key, value, root); 
10. } 

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

1. @Override 
2. public void delete(K key) { 
3. // 第一种实现： 
4. //        for (Node node = first, preNode = null; node != null; preNode = node, node = node.next) { 
5. //            if (node.key.equals(key)) { 
6. //                if (Objects.isNull(preNode)) { 
7. //                    first = first.next; 
8. //                } else { 
9. //                    preNode.next = node.next; 
10. //                } 
11. //            } 
12. //        } 
13.  
14. // 第二中实现: 
15.     for (Node node = first; node != null; node = node.next) { 
16.         if (node.key.equals(key)) { 
17.             Node next = node.next; 
18.             node.key = next.key; 
19.             node.value =next.value; 
20.             node.next = next.next; 
21.         } 
22.     } 
23. } 

分析上面基于链表实现的map，每次的put、get、delete都需要遍历整个链表，非常的低效，无法处理大量的数据，时间复杂度为O(N)