华为拿下的这个5G编码到底是什么 华为拿下的这个5G编码到底是什么
乐视危机虚实：贾跃亭，一个梦想 乐视危机虚实：贾跃亭，一个梦想
半个美国网络瘫痪让中国企业负责 半个美国网络瘫痪让中国企业负责

软件测试 > 测试开发技术 > 软件测试开发语言 > Java >

Java编程思想读书笔记－4（第9章-2HashMap的工作原理及其实现）

发表于：2007-05-25来源：作者：点击数： 标签：java编程读书9章-2HashMap
4．自己实现一个简单的HashMap及其原理 4.1在put()方法中： 1)首先通过key得出要插入的key-value pair的hash code，并这个hash code作为索引在数组bucket中找出key所对应的元素。 2)把要插入的key-value pair封装成实现了Map.Entry接口的类的一个对象。 3)在

4．    自己实现一个简单的HashMap及其原理


4.1    在put()方法中：
1)    首先通过key得出要插入的key-value　pair的hash　code，并这个hash　code作为索引在数组bucket中找出key所对应的元素。
2)    把要插入的key-value　pair封装成实现了Map.Entry接口的类的一个对象。
3)    在操作1）所找出的数组元素（也是一个LinkedList）中查看是否有与要插入的key-value　pair的key相同的元素，如果有，则对之进行更新；如果无，则把要插入的key-value　pair数组元素中。
4.2    在get()方法中
1)    首先通过key得出要查找的key-value　pair的hash　code，并这个hash　code作为索引在数组bucket中找出key所对应的元素。
2)    把要查找的key-value　pair的key封装成实现了Map.Entry接口的类的一个对象。
3)    在操作1）所找出的数组元素（也是一个LinkedList）中查看是否有与要插入的key-value　pair的key相同的元素，如果有，则返回key所对应的value；如果无，则返回一个null。
4.3    一个实例
  1. import java.util.*;
  2. /**
  3.  * MPair类实现了Map.Entry
  4.  */
  5. class MPair
  6.     implements Map.Entry, Comparable{
  7.     Object key, value;
  8.     MPair(Object k, Object v){
  9.         key = k;
  10.         value = v;
  11.     }
  12.     public Object getKey() { return key; }
  13.     public Object getValue() { return value; }
  14.     public Object setValue(Object v){
  15.         Object result = value;
  16.         value = v;
  17.         return result;
  18. }
  19.                 /**
  20.                   * 当比较两个MPair对象时，比较的是它们的key值
  21.                   */
  22.     public boolean equals(Object o){
  23.         return key.equals(((MPair)o).key);
  24.     }
  25.     public int compareTo(Object rv){
  26.         return (((Comparable)key).compareTo(((MPair)rv).key));
  27.     }
  28. }
  29. class SimpleHashMap extends AbstractMap{
  30.     private final static int SZ = 997;
  31.     private LinkedList[] bucket = new LinkedList[SZ];
  32.     /**
  33.      * 把key和value封装成Map.Entry的实现类后插入到array中
  34.      */
  35.     public Object put(Object key, Object value){
  36.         Object result = null;
  37.         //通过key得到要插入的key-value　pair的hash　code
  38.         int index = key.hashCode() % SZ;
  39.         if(index < 0) index = - index;
  40.         if(bucket[index] == null)
  41.             bucket[index] = new LinkedList();
  42.         //通过hash　code找出要插入的key所对应的array中的元素
  43.         LinkedList pairs = bucket[index];
  44.         //把要插入的key-value　pair封装成MPair
  45.         MPair pair = new MPair(key, value);
  46.         ListIterator it = pairs.listIterator();
  47.         boolean found = false;
  48.      //检查是否有与要插入的key相同的key存在，如果有，就对之进行更新
  49.         while(it.hasNext()){
  50.             Object iPair = it.next();
  51.             if(iPair.equals(iPair)){
  52.                 result = ((MPair)iPair).getValue();
  53.                 it.set(pair);
  54.                 found = true;
  55.                 break;
  56.             }
  57.         }
  58.         //如果无，则把新的key-value　pair插入
  59.         if(!found)
  60.             bucket[index].add(pair);
  61.         return result;
  62.     }
  63.     public Object get(Object key){
  64.         int index = key.hashCode() % SZ;
  65.         if(index < 0) index = -index;
  66.         if(bucket[index] == null) return null;
  67.         LinkedList pairs = bucket[index];
  68.         ListIterator it = pairs.listIterator();
  69.         MPair match = new MPair(key, null);
  70.         while(it.hasNext()){
  71.             Object iPair = it.next();
  72.             if(iPair.equals(match))
  73.                 return ((MPair)iPair).getValue();                
  74.         }
  75.         return null;
  76.     }
  77.     public Set entrySet(){
  78.         Set entries = new HashSet();
  79.         for(int i=0; i<bucket.length; i++){
  80.             if(bucket[i] == null) continue;
  81.             Iterator it = bucket[i].iterator();
  82.             while(it.hasNext())
  83.                 entries.add(it.next());
  84.         }
  85.         return entries;
  86.     }
  87. }
  88. public class ExplicitStatic{        
  89.     public static void main(String[] args){    
  90.         SimpleHashMap m = new SimpleHashMap();
  91.         for( int i=1; i<10; i++)
  92.             m.put("km" + i, "m" + i);
  93.         System.out.println(m);
  94.     }
  95. }

