ITPub博客

首页 > Linux操作系统 > Linux操作系统 > [转载]Java编程思想读书笔记-4(第9章-2HashMap的工作原理及其实现)

[转载]Java编程思想读书笔记-4(第9章-2HashMap的工作原理及其实现)

原创 Linux操作系统 作者:dinner1007 时间:2019-05-21 08:48:04 0 删除 编辑
Java编程思想读书笔记-4(第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) 在操作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; ilength; 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! ";
  14. else
  15. return "Early Spring! ";
  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! ";
  26. else
  27. return "Early Spring! ";
  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。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/374079/viewspace-130815/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2018-08-23

  • 博文量
    1455
  • 访问量
    1075470