黑马程序员技术交流社区

标题: 自己实现Map接口简单方法<升级版> [打印本页]
作者: My_Android    时间: 2016-5-26 09:39
标题: 自己实现Map接口简单方法<升级版>
升级版功能：
1：提高查询效率。如何提高？
通过获得key.hashCode()来获得对象的散列码，即对象的地址。
在对散列码进行%数组的长度。
添加元素的时候只需要获得取完数的大小，添加到相应的下标的位置。
取出元素的时候获得%的大小，拿出相应下标的位置。
弊端：
效率提高了。%完之后的大小，可能会有相同的数值，会造成数据的丢失。
如何解决?
用链表来解决。Map的底层是<数组+链表>来实现的。数组放的不再是一个对象，而是一个链表。链表是有一个节点构成的。节点里的值就存放key，value 对象。
  1. import java.util.LinkedList;

  3. /**
  4. * 自定义Map实现升级版
  5. * 1：提高查询效率
  6. * @author hasee
  7. *
  8. */
  9. public class SxtMap002 {
  10.        
  11.         LinkedList[] arr = new LinkedList[999]; //map底层实现数组+链表
  12.        
  13.         int size;
  14.        
  15.         public void put(Object key,Object value){
  16.                 //创建一个键值对对象
  17.                 SxtEntry e = new SxtEntry(key,value);
  18.                 //获得key对象地址%数组的长度
  19.                 int a = key.hashCode()%arr.length;
  20.                 /**
  21.                  * 如果 arr[a]==null 代表没有链表对象，
  22.                  */
  23.                 if(arr[a] == null){
  24.                         //新建一个链表对象
  25.                         LinkedList list = new LinkedList();
  26.                         //往链表容器添加数据
  27.                         list.add(e);
  28.                         //把链表赋值给链表数组
  29.                         arr[a] = list;
  30.                 }else{
  31.                         /**
  32.                          * 不等于空，遍历key对象地址%数组的长度数组链表，如果链表存在相同key，则覆盖
  33.                          */
  34.                         for(int i=0;i<arr[a].size();i++){
  35.                                 SxtEntry e2 = (SxtEntry) arr[a].get(i); //链表添加进去是什么类型，取出来需要强制转型
  36.                                 if(e.key.equals(key)){
  37.                                         e2.value = value;
  38.                                         return ;  //键值重复 覆盖
  39.                                 }
  40.                         }
  41.                         /**
  42.                          * for循环没执行，代表key不相同，不相同直接往链表在添加一个数据
  43.                          */
  44.                         arr[a].add(e);
  45.                 }
  46.                 size++;
  47.         }
  48.        
  49.         public Object get(Object key){
  50.                 int a = key.hashCode()%arr.length;
  51.                 /**
  52.                  * 如果等于==null，代表没有链表，不需要遍历，直接返回空
  53.                  * 不都于需要遍历链表的存放的元素，如果有相等的key，则返回对应的value
  54.                  */
  55.                 if(arr[a] != null){
  56.                         for(int i=0;i<arr[a].size();i++){
  57.                                 SxtEntry e = (SxtEntry) arr[a].get(i);
  58.                                 if(e.key.equals(key)){
  59.                                         return e.value;
  60.                                 }
  61.                         }
  62.                 }
  63.                 return null;
  64.         }
  65. }
复制代码







欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2