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    一个实例

import java.util.*;
/**
* MPair类实现了Map.Entry
*/
class MPair
implements java/util/Map.java.html" target="_blank">Map.Entry, java/lang/Comparable.java.html" target="_blank">Comparable{
java/lang/Object.java.html" target="_blank">Object key, value;
MPair(java/lang/Object.java.html" target="_blank">Object k, java/lang/Object.java.html" target="_blank">Object v){
key = k;
value = v;
}
public java/lang/Object.java.html" target="_blank">Object getKey() { return key; }
public java/lang/Object.java.html" target="_blank">Object getValue() { return value; }
public java/lang/Object.java.html" target="_blank">Object setValue(java/lang/Object.java.html" target="_blank">Object v){
java/lang/Object.java.html" target="_blank">Object result = value;
value = v;
return result;
}
/**
* 当比较两个MPair对象时，比较的是它们的key值
*/
public boolean equals(java/lang/Object.java.html" target="_blank">Object o){
return key.equals(((MPair)o).key);
}
public int compareTo(java/lang/Object.java.html" target="_blank">Object rv){
return (((java/lang/Comparable.java.html" target="_blank">Comparable)key).compareTo(((MPair)rv).key));
}
}
class SimpleHashMap extends java/util/AbstractMap.java.html" target="_blank">AbstractMap{
private final static int SZ = 997;
private java/util/LinkedList.java.html" target="_blank">LinkedList[] bucket = new java/util/LinkedList.java.html" target="_blank">LinkedList[SZ];
/**
* 把key和value封装成Map.Entry的实现类后插入到array中
*/
public java/lang/Object.java.html" target="_blank">Object put(java/lang/Object.java.html" target="_blank">Object key, java/lang/Object.java.html" target="_blank">Object value){
java/lang/Object.java.html" target="_blank">Object result = null;
//通过key得到要插入的key-value　pair的hash　code
int index = key.hashCode() % SZ;
if(index < 0) index = - index;
if(bucket[index] == null)
bucket[index] = new java/util/LinkedList.java.html" target="_blank">LinkedList();
//通过hash　code找出要插入的key所对应的array中的元素
java/util/LinkedList.java.html" target="_blank">LinkedList pairs = bucket[index];
//把要插入的key-value　pair封装成MPair
MPair pair = new MPair(key, value);
java/util/ListIterator.java.html" target="_blank">ListIterator it = pairs.listIterator();
boolean found = false;
//检查是否有与要插入的key相同的key存在，如果有，就对之进行更新
while(it.hasNext()){
java/lang/Object.java.html" target="_blank">Object iPair = it.next();
if(iPair.equals(iPair)){
result = ((MPair)iPair).getValue();
it.set(pair);
found = true;
break;
}
}
//如果无，则把新的key-value　pair插入
if(!found)
bucket[index].add(pair);
return result;
}
public java/lang/Object.java.html" target="_blank">Object get(java/lang/Object.java.html" target="_blank">Object key){
int index = key.hashCode() % SZ;
if(index < 0) index = -index;
if(bucket[index] == null) return null;
java/util/LinkedList.java.html" target="_blank">LinkedList pairs = bucket[index];
java/util/ListIterator.java.html" target="_blank">ListIterator it = pairs.listIterator();
MPair match = new MPair(key, null);
while(it.hasNext()){
java/lang/Object.java.html" target="_blank">Object iPair = it.next();
if(iPair.equals(match))
return ((MPair)iPair).getValue();
}
return null;
}
public java/util/Set.java.html" target="_blank">Set entrySet(){
java/util/Set.java.html" target="_blank">Set entries = new java/util/HashSet.java.html" target="_blank">HashSet();
for(int i=0; i<bucket.length; i++){
if(bucket[i] == null) continue;
java/util/Iterator.java.html" target="_blank">Iterator it = bucket[i].iterator();
while(it.hasNext())
entries.add(it.next());
}
return entries;
}
}
public class ExplicitStatic{
public static void main(java/lang/String.java.html" target="_blank">String[] args){
SimpleHashMap m = new SimpleHashMap();
for( int i=1; i<10; i++)
m.put("km" + i, "m" + i);
java/lang/System.java.html" target="_blank">System.out.println(m);
}
}

