您的位置: 首页  >  文章  >  360笔试题目-HashMap实现

360笔试题目-HashMap实现

分类: 文章 • 2024-11-13 09:59:28
自定义一个HashMap，实现map_put,map_delete,map_get方法，要求：

     1.查找时间复杂度O(1)

     2..

     3..

   因为Java中自带HashMap，平时直接用，也没有考虑，前一段时间只是实现了ArrayList，Vetor，Quene，并没有考虑HashMap。笔试的时候由于时间紧，我只是在HashMap中定义两个ArrayList，一个保存Key，一个保存Value，现在想想肯定是不对的，这根本没有按照要求实现。题目的原意是让实现链表，考察操作链表的能力。回来之后，我想了想，用Java实现了一般的链表：

     

[java] view plain copy
  1. <span style="font-size:14px;">/** 
  2.  *  
  3.  * @author lip 
  4.  * 用拉链法实现hashMap 
  5.  * 原理：hashmap中有一个链表数组 
  6.  *   一般数组的大小为一个素数 
  7.  */  
  8. public class HashMap<T1,T2>  
  9.     {  
  10.         private final int LENGTH=31;  
  11.         private Entry<T1, T2>[]table;  
  12.         private int size=0;  
  13.         public HashMap()  
  14.             {  
  15.                 table=new Entry[LENGTH];  
  16.             }  
  17.         //向hashMap插入值  
  18.         public void put(T1 key,T2 value)  
  19.         {  
  20.             size++;  
  21.             //求出T1的hash值，然后p=hash(key)%LENGTH，将key放在数组中p位置处的链表中  
  22.             //如果map中存在该值，那么更新该值  
  23.             //不存在该值，那么插在链表最后一个位置  
  24.             int pos=key.hashCode()%LENGTH;  
  25.             if(table[pos]==null)  
  26.                 {  
  27.                   table[pos]=new Entry<T1,T2>(key,value);  
  28.                   return;  
  29.                 }  
  30.             //遍历list，看key-value是否已经存在  
  31.             Entry<T1, T2> entry=table[pos];  
  32.             boolean exist=false;  
  33.             while (table[pos] != null)  
  34.                 {  
  35.                     if (table[pos].key == key)// 存在，更新就可以了  
  36.                         {  
  37.                             table[pos].value = value;  
  38.                             size--;  
  39.                             exist = true;  
  40.                             break;  
  41.                         }  
  42.                     if(table[pos].next==null)  
  43.                         break;  
  44.                     else table[pos] = table[pos].next;  
  45.                 }  
  46.             if(!exist)  
  47.                 table[pos].next=new Entry<T1,T2>(key,value);  
  48.             table[pos]=entry;  
  49.           
  50.         }  
  51.         //删除一个key  
  52.         public void delete(T1 key)  
  53.         {  
  54.             int pos=key.hashCode()%LENGTH;  
  55.             Entry<T1, T2> entry=table[pos];  
  56.             while(entry!=null)  
  57.                 {  
  58.                     if(entry.key==key)  
  59.                         {  
  60.                           //删除当前接节点  
  61.                             Entry<T1, T2>tempEntry=entry.next;  
  62.                             entry=entry.next;  
  63.                             if(entry!=null)  
  64.                                 entry.next=tempEntry.next;  
  65.                             size--;  
  66.                             break;  
  67.                         }  
  68.                     entry=entry.next;  
  69.                 }  
  70.         }  
  71.         //得到key的value  
  72.         public T2 getValue(T1 key)  
  73.         {  
  74.             int pos=key.hashCode()%LENGTH;  
  75.             Entry<T1, T2>entry=table[pos];  
  76.             while(entry!=null)  
  77.                 {  
  78.                     if(entry.key==key)  
  79.                         return entry.value;  
  80.                     entry=entry.next;  
  81.                 }  
  82.             return null;  
  83.         }  
  84.         //得到key的集合  
  85.         public Set<T1> getKeySet()  
  86.         {  
  87.             Set<T1> set=new HashSet<T1>();  
  88.             for(int i=0;i<LENGTH;i++)  
  89.                 {  
  90.                     Entry<T1, T2> entry=table[i];  
  91.                     while(entry!=null)  
  92.                         {  
  93.                            set.add(entry.key);  
  94.                            entry=entry.next;  
  95.                         }  
  96.                 }  
  97.             return set;  
  98.         }  
  99.         //得到map的大小  
  100.         public int size()  
  101.         {  
  102.             return size;  
  103.         }  
  104.         class Entry<T1,T2>  
  105.             {  
  106.                 private T1 key;  
  107.                 private T2 value;  
  108.                 public Entry<T1, T2>next;  
  109.                 public  Entry(T1 key,T2 value)  
  110.                 {  
  111.                     this.key=key;  
  112.                     this.value=value;  
  113.                 }  
  114.             }  
  115.         public static void main(String[] args)  
  116.             {  
  117.                 // TODO Auto-generated method stub  
  118.                 HashMap<String, Integer>hashMap=new HashMap<String, Integer>();  
  119.                 hashMap.put("语文", 82);  
  120.                 hashMap.put("数学", 99);  
  121.                 hashMap.put("英语", 90);  
  122.                 hashMap.put("物理", 88);  
  123.                 hashMap.put("化学", 93);  
  124.                 hashMap.put("生物", 86);  
  125.                 hashMap.put("生物", 88);  
  126.                 System.out.println("HashMap Size:"+hashMap.size());  
  127.                 System.out.println("生物："+hashMap.getValue("生物"));  
  128.                 System.out.println("语文："+hashMap.getValue("语文"));  
  129.                 Set<String> set=hashMap.getKeySet();  
  130.                 for(Iterator<String> iterator=set.iterator();iterator.hasNext();)  
  131.                     {  
  132.                         String key=iterator.next();  
  133.                         System.out.println(key+":"+hashMap.getValue(key));  
  134.                     }  
  135.             }  
  136.   
  137.     }</span>  
运行如图：

      360笔试题目-HashMap实现

相关推荐