hashmap源码深度解析_redis的hash数据结构

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

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

       本文来自:高爽|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。 
       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是最常用的集合类框架之一,它实现了Map接口,所以存储的元素也是键值对映射的结构,并允许使用null值和null键,其内元素是无序的,如果要保证有序,可以使用LinkedHashMap。HashMap是线程不安全的,下篇文章会讨论。HashMap的类关系如下:

java.util
Class HashMap<K,V>

java.lang.Object
  |--java.util.AbstractMap<K,V>
      |--java.util.HashMap<K,V>

所有已实现的接口:

Serializable,Cloneable,Map<K,V>

直接已知子类:

LinkedHashMap,PrinterStateReasons

       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,有个专业名词叫
碰撞,当碰撞发生时,这时会取到
bucketIndex位置已存储的元素,最终通过equals来比较,equals方法就是碰撞时才会执行的方法,所以前面说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在,如果已存在,则使用新V值替换旧V值,并返回旧V值,如果不存在 ,则存放新的键值对<K, V>到
bucketIndex位置。文字描述有些乱,通过下面的流程图来梳理一下整个put过程。
hashmap源码深度解析_redis的hash数据结构
       现在我们知道,执行put方法后,最终HashMap的存储结构会有这三种情况,我们当然期望情形3是最少发生的(效率最低)。到目前为止,我们了解了两件事:
  • HashMap通过键的hashCode来快速的存取元素。
  • 当不同的对象发生碰撞时,HashMap通过单链表来解决,将新元素加入链表表头,通过next指向原有的元素。单链表在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,转载请注明。

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195181.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • zabbix 监控介绍「建议收藏」

    zabbix 监控介绍「建议收藏」一、监控介绍你用过哪些监控软件?zabbix和nagios、cacti、ganglia有什么区别?zabbix有那些好处?zabbix的监控流程是什么?zabbix常见监控项有那些?1、CactiCacti是一套基于PHP、MySQL、SNMP及RRDTool开发的监测图形分析工具,Cacti是使用轮询的方式由主服务器向设备发送数据请求来获取设备上状态数据信息的,如果设备不断增多,这个轮询的过程就非常的耗时,轮询的结果就不能即时的反应设备的状态

  • CSV文件太大打不开进行分割、和打开乱码问题[通俗易懂]

    CSV文件太大打不开进行分割、和打开乱码问题[通俗易懂]CSV文件打开以及乱码问题今天要使用一个csv文件,但是有8个G,excel打不开,用Python的pandas也读不了,可能是我电脑配置太落后,也可能是数据实在太大了。解决办法:首先处理打不开的问题,我们可以把大的csv分割成若干小文件,使用文件分割器,按10000行一个文件分割,分割器在F:\新建文件夹\csv文件分割器\split.exe,稍等一段时间就行。我还试过另一个分割器,但是不行…

  • java通过jdbc连接sql server数据库_mysqljdbc连接数据库代码

    java通过jdbc连接sql server数据库_mysqljdbc连接数据库代码文章目录一、需求二、项目结构三、步骤1、创建数据库、数据表,插入数据2、创建javaweb项目3、下载驱动包4、导入驱动包5、创建包,创建类6、程序7、运行结果一、需求创建一个javaweb项目,读取bookinfo表中的数据,并输出到控制台二、项目结构JDBC.java用来写主程序mysql-connector-java-5.1.47.jar是java连接mysql需要导入的jar包…

  • 单片机中P1=0x01什么意思「建议收藏」

    单片机中P1=0x01什么意思「建议收藏」0x01是16进制,转化为二进制:00000001(字节(Byte)是计算机信息技术用于计量存储容量的一种计量单位,作为一个单位来处理的一个二进制数字串,是构成信息的一个小单位。最常用的字节是八位的字节,即它包含八位的二进制数)P1=0x01,表示P1.7~P.1=0,P1.0=1…

    2022年10月23日
  • HTML设置图片为页面背景

    HTML设置图片为页面背景HTML设置图片为页面背景:问题:在HTML页面中不使用CSS盒模型的前提下如何将一张图片设置为页面背景?方法:在<body>中使用background以及style来设置例:在这里我把html格式的文件和jpg格式的图片文件都放到了桌面上<html><head> <metacontent=”text/html”charset=”UTF-8″> <title>HTML设置图片为页面背景</

  • pycharm配置路径_如何在pycharm添加解释器

    pycharm配置路径_如何在pycharm添加解释器步骤一:pycharm–>settingforNewProjects步骤二:settingsforNewprojects–>projectInterpreter–>showAll–>Add

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号