HashMap深度解析（一）

  HashMap可以说是Java中最常用的集合类框架之一，是Java语言中非常典型的数据结构，我们总会在不经意间用到它，很大程度上方便了我们日常 开发。在很多Java的笔试题中也会被问到，最常见的，“HashMap和HashTable有什么区别？”，这也不是三言两语能说清楚的，这种笔试题就 是考察你来笔试之前有没有复习功课，随便来个快餐式的复习就能给出简单的答案。
       HashMap计划写两篇文章，一篇是HashMap工作原理，也就是本文，另一篇是多线程下的HashMap会引发的问题。这一年文章写的有点少，工 作上很忙，自己业余时间也做点东西，就把博客的时间占用了，以前是力保一周一篇文章，有点给自己任务的意思，搞的自己很累，文章质量也不高，有时候写技术 文章也是需要灵感的，为了举一个例子可能要绞尽脑汁，为了一段代码可能要验证好多次，现在想通了，有灵感再写，需要一定的积累，才能把自己了解的知识点总 结归纳成文章。
       言归正传，了解HashMap之前，我们需要知道Object类的两个方法hashCode和equals，我们先来看一下这两个方法的默认实现：

[java] view plain copy print?

1. /** JNI，调用底层其它语言实现 */  
2. public native int hashCode();  
3.   
4. /** 默认同==，直接比较对象 */  
5. public boolean equals(Object obj) {  
6.     return (this == obj);  
7. }  

       equals方法我们太熟悉了，我们经常用于字符串比较，String类中重写了equals方法，比较的是字符串值，看一下源码实现：

[java] view plain copy print?

1. public boolean equals(Object anObject) {  
2.     if (this == anObject) {  
3.         return true;  
4.     }  
5.     if (anObject instanceof String) {  
6.         String anotherString = (String) anObject;  
7.         int n = value.length;  
8.         if (n == anotherString.value.length) {  
9.             char v1[] = value;  
10.             char v2[] = anotherString.value;  
11.             int i = 0;  
12.             // 逐个判断字符是否相等  
13.             while (n-- != 0) {  
14.                 if (v1[i] != v2[i])  
15.                         return false;  
16.                 i++;  
17.             }  
18.             return true;  
19.         }  
20.     }  
21.     return false;  
22. }  

       重写equals要满足几个条件：

• 自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。 
• 对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。 
• 传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。 
• 一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。 
• 对于任何非空引用值 x，x.equals(null) 都应返回 false。 

java.util
类 HashMap<K,V>

java.lang.Object
  

java.util.AbstractMap<K,V>
      

java.util.HashMap<K,V>

所有已实现的接口：

Serializable, Cloneable, Map<K,V>

直接已知子类：

LinkedHashMap, PrinterStateReasons

[java] view plain copy print?

1. public V put(K key, V value) {  
2.     // 处理key为null，HashMap允许key和value为null  
3.     if (key == null)  
4.         return putForNullKey(value);  
5.     // 得到key的哈希码  
6.     int hash = hash(key);  
7.     // 通过哈希码计算出bucketIndex  
8.     int i = indexFor(hash, table.length);  
9.     // 取出bucketIndex位置上的元素，并循环单链表，判断key是否已存在  
10.     for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
11.         Object k;  
12.         // 哈希码相同并且对象相同时  
13.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
14.             // 新值替换旧值，并返回旧值  
15.             V oldValue = e.value;  
16.             e.value = value;  
17.             e.recordAccess(this);  
18.             return oldValue;  
19.         }  
20.     }  
21.   
22.     // key不存在时，加入新元素  
23.     modCount++;  
24.     addEntry(hash, key, value, i);  
25.     return null;  
26. }  

       到这里，我们了解了HashMap工作原理的一部分，那还有另一部分，如，加载因子及rehash，HashMap通常的使用规则，多线程并发时HashMap存在的问题等等，这些会留在下一章说明。

       本文来自：高爽|Coder，原文地址：http://blog.csdn.net/ghsau/article/details/16843543，转载请注明。