`
tangyanbo
  • 浏览: 262530 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

跟我一起阅读Java源代码之HashMap(二)

阅读更多

上一节中实现的SimpleHashMap,没有解决冲突的问题,这一节我们继续深入

由于table的大小是有限的,而key的集合范围是无限大的,所以寄希望于hashcode散落,肯定会出现多个key散落在同一个数组下标下面,

因此我们要引入另外一个概念,将key和value同时存入table[index]中,即将key和value构成一个对象放在table[index],而且可能存放多个,他们的key对应的index相同,但是key本身不同

 

现在我们就该讨论以什么样的方式存储这些散落在同一个数组下标的元素

可以考虑数组?

也可以考虑链表存储

源码里面是用链表存储的,其实我也没明白这两种方式在这里有什么区别

,感觉无论在检索和存储上都是差不多的效率,

检索都是需要遍历的方式,而存储也可以是顺序的

 

那这个问题留给大家吧。

我们来实现链式存储的方式,首先定义一个链表数据结构Entry:

public class Entry<K, V> {
	//存储key
	final K key;
	//存储value
	V value;
	//存储指向下一个节点的指针
	Entry<K, V> next;
	//存储key映射的hash
	final int hash;
}

 

新的EntryHashMap实现方式

public class EntryHashMap<K, V> {

	transient Entry[] table;

	transient int size;

	public V put(K key, V value) {
		//计算出新的hash
		int hash = hash(key.hashCode());
		//计算出数组小标i
		int i = indexFor(hash, table.length);
		//遍历table[i],如果table[i]没有与新加入的key相等的,则新加入
		//一个value到table[i]中的entry,否则将新的value覆盖旧的value并返回旧的value
		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;
				return oldValue;
			}
		}
		addEntry(hash, key, value, i);
		return null;
	}

	public void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		//将新的元素插入链表前端
		table[bucketIndex] = new Entry<>(hash, key, value, e);
		size++;
	}

	/**
	 * 通过hash code 和table的length得到对应的数组下标
	 * 
	 * @param h
	 * @param length
	 * @return
	 */
	static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	/**
	 * 通过一定算法计算出新的hash值
	 * 
	 * @param h
	 * @return
	 */
	static int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}
}

 

 

分享到:
评论

相关推荐

    java代码-使用java解决手写hashMap的源代码

    java代码-使用java解决手写hashMap的源代码 ——学习参考资料:仅用于个人学习使用!

    java源代码原理视频.txt

    java源代码原理,深入理解HashMap原理、高可用redis集群架构、zookeeper分布式、海量数据缓存、springAOP底层源码分析等

    Java学生成绩管理系统源代码

    Java学生成绩管理系统源代码: imporjava.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io....

    Java 实例 - HashMap遍历源代码-详细教程.zip

    Java 实例 - HashMap遍历源代码-详细教程.zip

    一个java正则表达式工具类源代码.zip(内含Regexp.java文件)

    7 匹配身份证 8 匹配邮编代码 9. 不包括特殊字符的匹配 (字符串中不包括符号 数学次方号^ 单引号' 双引号" 分号; 逗号, 帽号: 数学减号- 右尖括号&gt; 左尖括号反斜杠\ 即空格,制表符,回车符等 10 匹配非负整数(正...

    java jdk实列宝典 光盘源代码

    java为数据结构中的映射定义一个接口java.util.Map,有四个实现类HashMap Hashtable LinkedHashMap TreeMap用法和区别;对Map排序; 5字符串 使用String;判断一个字符串是否是合法的java标识符;使用StringBuffer;...

    通过 HashMap、HashSet 的源代码分析其 Hash 存储机制1

    通过 HashMap、HashSet 的源代码分析其 Hash 存储机制1

    HashMap关系数据映射技术软件源代码和jar文件(pvo_v1.3)

    HashMap关系数据映射技术软件源代码和jar文件。pvo是基于List这样的数据结构实现的通用DAO工具,在pvo_1.3资源文件中新增了用于客户端的pvo.js文件,用于服务端的ProcessForm类,这是一个通用的表单解析工具,是一个...

    Java高级面试第二套1.面试必考之HashMap源码分析与实现

    c#、java、php等多语言解决方案源代码 Wafer - 快速构建具备弹性能力的微信小程序 https://github.com/tencentyun/wafer 重要: 1.第二步,可以在5分钟内实现; 2.成本3元(腾讯云支持微信小程序2017年推广期间,3...

    HashMap关系数据映射技术软件

    HashMap关系数据映射技术软件...现将PVO_v1.1软件包及其源代码对外公布,欢迎有实力的Java技术人员对其进行改进,共同打造一个高效、方便、灵活的关系映射工具。 PVO的目标是减轻你的工作负担、提高你的开发效率。

    Java集合框架源码剖析:HashSet 和 HashMap

     之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。  HashMap实现了Map...

    java7hashmap源码-AnnotationDemo:注解基础知识,编译时注解和运行时注解例子

    注解就相当于对源代码打的标签,给代码打上标签和删除标签对源代码没有任何影响。有的人要说了,你尽几把瞎扯,没有影响,打这些标签干毛线呢?其实不是这些标签自己起了什么作用,而且外部工具通过访问这些标签,...

    Servlet购物车思路及源代码

    里面有注释,使用的技术:Session,HashMap,List有易于帮助新手开阔思路.很简单的。

    java7hashmap源码-AAA_JAVA:AAA_JAVA

    用于源代码编译源文件 JAVA--&gt;用于源文件丢虚拟机运行 JDB--&gt;java调试器 编码表详解 ASCII:American Standard Code for Infomation Interchage美国信息交换标准代码 Unicode:万国码,0-127与ASCII一样 判断...

    Listener使用

    关于SWING基本功能,按键以及事件触发器使用源代码。对于初学JAVA的有较好帮助。

    Potato:阅读适用于Android采访的他妈的源代码-android source code

    阅读面试的源代码计划 本项目逐步面试准备过程的资料收集,原始资料阅读,参考大量的网上内容。 持续更新中... 关于问题标签的说明 概念:纯概念介绍,需要记住 使用方法:偏重用法,与源代码相对应 源代码:文章...

    爬虫例子源代码

    import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Queue; import org.htmlparser.Node; import org.htmlparser.Parser; import org.htmlparser.Tag; import org....

    javajdk1.8源码-Java-source-reading:jdk1.8源代码分析

    java jdk1.8 源码 Java-source-reading 缓慢更新一些个人学习java相关源码过程中的笔记,在这里你将不可避免地看到以下情况: 个别不懂/没想好的地方留空待补全 限于个人水平出现的解读错误 编辑错误 排版不统一 如...

    汽车销售管理系统

    纯Java版汽车管理销售系统(eclipse编译),分为管理员登陆和用户登陆,数据用列表List,ArrayList,Map及HashMap储存,没有数据库连接和其他什么额外工具,java控制台运行管理

    java词典源码-WordSeperator:Java源代码和字典,可用于将复合词分隔为子词

    Java源代码和字典,可用于将复合词分隔为子词。 编译并使用字典作为参数运行Seperator。 字典必须以行分隔,并且理想情况下不应包含任何复合词。 复杂度估算 空间复杂度 数据结构 字典被存储为Trie-Data结构。 字典...

Global site tag (gtag.js) - Google Analytics