当前页面: 开发资料首页 → Java 专题 → Java编程思想（2nd）学习笔记（9）-2
Java编程思想（2nd）学习笔记（9）-2
摘要: Java编程思想（2nd）学习笔记（9）-2
一. 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
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);
↑返回目录
前一篇: Java编程思想（2nd）学习笔记（9）-3
后一篇: Java编程思想（2nd）学习笔记（9）-1