本文来自:高爽|Coder,原文地址:http://blog.csdn.net/ghsau/article/details/16843543,转载请注明。
HashMap可以说是Java中最常用的集合类框架之一,是Java语言中非常典型的数据结构,我们总会在不经意间用到它,很大程度上方便了我们日常开发。在很多Java的笔试题中也会被问到,最常见的,“HashMap和HashTable有什么区别?”,这也不是三言两语能说清楚的,这种笔试题就是考察你来笔试之前有没有复习功课,随便来个快餐式的复习就能给出简单的答案。
HashMap计划写两篇文章,一篇是HashMap工作原理,也就是本文,另一篇是多线程下的HashMap会引发的问题。这一年文章写的有点少,工作上很忙,自己业余时间也做点东西,就把博客的时间占用了,以前是力保一周一篇文章,有点给自己任务的意思,搞的自己很累,文章质量也不高,有时候写技术文章也是需要灵感的,为了举一个例子可能要绞尽脑汁,为了一段代码可能要验证好多次,现在想通了,有灵感再写,需要一定的积累,才能把自己了解的知识点总结归纳成文章。
言归正传,了解HashMap之前,我们需要知道Object类的两个方法hashCode和equals,我们先来看一下这两个方法的默认实现:
/** JNI,调用底层其它语言实现 */ public native int hashCode(); /** 默认同==,直接比较对象 */ public boolean equals(Object obj) { return (this == obj); }
equals方法我们太熟悉了,我们经常用于字符串比较,String类中重写了equals方法,比较的是字符串值,看一下源码实现:
public boolean equals(Object anObject) { if (this == anObject) { return true; } if (anObject instanceof String) { String anotherString = (String) anObject; int n = value.length; if (n == anotherString.value.length) { char v1[] = value; char v2[] = anotherString.value; int i = 0; // 逐个判断字符是否相等 while (n-- != 0) { if (v1[i] != v2[i]) return false; i++; } return true; } } return false; }
重写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 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。
- 如果根据 equals(Object) 方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
- 以下情况不 是必需的:如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。
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
,则存放新的键值对<K, V>到bucketIndex位置。文字描述有些乱,通过下面的流程图来梳理一下整个put过程。
- HashMap通过键的hashCode来快速的存取元素。
- 当不同的对象hashCode发生碰撞时,HashMap通过单链表来解决,将新元素加入链表表头,通过next指向原有的元素。单链表在Java中的实现就是对象的引用(复合)。
public V put(K key, V value) { // 处理key为null,HashMap允许key和value为null if (key == null) return putForNullKey(value); // 得到key的哈希码 int hash = hash(key); // 通过哈希码计算出bucketIndex int i = indexFor(hash, table.length); // 取出bucketIndex位置上的元素,并循环单链表,判断key是否已存在 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 哈希码相同并且对象相同时 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 新值替换旧值,并返回旧值 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // key不存在时,加入新元素 modCount++; addEntry(hash, key, value, i); return null; }
到这里,我们了解了HashMap工作原理的一部分,那还有另一部分,如,加载因子及rehash,HashMap通常的使用规则,多线程并发时HashMap存在的问题等等,这些会留在下一章说明。