四. HashMap的一些其它讨论

1．关于HashMap中的key值的使用
1.1. 以Java的库函数做为HashMap的key值时，可以直接使用。

import java.util.*;
class Counter{
int i = 1;
public java/lang/String.java.html" target="_blank">String toString(){
return java/lang/Integer.java.html" target="_blank">Integer.toString(i);
}
}
public class ExplicitStatic{
public static void main(java/lang/String.java.html" target="_blank">String[] args){
java/util/HashMap.java.html" target="_blank">HashMap hm = new java/util/HashMap.java.html" target="_blank">HashMap();
for(int i = 0; i < 10000; i++)
{
//HashMap的key的类型为Integer
java/lang/Integer.java.html" target="_blank">Integer r = new java/lang/Integer.java.html" target="_blank">Integer((int) (java/lang/Math.java.html" target="_blank">Math.random() * 20));
if(hm.containsKey(r))
((Counter)hm.get(r)).i++;
else
hm.put(r, new Counter());
}
java/lang/System.java.html" target="_blank">System.out.println(hm);
}
}

1.2. 如果在HashMap中使用你自己撰写的classes做为key，你一定得同时覆写hashCode()和equals()。
下面代码用自己实现的class做为key，但没有覆写hashCode()和equals()。

import java.util.*;
class Groundhog{
int ghNumber;
Groundhog(int n) { ghNumber = n; }
public java/lang/String.java.html" target="_blank">String toString(){
return "Groundhog@" + ghNumber;
}
}
class Prediction{
boolean shadow = java/lang/Math.java.html" target="_blank">Math.random() > 0.5;
public java/lang/String.java.html" target="_blank">String toString(){
if(shadow)
return "Six more weeks of Winter!\n";
else
return "Early Spring!\n";
}
}
public class Test{
public static void main(java/lang/String.java.html" target="_blank">String[] args){
java/util/HashMap.java.html" target="_blank">HashMap hm = new java/util/HashMap.java.html" target="_blank">HashMap();
for(int i = 1; i < 10; i++)
hm.put(new Groundhog(i), new Prediction());
java/lang/System.java.html" target="_blank">System.out.println("hm = " + hm);
java/lang/System.java.html" target="_blank">System.out.println("Looking up prediction for Groundhog #3:");
Groundhog gh = new Groundhog(3);
if(hm.containsKey(gh)) 　//（1）
java/lang/System.java.html" target="_blank">System.out.println((Prediction)hm.get(gh));
else
java/lang/System.java.html" target="_blank">System.out.println("Key not found: " + gh);
}
}

运行结果：
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()。

java.util.*;
class Groundhog2{
int ghNumber;
Groundhog2(int n) { ghNumber = n; }
public java/lang/String.java.html" target="_blank">String toString(){
return "Groundhog2@" + ghNumber;
}
/**
* 以ghNumber作为hash　code
*/
public int hashCode() { return ghNumber; }
/**
*比较的是两个key的ghNumber值
*/
public boolean equals(java/lang/Object.java.html" target="_blank">Object o)
{
return (o instanceof Groundhog2)
&& (ghNumber == ((Groundhog2)o).ghNumber);
}
}
class Prediction{
boolean shadow = java/lang/Math.java.html" target="_blank">Math.random() > 0.5;
public java/lang/String.java.html" target="_blank">String toString(){
if(shadow)
return "Six more weeks of Winter!\n";
else
return "Early Spring!\n";
}
}
public class Test{
public static void main(java/lang/String.java.html" target="_blank">String[] args){
HashMap hm = new HashMap();
for(int i = 1; i < 10; i++)
hm.put(new Groundhog2(i), new Prediction());
java/lang/System.java.html" target="_blank">System.out.println("size = " + hm.size() + " , hm = " + hm);
java/lang/System.java.html" target="_blank">System.out.println("Looking up prediction for Groundhog #3:");
Groundhog2 gh = new Groundhog2(2);
if(hm.containsKey(gh))
java/lang/System.java.html" target="_blank">System.out.println((Prediction)hm.get(gh));
else
java/lang/System.java.html" target="_blank">System.out.println("Key not found: " + gh);
}
}

运行结果为：
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。

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

四. HashMap的一些其它讨论

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