明辉站/网站教程/内容

Java编程思想读书笔记(9.2章)

网站教程2024-05-19 阅读
[摘要]4. 自己实现一个简单的HashMap及其原理    4.1 在put()方法中:    1) 首先通过key得出要插入的key-valuepair的hashcode,并这个hashcode作为索引在数组bucket中找出key所对应的元素。    2) 把要插入的key-valuepair封装成...
4. 自己实现一个简单的HashMap及其原理

   4.1 在put()方法中:

   1) 首先通过key得出要插入的key-valuepair的hashcode,并这个hashcode作为索引在数组bucket中找出key所对应的元素。

   2) 把要插入的key-valuepair封装成实现了Map.Entry接口的类的一个对象。

   3) 在操作1)所找出的数组元素(也是一个LinkedList)中查看是否有与要插入的key-valuepair的key相同的元素,如果有,则对之进行更新;如果无,则把要插入的key-valuepair数组元素中。

   4.2 在get()方法中

   1) 首先通过key得出要查找的key-valuepair的hashcode,并这个hashcode作为索引在数组bucket中找出key所对应的元素。

   2) 把要查找的key-valuepair的key封装成实现了Map.Entry接口的类的一个对象。

   3) 在操作1)所找出的数组元素(也是一个LinkedList)中查看是否有与要插入的key-valuepair的key相同的元素,如果有,则返回key所对应的value;如果无,则返回一个null。

   4.3 一个实例

   import java.util.*;
   /**
   * MPair类实现了Map.Entry
   */
   class MPair
   implements Map.Entry, Comparable{
   Object key, value;
   MPair(Object k, Object v){
   key = k;
   value = v;
   }
   public Object getKey() { return key; }
   public Object getValue() { return value; }
   public Object setValue(Object v){
   Object result = value;
   value = v;
   return result;
   }
   /**
   * 当比较两个MPair对象时,比较的是它们的key值
   */
   public boolean equals(Object o){
   return key.equals(((MPair)o).key);
   }
   public int compareTo(Object rv){
   return (((Comparable)key).compareTo(((MPair)rv).key));
   }
   }
   class SimpleHashMap extends AbstractMap{
   private final static int SZ = 997;
   private LinkedList[] bucket = new LinkedList[SZ];
   /**
   * 把key和value封装成Map.Entry的实现类后插入到array中
   */
   public Object put(Object key, Object value){
   Object result = null;
   //通过key得到要插入的key-valuepair的hashcode
   int index = key.hashCode() % SZ;
   if(index < 0) index = - index;
   if(bucket[index] == null)

   bucket[index] = new LinkedList();
   //通过hashcode找出要插入的key所对应的array中的元素
   LinkedList pairs = bucket[index];
   //把要插入的key-valuepair封装成MPair
   MPair pair = new MPair(key, value);
   ListIterator it = pairs.listIterator();
   boolean found = false;
   //检查是否有与要插入的key相同的key存在,如果有,就对之进行更新
   while(it.hasNext()){
   Object iPair = it.next();
   if(iPair.equals(iPair)){
   result = ((MPair)iPair).getValue();
   it.set(pair);
   found = true;
   break;
   }
   }
   //如果无,则把新的key-valuepair插入
   if(!found)

   bucket[index].add(pair);
   return result;
   }
   public Object get(Object key){
   int index = key.hashCode() % SZ;
   if(index < 0) index = -index;
   if(bucket[index] == null) return null;
   LinkedList pairs = bucket[index];
   ListIterator it = pairs.listIterator();
   MPair match = new MPair(key, null);
   while(it.hasNext()){
   Object iPair = it.next();
   if(iPair.equals(match))

   return ((MPair)iPair).getValue();
   }
   return null;
   }
   public Set entrySet(){
   Set entries = new HashSet();
   for(int i=0; i
   if(bucket[i] == null) continue;
   Iterator it = bucket[i].iterator();
   while(it.hasNext())

   entries.add(it.next());
   }
   return entries;
   }
   }
   public class ExplicitStatic{
   public static void main(String[] args){
   SimpleHashMap m = new SimpleHashMap();
   for( int i=1; i<10; i++)

   m.put("km" + i, "m" + i);
   System.out.println(m);
   }
   }
   四. HashMap的一些其它讨论

   1. 关于HashMap中的key值的使用

   1.1. 以Java的库函数做为HashMap的key值时,可以直接使用。

   import java.util.*;
   class Counter{
   int i = 1;
   public String toString(){
   return Integer.toString(i);
   }
   }
   public class ExplicitStatic{
   public static void main(String[] args){
   HashMap hm = new HashMap();
   for(int i = 0; i < 10000; i++)

   {
   //HashMap的key的类型为Integer
   Integer r = new Integer((int) (Math.random() * 20));
   if(hm.containsKey(r))

   ((Counter)hm.get(r)).i++;

   else
   hm.put(r, new Counter());
   }
   System.out.println(hm);
   }
   }

……

相关阅读