HashMap深度解析(一)

标签: hashmap 深度 解析 | 发表时间:2013-11-22 00:11 | 作者:ghsau
出处:http://blog.csdn.net

       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。 
       Object 类的 equals 方法实现对象上差别可能性最大的相等关系;即,对于任何非空引用值 x 和 y,当且仅当 x 和 y 引用同一个对象时,此方法才返回 true(x == y 具有值 true)。 当此方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。
       下面来说说hashCode方法,这个方法我们平时通常是用不到的,它是为哈希家族的集合类框架(HashMap、HashSet、HashTable)提供服务,hashCode 的常规协定是:
  • 在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。 
  • 如果根据 equals(Object) 方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。 
  • 以下情况不 是必需的:如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。
       当我们看到实现这两个方法有这么多要求时,立刻凌乱了,幸好有IDE来帮助我们,Eclipse中可以通过快捷键alt+shift+s调出快捷菜单,选择Generate hashCode() and equals(),根据业务需求,勾选需要生成的属性,确定之后,这两个方法就生成好了,我们通常需要在JavaBean对象中重写这两个方法。
       好了,这两个方法介绍完之后,我们回到HashMap,HashMap中我们最长用的就是put(K, V)和get(K),我们都知道,HashMap的K值是唯一的,那如何保证唯一性呢?我们首先想到的是用equals比较,没错,这样可以实现,那随着内部元素的增多,put和get的效率将越来越低,这里的时间复杂度是O(n),假如有1000个元素,put时需要比较1000次,实际上,HashMap很少会用到equals方法,因为其内通过一个哈希表管理所有元素,哈希是通过hash单词音译过来的,也可以称为散列表,哈希算法可以快速的存取元素,当我们调用put存值时,HashMap首先会调用K的hashCode方法,获取哈希码,通过哈希码快速找到某个存放位置,这个位置可以被称之为 bucketIndex,然后取到 bucketIndex位置已存储的元素,首先比较已有元素K和新元素K的hashCode,通过上面所述hashCode的协定可以知道, 如果hashCode不同,equals一定为false,如果hashCode相同,equals不一定为true。hashCode可能存在冲突的情况,有个专业名词叫 碰撞,两个不同的对象会产生同一个哈希码,equals方法就是哈希码碰撞时才会执行的方法,所以前面说HashMap很少会用到equals,通过hashCode和equals最终判断出K是否已存在,如果已存在,则使用新V值替换旧V值,并返回旧V值,如果不存在 ,则存放新的键值对<K, V>。这里可能有些疑问,为什么bucketIndex位置会已经有对象,这是因为由于某些情况下,不同的对象可能会产生相同的hash,这时hash相同,而对象不同,就会发生该情况了。文字描述有些乱,通过下面的流程图来整理一下整个put过程。

       现在我们知道,执行put方法后,最终HashMap的存储结构会有这三种情况,情形3是最少发生的,哈希码发生碰撞属于小概率事件。到目前为止,我们了解了两件事:
  • HashMap通过键的hashCode来快速的存取元素。
  • 当不同的对象hashCode发生碰撞时,HashMap通过单链表来解决,单链表在Java中的实现就是对象的引用(复合)。
       来鉴赏一下HashMap中put方法源码:
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存在的问题等等,这些会留在下一章说明。
       本文来自: 高爽|Coder,原文地址: http://blog.csdn.net/ghsau/article/details/16843543

作者:ghsau 发表于2013-11-22 0:11:04 原文链接
阅读:142 评论:0 查看评论

相关 [hashmap 深度 解析] 推荐:

HashMap深度解析(一)

- - CSDN博客编程语言推荐文章
       HashMap可以说是Java中最常用的集合类框架之一,是Java语言中非常典型的数据结构,我们总会在不经意间用到它,很大程度上方便了我们日常开发. 在很多Java的笔试题中也会被问到,最常见的,“HashMap和HashTable有什么区别. ”,这也不是三言两语能说清楚的,这种笔试题就是考察你来笔试之前有没有复习功课,随便来个快餐式的复习就能给出简单的答案.

深入解析Java对象的hashCode和hashCode在HashMap的底层数据结构的应用

- - 编程语言 - ITeye博客
对比对象实例的内存地址(也即对象实例的ID),来判断是否是同一对象实例;又可以说是判断对象实例是否物理相等;. 对比两个对象实例是否相等. 当对象所属的类没有重写根类Object的equals()方法时,equals()判断的是对象实例的ID(内存地址),是否是同一对象实例;该方法就是使用的等号(==)的判断结果.

java HashMap的原理

- - CSDN博客研发管理推荐文章
HashMap的数据结构:    在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外. HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体.    从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表.

深入理解HashMap

- - 你好IT
Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下. 网上关于hashmap的文章很多,但到底是自己学习的总结,就发出来跟大家一起分享,一起讨论. 1、hashmap的数据结构. 要知道hashmap是什么,首先要搞清楚它的数据结构,在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,hashmap也不例外.

Cookie深度解析

- - CSDN博客互联网推荐文章
       最近在公司做了Web端单点登录(SSO)功能,基于Cookie实现,做完之后感觉有必要总结一下,本文着重讲解Cookie,下文会说明单点登录的实现方案.        众所周知,Web协议(也就是HTTP)是一个无状态的协议. 一个Web应用由很多个Web页面组成,每个页面都有唯一的URL来定义.

Kafka深度解析

- - zzm
原创文章,转载请务必将下面这段话置于文章开头处. 本文转发自Jason’s Blog,原文链接. http://www.jasongj.com/2015/01/02/Kafka深度解析. Kafka是一种分布式的,基于发布/订阅的消息系统. 以时间复杂度为O(1)的方式提供消息持久化能力,即使对TB级以上数据也能保证常数时间的访问性能.

无锁HashMap的原理与实现

- - 酷壳 - CoolShell.cn
 (本文由 onetwogoo投稿). 在《 疫苗:Java HashMap的死循环》中,我们看到,java.util.HashMap并不能直接应用于多线程环境. 对于多线程环境中应用HashMap,主要有以下几种选择:. 使用线程安全的java.util.Hashtable作为替代. 使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的.

Java 8:HashMap的性能提升

- - Java译站
HashMap是一个高效通用的数据结构,它在每一个Java程序中都随处可见. 你可能也知道,HashMap使用key的hashCode()和equals()方法来将值划分到不同的桶里. 桶的数量通常要比map中的记录的数量要稍大,这样每个桶包括的值会比较少(最好是一个). 当通过key进行查找时,我们可以在常数时间内迅速定位到某个桶(使用hashCode()对桶的数量进行取模)以及要找的对象.

面试关于HashMap的工作原理

- - Java - 编程语言 - ITeye博客
几乎每个人都会回答“是的”,然后回答HashMap的一些特性,譬如HashMap可以接受null键值和值,而Hashtable则不 能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等. 这显示出你已经用过HashMap,而且 对它相当的熟悉. 但是面试官来个急转直下,从此刻开始问出一些刁钻的问题,关于HashMap的更多基础的细节.

深度解析电商供应链

- - 品途网
投身新时代的商业,你得学会从供应链出发看问题. 本文将告诉你:供应链管理由何而来;供应链是什么;在这个电商兴起的时代,供应链上哪些问题值得关注. 我们相信,从供应链的视角来观察商业流程,作为电商从业者的你,将会从中获得启发. 自20世纪中叶“科学管理”思想兴起以来,企业管理模式经历了从独立经营到纵向一体化,再到供应链管理的三个过程.