的实现本文转载请联系贝学JAVA公众号。前言JAVA中的Map主要是将一个key和一个value关联起来。虽然JAVA中已经提供了很多Map的实现，但是为了学习和掌握常用的数据结构，我将从本文开始自己实现Map的功能。本文主要通过数组和链表来实现。黑树，哈希表的版本实现。通过自己手写各个版本的Map实现，掌握各个数据结构的优缺点，在实际工作中可以根据需要选择合适的Map。MapAPI的定义在开始之前，我们需要先定义Map的接口定义。后续版本将实现publicinterfaceMap{voidput(Kkey,Vvalue);Vget(Kkey);voiddelete(Kkey);基于这个接口。intsize();Iterablekeys();defaultbooleancontains(Kkey){returnget(key)!=null;}defaultbooleanisEmpty(){returnsize()==0;}}这个接口是最简单的Map定义，相信这些方法对于java程序员来说并不陌生；基于链表实现Map基于链表实现首先我们需要定义一个Node节点，表示我们需要存储的key，vlaueclassNode{Kkey;Vvalue;Nodeext;publicNode(Kkey,Vvalue,Nodeext){this.key=key;this.value=value;this.next=next;}}get方法的实现思路是遍历链表，然后比较每个Node中的key是否相等，如果相等则返回value相等，否则返回null@OverridepublicVget(Kkey){returnsearchNode(key).map(node->node.value).orElse(null);}publicOptionalsearchNode(Kkey){for(Nodenode=root;node!=null;node=node.next){if(node.key.equals(key)){returnOptional.of(node);}}returnOptional.empty();}put方法的实现思路也是为了遍历链表，然后比较每个Node的key值是否相等，如果相等则覆盖值，如果没有找到相同key的节点，则创建一个新的Node放在链表的开头列出@Overridepublicvoidput(Kkey,Vvalue){OptionaloptionalNode=searchNode(key);if(可选节点。存在（）){optionalNode.get().value=value;return;}this.root=newNode(key,value,root);}delete方法的实现也需要遍历链表，因为我们的是单向的链表，删除一个节点有两种思路。第一种是在遍历链表时记录当前节点的前一个节点，将前一个节点的next指向当前节点的next；二是遍历到需要删除的节点。将节点的nextkey和value完整复制到要删除的节点，next指针指向next.next，例如：first->A->B->C->D->E->F->G->NULL,删除节点C，将节点D完全复制到c，然后C->E，变相删除C@Overridepublicvoiddelete(Kkey){//第一次实现：//for(Nodenode=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(Nodenode=first;node!=null;node=node.next){if(node.key.equals(key)){Nodeext=node.next;node.key=next.key;node.value=next.value;node.next=next.next;}}}基于链表的分析实现map，每次put，get，delete都需要遍历整个链表，效率很低，无法处理大量数据，时间复杂度为O(N)。”Map的基于数组的实现-基于链表的实现非常效率低下，因为每次操作都需要遍历链表。如果我们的数据是有序的，我们在查找的时候可以使用二分查找的方式，get方式会快很多。为了体现我们的Map是有序的，我们需要重新定义一个有序的MappublicinterfaceSortedMap<KextendsComparable,V>extendsMap{intrank(Kkey);}这个定义要求key必须实现Comparable接口，rank方法如果key值存在则返回数组中对应的下标,如果不存在在基于数组的实现中，我们将定义两个数组变量来存储键和值；rank方法的实现：由于我们整个数组是有序的，所以可以使用二分查找的方法（可以勾选《老哥是时候来复习下数据结构与算法了》），如果存在，则返回数组的下表，如果不存在，则返回0@Overridepublicintrank(Kkey){intlo=0,hi=size-1;while(lo<=hi){intmid=(hi-lo)/2+lo;intcompare=key.compareTo(keys[mid]);if(compare>0){lo=mid+1;}elseif(compare<0){hi=mid-1;}else{returnmid;}}returnlo;}get方法实现：根据rank方法，判断返回的keys[index]并将其与密钥进行比较。如果它们相等，则返回values[index]；如果它们不相等，则返回null@OverridepublicVget(Kkey){intindex=this.rank(key);if(indexindex;j--){this.键[j]=this.keys[j--];this.values[j]=this.values[j--];}keys[index]=key;values[index]=value;size++;}delete方法实现：使用rank方法判断是否key存在，不存在直接返回，存在则需要移动数组@Overridepublicvoiddelete(Kkey){intindex=this.rank(key);if(Objects.isNull(keys[index])||key.compareTo(keys[index])!=0){return;}for(intj=index;j
