Java编程思想读书笔记（9.2章）

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);
　　 }
　　 }

……