一. HashMap的工作原理及实现
1． 如何实现一个Map
1.1 与Map相关的知识
1.1.1 Map.Entry接口
一个实现了Map.Entry接口的类代表的是一个Map中的条目（一个key-value pair）。所以一个Map中必须要有一个实现了Map.Entry接口的类，并用这个类来存放Map中的key-value pair。
1.1.2 public abstract Set entrySet()函数
1) entrySet()函数返回一个Set，并且Set中的每一个元素都是一个Map.Entry类型的对象。在entrySet()函数中要把Map中所有的key-value pair以Map.Entry封装后存入Set中的。
2) 当对Map进行修改操作后，entrySet()函数都会被调用。所以对Map的修改也会产生对这个Set的修改。
3) 当用这个Set的iterator进行操作时，不能进行add和addAll的操作。
1.2 实现一个简单的Map的实例
import java.util.*;
/**
* MPair类实现了Map.Entry
*/
class MPair
implements Map.Entry, Comparable{
Object key, value; //key和value分别用来存放Map中的key和value
MPair(Object k, Object v){
key = k;
value = v;
}
//下面方法实现了Map.Entry接口中的方法
public Object getKey() { return key; }
public Object getValue() { return value; }
public Object setValue(Object v){
Object result = value;
value = v;
return result;
}
//下面方法实现了Comparable接口中的方法
public boolean equals(Object o){
return key.equals(((MPair)o).key);
}
public int compareTo(Object rv){
return ((Comparable)key).compareTo(((MPair)rv).key);
}
}
class SlowMap extends AbstractMap{
private ArrayList
keys = new ArrayList(),
values = new ArrayList();
public Object put(Object key, Object value){
Object result = get(key);
if(!keys.contains(key)){ //（1）
keys.add(key);
values.add(value);
}
else
values.set(keys.indexOf(key), value);
return result;
}
public Object get(Object key){
if(!keys.contains(key)){
return null;
}
else
return values.get(keys.indexOf(key));
}
//用Mpair封装Map中的key-value pair并存入Set中
public Set entrySet(){
Set entries = new HashSet();
Iterator
ki = keys.iterator(),
vi = values.iterator();
while(ki.hasNext())
entries.add(new MPair(ki.next(), vi.next()));
return entries;
}
}
public class ExplicitStatic{
public static void main(String[] args){
SlowMap m = new SlowMap();
for( int i=1; i<10; i++)
m.put("km" + i, "m" + i);
System.out.println(m);
}
}
在上面代码的（1）处，我们要从ArrayList中查找出是否具有key值，而这个查找过程线性查找，且key不具任何顺序，所以速度会很慢。
1.3 如何对Map用迭代器进行操作
其它容器可以通过iterator()函数来生成对象的迭代器，但Map是不能生成的。如果要用迭代器对Map进行操作，则要通过entrySet()函数。用entrySet()函数生成的迭代器不能对Map进行add和addAll的操作。
public class ExplicitStatic{
public static void main(String[] args){
HashMap m = new HashMap();
for( int i=1; i<10; i++)
m.put("km" + i, "m" + i);
System.out.println("User for loop：");
for( int i=1; i<=m.size(); i++ )
System.out.println("km" + i + " = " + m.get("km" + i));
System.out.println("User Iterator loop：");
Iterator it = m.entrySet().iterator();
while(it.hasNext()){
Map.Entry entry = (Map.Entry)it.next();
System.out.println(entry.getKey() + " = " + entry.getValue());
}
}
}
2． 与HashMap相关的几个函数
1) hashCode()函数
Object.hashCode()函数会为对象产生hash code。如果一个类没有实现hashCode()函数，那么在缺省情况下将返回它的对象的内存地址。
2) equals()函数
Object.equals()在比较两个对象时，比较的是两个对象的内存地址。
3． HashMap的工作原理
3.1 用array来表现key的信息。每个key的hashCode()函数会为key产生一个hash code，而key的hash code作为array的索引。如假设有一个名为bucket的arrsy，姥一个hash code为2的key就被索引到bucket[2]，key所对应的值也在bucket[2]中。
3.1 由于array中存放的是value值，而HashMap的元素个数可以是无限的，所以array中的元素指向的不是某个key的value，而是指向具有相同的hash code的key的value值（也就是说指向的是一串values值）。如假设array被定义为LinkedList []bucket = new LinkedList[10]，那么bucket[2]中存放的是所有hash code值为2的key的value。
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 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-value pair的hash code
int index = key.hashCode() % SZ;
if(index < 0) index = - index;
if(bucket[index] == null)
bucket[index] = new LinkedList();
//通过hash code找出要插入的key所对应的array中的元素
LinkedList pairs = bucket[index];
//把要插入的key-value pair封装成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-value pair插入
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<bucket.length; 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);
}
} 
|
本类阅读TOP10