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