4． 自己實現(xiàn)一個簡單的HashMap及其原理

　　 4.1 在put()方法中：

　　 1) 首先通過key得出要插入的key-valuepair的hashcode，并這個hashcode作為索引在數(shù)組bucket中找出key所對應(yīng)的元素。

　　 2) 把要插入的key-valuepair封裝成實現(xiàn)了Map.Entry接口的類的一個對象。

　　 3) 在操作1）所找出的數(shù)組元素（也是一個LinkedList）中查看是否有與要插入的key-valuepair的key相同的元素，如果有，則對之進行更新；如果無，則把要插入的key-valuepair數(shù)組元素中。

　　 4.2 在get()方法中

　　 1) 首先通過key得出要查找的key-valuepair的hashcode，并這個hashcode作為索引在數(shù)組bucket中找出key所對應(yīng)的元素。

　　 2) 把要查找的key-valuepair的key封裝成實現(xiàn)了Map.Entry接口的類的一個對象。

　　 3) 在操作1）所找出的數(shù)組元素（也是一個LinkedList）中查看是否有與要插入的key-valuepair的key相同的元素，如果有，則返回key所對應(yīng)的value；如果無，則返回一個null。

　　 4.3 一個實例

　　 import java.util.*;
　　 /**
　　 * MPair類實現(xiàn)了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的實現(xiàn)類后插入到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所對應(yīng)的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． 關(guān)于HashMap中的key值的使用

　　 1.1. 以Java的庫函數(shù)做為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);
　　 }
　　 }