基于数组或链表实现Map

[[388024]]

本文转载自微信公众号「贝塔学JAVA」，作者Silently9527。转载本文请联系贝塔学JAVA公众号。

“专业、务实、高效、创新、把客户的事当成自己的事”是我们每一个人一直以来坚持追求的企业文化。 创新互联公司是您可以信赖的网站建设服务商、专业的互联网服务提供商! 专注于成都做网站、网站建设、软件开发、设计服务业务。我们始终坚持以客户需求为导向，结合用户体验与视觉传达，提供有针对性的项目解决方案，提供专业性的建议，创新互联建站将不断地超越自我，追逐市场，引领市场！

前言

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

Map API的定义

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

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

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

基于链表实现Map

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

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

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

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

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

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

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

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

”

基于数组实现Map

基于链表的实现非常低效，因为每次操作都需要遍历链表，假如我们的数据是有序的，那么查找的时候我们可以使用二分查找法，那么get方法会加快很多

为了体现出我们的Map是有序的，我们需要重新定义一个有序的Map

 
 
 
    
  
  
  
  1. public interface SortedMap, V> extends Map { 
    2. 
  
  
  
  2.     int rank(K key); 
    3. 
  
  
  
  3. } 
    4.

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

  • 在基于数组的实现中，我们会定义两个数组变量分部存放keys、values;
  • rank方法的实现：由于我们整个数组都是有序的，我们可以二分查找法(可以查看《老哥是时候来复习下数据结构与算法了》)，如果存在就返回所在数组的下表，如果不存在就返回0
 
 
 
    
  
  
  
  1. @Override 
    2. 
  
  
  
  2. public int rank(K key) { 
    3. 
  
  
  
  3.     int lo = 0, hi = size - 1; 
    4. 
  
  
  
  4.     while (lo <= hi) { 
    5. 
  
  
  
  5.         int mid = (hi - lo) / 2 + lo; 
    6. 
  
  
  
  6.         int compare = key.compareTo(keys[mid]); 
    7. 
  
  
  
  7.         if (compare > 0) { 
    8. 
  
  
  
  8.             lo = mid + 1; 
    9. 
  
  
  
  9.         } else if (compare < 0) { 
    10. 
  
  
  
  10.             hi = mid - 1; 
    11. 
  
  
  
  11.         } else { 
    12. 
  
  
  
  12.             return mid; 
    13. 
  
  
  
  13.         } 
    14. 
  
  
  
  14.     } 
    15. 
  
  
  
  15.     return lo; 
    16. 
  
  
  
  16. } 
    17.

get方法实现：基于rank方法，判断返回的keys[index]与key进行比较，如果相等返回values[index]，不相等就返回null

 
 
 
    
  
  
  
  1. @Override 
    2. 
  
  
  
  2. public V get(K key) { 
    3. 
  
  
  
  3.     int index = this.rank(key); 
    4. 
  
  
  
  4.     if (index < size && key.compareTo(keys[index]) == 0) { 
    5. 
  
  
  
  5.         return values[index]; 
    6. 
  
  
  
  6.     } 
    7. 
  
  
  
  7.     return null; 
    8. 
  
  
  
  8. } 
    9.

put方法实现：基于rank方法，判断返回的keys[index]与key进行比较，如果相等直接修改values[index]的值，如果不相等表示不存在该key，需要插入并且移动数组

 
 
 
    
  
  
  
  1. @Override 
    2. 
  
  
  
  2. public void put(K key, V value) { 
    3. 
  
  
  
  3.     int index = this.rank(key); 
    4. 
  
  
  
  4.     if (index < size && key.compareTo(keys[index]) == 0) { 
    5. 
  
  
  
  5.         values[index] = value; 
    6. 
  
  
  
  6.         return; 
    7. 
  
  
  
  7.     } 
    8. 
  
  
  
  8.  
    9. 
  
  
  
  9.     for (int j = size; j > index; j--) { 
    10. 
  
  
  
  10.         this.keys[j] = this.keys[j--]; 
    11. 
  
  
  
  11.         this.values[j] = this.values[j--]; 
    12. 
  
  
  
  12.     } 
    13. 
  
  
  
  13.     keys[index] = key; 
    14. 
  
  
  
  14.     values[index] = value; 
    15. 
  
  
  
  15.     size++; 
    16. 
  
  
  
  16. } 
    17.

delete方法实现：通过rank方法判断该key是否存在，如果不存在就直接返回，如果存在需要移动数组

 
 
 
    
  
  
  
  1. @Override 
    2. 
  
  
  
  2. public void delete(K key) { 
    3. 
  
  
  
  3.     int index = this.rank(key); 
    4. 
  
  
  
  4.     if (Objects.isNull(keys[index]) || key.compareTo(keys[index]) != 0) { 
    5. 
  
  
  
  5.         return; 
    6. 
  
  
  
  6.     } 
    7. 
  
  
  
  7.     for (int j = index; j < size - 1; j++) { 
    8. 
  
  
  
  8.         keys[j] = keys[j + 1]; 
    9. 
  
  
  
  9.         values[j] = values[j + 1]; 
    10. 
  
  
  
  10.     } 
    11. 
  
  
  
  11.     keys[size - 1] = null; 
    12. 
  
  
  
  12.     values[size - 1] = null; 
    13. 
  
  
  
  13.     size--; 
    14. 
  
  
  
  14. } 
    15.

基于数组实现的Map，虽然get方法采用的二分查找法，很快O(logN)，但是在处理大量数据的情况下效率依然很低，因为put方法还是太慢;下篇我们将基于二叉树来实现Map，继续改进提升效率

”

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

分享标题：基于数组或链表实现Map
标题链接：http://www.csdahua.cn/qtweb/news21/508421.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

做网站知识

同城分类信息

网站制作　　 　成都企业网站设计　　 　成都app软件开发公司　　 　网络整合营销　　 　四川國際商會　　 　恒翔机电　　 　网上商城管理系统　　 　网络推广平台　　 　中国（西部）云计算中心　　 　眉山服务器租用　　 　特丽尔硅藻泥　　 　成都app制作　　 　四川发电机维修　　 　网站优化排名推广　　 　达州网站建设　　 　成都婚庆策划　　 　合江网站建设　　 　成都网站制作　　 　成都画册制作　　 　百度推广公司