【转】Java中HashMap的工作机制

2012-10-30  付民 

现在很多的Java程序员都会把HashMap当作一个热门话题，今天我也来说一说Hashmap。

　　我假设你对HashMap感兴趣，另外我认为你已经了解了HashMap的基础，这里我就不再赘述HashMap是个什么东东，如果对于你来讲HashMap还是一个新概念的话，你可以去看看官方的javadoc.

　　目录：

　　1、一句话回答

　　2、什么是哈希

　　3、关于Entry类的一点介绍

　　4、put()方法实际上做了什么

　　5、get()方法内部工作机制

　　6、注意点

　　一句话回答

　　如果任何人让我描述一下HashMap的工作机制的话，我就简单的回答：“基于Hash的规则”。这句话非常简单，但是要理解这句话之前，首先我们得了解什么是哈希，不是么？

　　什么是哈希

　　哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串，用这个串来确定变量/对象的唯一性。一个正确的哈希函数必须遵守这个准则。

　　当哈希函数应用在相同的对象或者equal的对象的时候，每次执行都应该返回相同的值。换句话说，两个相等的对象应该有相同的hashcode。

　　注：所有Java对象都从Object类继承了一个默认的hashCode()方法。这个方法将对象在内存中的地址作为整数返回，这是一个很好的hash实现，他确保了不同的对象拥有不同的hashcode。

　　关于Entry类的一点介绍

　　一个map的定义是：一个映射键（key）到值（value）的对象。非常简单对吧。

　　所以，在HashMap中一定有一定的机制来存储这些键值对。使得，HashMap有一个内部类Entry，看起来像这样。

  1. static class Entry<K,V> implements Map.Entry<K,V>   
  2. {  
  3.         final K key;  
  4.         V value;  
  5.         Entry<K,V> next;  
  6.         final int hash;  
  7.         ...//More code goes here 
  8. }

　　当然，Entry类有属性用来存储键值对映射。key被final标记，除了key和value，我们还能看到两个变量next和hash。接下来我们试着理解这些变量的含义。

　　put()方法实际上做了什么

　　再进一步看put方法的实现之前，我们有必要看一看Entry实例在数组中的存储，HashMap中是这样定义的：

  1. /** 
  2.      * The table, resized as necessary. Length MUST Always be a power of two. 
  3.      */ 
  4.     transient Entry[] table;

　　现在再来看put方法的实现。

  1. /** 
  2. * Associates the specified value with the specified key in this map. 
  3. * If the map previously contained a mapping for the key, the old 
  4. * value is replaced. 
  5. * 
  6. * @param key key with which the specified value is to be associated 
  7. * @param value value to be associated with the specified key 
  8. * @return the previous value associated with <tt>key</tt>, or 
  9. *&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tt>null</tt> if there was no mapping for <tt>key</tt>. 
  10. *&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (A <tt>null</tt> return can also indicate that the map 
  11. *&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; previously associated <tt>null</tt> with <tt>key</tt>.) 
  12. */ 
  13. public V put(K key, V value) {  
  14. if (key == null)  
  15. return putForNullKey(value);  
  16. int hash = hash(key.hashCode());  
  17. int i = indexFor(hash, table.length);  
  18. for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  19. Object k;  
  20. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  21. V oldValue = e.value;  
  22. e.value = value;  
  23. e.recordAccess(this);  
  24. return oldValue;  
  25. }  
  26. }  
  27. modCount++;  
  28. addEntry(hash, key, value, i);  
  29. return null;  
  30. }

让我们一步一步的看

　　首先，检查key是否为null，如果key是null值被存在table[0]的位置，因为null的hashcode始终为0接下来，通过key的hashCode()方法计算了这个key的hash值，这个hash值被用来计算存储Entry对象的数组中的位置。JDK的设计者假设会有一些人可能写出非常差的hashCode()方法，会出现一些非常大或者非常小的hash值。为了解决这个问题，他们引入了另外一个hash函数，接受对象的hashCode()，并转换到适合数组的容量大小。

　　接着是indexFor(hash,table,length)方法，这个方法计算了entry对象存储的准确位置。

　　接下来就是主要的部分，我们都知道两个不相等的对象可能拥有过相同的hashCode值，两个不同的对象是怎么存储在相同的位置[叫做bucket]呢？

　　答案是LinkedList。如果你记得，Entry类有一个next变量，这个变量总是指向链中的下一个变量，这完全符合链表的特点。

　　所以，在发生碰撞的时候，entry对象会被以链表的形式存储起来，当一个Entry对象需要被存储的时候，hashmap检查该位置是否已近有了一个entry对象，如果没有就存在那里，如果有了就检查她的next属性，如果是空，当前的entry对象就作为已经存储的entry对象的下一个节点，依次类推。

　　如果我们给已经存在的key存入另一个value会怎么样的？逻辑上，旧的值将被替换掉。在检测了Entry对象的存储位置后，hashmap将会遍历那个位置的entry链表，对每一个entry调用equals方法，这个链表中的所有对象都具有相同的hashCode()而equals方法都不等。如果发现equals方法有相等的就执行替换。

　　在这种方式下HashMap就能保证key的唯一性。

　　get方法的工作机制

　　现在我们已经了解了HashMap中存储键值对的机制。下一个问题是：怎样从一个HashMap中查询结果。

　　其实逻辑跟put是一样的，如果传入的key有匹配就将该位置的value返回，如果没有就返回null。

  1. /**  
  2. * Returns the value to which the specified key is mapped,  
  3. * or {@code null} if this map contains no mapping for the key.  
  4. *  
  5. * <p>More formally, if this map contains a mapping from a key  
  6. * {@code k} to a value {@code v} such that {@code (key==null ? k==null :  
  7. * key.equals(k))}, then this method returns {@code v}; otherwise  
  8. * it returns {@code null}.&nbsp; (There can be at most one such mapping.)  
  9. *  
  10. * <p>A return value of {@code null} does not <i>necessarily</i>  
  11. * indicate that the map contains no mapping for the key; it's also  
  12. * possible that the map explicitly maps the key to {@code null}.  
  13. * The {@link #containsKey containsKey} operation may be used to  
  14. * distinguish these two cases.  
  15. *  
  16. * @see #put(Object, Object)  
  17. */ 
  18. public V get(Object key) {  
  19. if (key == null)  
  20. return getForNullKey();  
  21. int hash = hash(key.hashCode());  
  22. for (Entry<K,V> e = table[indexFor(hash, table.length)];  
  23. e != null;  
  24. e = e.next) {  
  25. Object k;  
  26. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
  27. return e.value;  
  28. }  
  29. return null;  
  30. }

　　上面的代码看起来跟put()方法很像，除了if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。

　　注意点

　　存储Entry对象的数据结构是一个叫做Entry类型的table数组。

　　数组中一个特定的索引位置称为bucket,因为它可以容纳一个LinkedList的第一个元素的对象。

　　Key对象的hashCode()需要用来计算Entry对象的存储位置。

　　Key对象的equals()方法需要用来维持Map中对象的唯一性。

　　get()和put()方法跟Value对象的hashCode和equals方法无关。

　　null的hashCode总是0，这样的Entry对象总是被存储在数组的第一个位置。

332°/3324 人阅读/0 条评论 发表评论
请 登录 后发表评论
付民
访客 251411
付民 的其他博文 更多