四.    HashMap的一些其它讨论

1．    关于HashMap中的key值的使用
1.1.    以Java的库函数做为HashMap的key值时，可以直接使用。
  1. import java.util.*;
  2. class Counter{
  3.     int i = 1;
  4.     public String toString(){
  5.         return Integer.toString(i);
  6.     }
  7. }
  8. public class ExplicitStatic{   
  9.     public static void main(String[] args){
  10.         HashMap hm = new HashMap();
  11.         for(int i = 0; i < 10000; i++)
  12.         {
  13.             //HashMap的key的类型为Integer
  14.             Integer r = new Integer((int) (Math.random() * 20));
  15.             if(hm.containsKey(r))
  16.                 ((Counter)hm.get(r)).i++;
  17.             else
  18.                 hm.put(r, new Counter());
  19.         }
  20.         System.out.println(hm);
  21.     }
  22. }

1.2.    如果在HashMap中使用你自己撰写的classes做为key，你一定得同时覆写hashCode()和equals()。
下面代码用自己实现的class做为key，但没有覆写hashCode()和equals()。
  1. import java.util.*;
  2. class Groundhog{
  3.             int ghNumber;
  4.             Groundhog(int n) { ghNumber = n; }
  5.             public String toString(){
  6.                 return "Groundhog@" + ghNumber;
  7.             }
  8. }
  9. class Prediction{
  10.             boolean shadow = Math.random() > 0.5;
  11.             public String toString(){
  12.                 if(shadow)
  13.                     return "Six more weeks of Winter!\n";
  14.                 else
  15.                     return "Early Spring!\n";
  16.             }
  17. }        
  18. public class Test{   
  19.             public static void main(String[] args){
  20.                 HashMap hm = new HashMap();
  21.                 for(int i = 1; i < 10; i++)
  22.                     hm.put(new Groundhog(i), new Prediction());
  23.                 System.out.println("hm = " + hm);
  24.                 System.out.println("Looking up prediction for Groundhog #3:");
  25.                 Groundhog gh = new Groundhog(3);
  26.                 if(hm.containsKey(gh)) 　//（1）
  27.                     System.out.println((Prediction)hm.get(gh)); 
  28.                 else
  29.                     System.out.println("Key not found: " + gh);
  30.             }
  31. }

运行结果：
hm = {Groundhog@9=Early Spring!
, Groundhog@8=Six more weeks of Winter!
, Groundhog@7=Six more weeks of Winter!
, Groundhog@6=Early Spring!
, Groundhog@5=Early Spring!
, Groundhog@4=Early Spring!
, Groundhog@3=Early Spring!
, Groundhog@2=Early Spring!
, Groundhog@1=Six more weeks of Winter!
}
Looking up prediction for Groundhog #3:
Key not found: Groundhog@3
key没覆写hashCode()和equals()，那么在通过key取得hash　code时，就会取得key的内存地址；同样，当通过equals()函数比较两个key是否相等时，比较的也是两个key的地址。所以（1）处代码比较的结果为false（因为两个对象的内存地址肯定是不相同的）。显然，这不是我们要得到的结果。
为了要得到正确的结果，我们只需在作为key的类中实现hashCode()和equals()。
  1. java.util.*;
  2. class Groundhog2{
  3.             int ghNumber;
  4.             Groundhog2(int n) { ghNumber = n; }
  5.             public String toString(){
  6.                 return "Groundhog2@" + ghNumber;
  7.             }
  8.             /**
  9.          * 以ghNumber作为hash　code
  10.          */
  11.             public int hashCode() { return ghNumber; }
  12.             /**
  13.          *比较的是两个key的ghNumber值
  14.          */
  15.             public boolean equals(Object o)
  16.             {
  17.                 return (o instanceof Groundhog2) 
  18.                     && (ghNumber == ((Groundhog2)o).ghNumber);
  19.             }
  20. }
  21. class Prediction{
  22.             boolean shadow = Math.random() > 0.5;
  23.             public String toString(){
  24.                 if(shadow)
  25.                     return "Six more weeks of Winter!\n";
  26.                 else
  27.                     return "Early Spring!\n";
  28.             }
  29. }
  30. public class Test{   
  31.             public static void main(String[] args){
  32.                 HashMap hm = new HashMap();
  33.                 for(int i = 1; i < 10; i++)
  34.                     hm.put(new Groundhog2(i), new Prediction());
  35.                 System.out.println("size = " + hm.size() + " , hm = " + hm);
  36.                 System.out.println("Looking up prediction for Groundhog #3:");
  37.                 Groundhog2 gh = new Groundhog2(2);
  38.                 if(hm.containsKey(gh))
  39.                     System.out.println((Prediction)hm.get(gh));
  40.                 else
  41.                     System.out.println("Key not found: " + gh);
  42.             }
  43. }

运行结果为：
hm = {Groundhog2@9=Early Spring!
, Groundhog2@8=Six more weeks of Winter!
, Groundhog2@7=Six more weeks of Winter!
, Groundhog2@6=Six more weeks of Winter!
, Groundhog2@5=Early Spring!
, Groundhog2@4=Early Spring!
, Groundhog2@3=Six more weeks of Winter!
, Groundhog2@2=Early Spring!
, Groundhog2@1=Early Spring!
}
Looking up prediction for Groundhog #3:
Early Spring!
在新的代码中，我们在作为key的类中实现了hashCode()和equals()函数，得到了想要的结果。
2．    HashMap的效能因子
Capacity：容量，表格中的buckets数量
Initial　capacity：初始容量，表格建立之初的buckets数量。
HashMap和HashSet：各有构造函数，允许指定初始容量。
Size：大小，表格内目前所有的条目。
Load factor：负载因子，size / capacity（大小/容量）。负载因子为0，表示一个空表格，0.5是一个半满表格，依此类推。一个轻负载表格出现碰撞（collisions）的机会比较低，比较适合安插和查找（但会降低“通过迭代器巡访”的速度）。在HashMap和HashSet各有构造函数中指定了负载因子后，当容器达到这个负载因子，容器的容量（buckets个数）就会自动扩充，并将原有的对象重新导入到新的buckets内（这称为rechashing）。HashMap缺省的负载因子值是0.75。

原文转自：http://www.ltesting.net

评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）

相关文章

软件测试沙龙 More>>

新浪微博More>>

...

热门标签