HaspMap的原理

实现简单的Map


前几天有想法弄懂HashMap的实现的原理,我自己也YY了一个想法去实现一个简单的Map, 代码如下:

public class KeyValuePair<K,V> {
	
	public  K Key;
	public  V Value;
	
	public K getKey() {
		return Key;
	}
	
	public void setKey(K key) {
		Key = key;
	}
	
	public V getValue() {
		return Value;
	}
	
	public void setValue(V value) {
		Value = value;
	}
}

然后使用List作为Container对数据进行存储,主体的内部实现原理如下:

public class MyMap<K, V> {
	private List<KeyValuePair<K, V>> map;
	
	public MyMap() {
		map = new ArrayList<KeyValuePair<K, V>>();
	}
	
	public V put(K k, V v) {
		KeyValuePair<K, V> keyValuePair = new KeyValuePair<K, V>();
		keyValuePair.setKey(k);
		keyValuePair.setValue(v);
		map.add(keyValuePair);
		return v;
	}
	
	public V get(K k) {
		for (KeyValuePair pair : map) {
			if (pair.getKey().equals(k)) {
				return (V) pair.getValue();
			}
		}
		return null;
	}
}

虽然也能实现类似的效果,但我们可以看到这个的map的时间复杂度是O(n),当集合数量很大时,则效率可以的非常的糟糕,下面做一个对比的测试:

@Test
public void MapTest(){
	
	long start=System.currentTimeMillis();
	MyMap<String,String> map =new MyMap();
	for (int i=0;i<10000;i++){
		map.put("Key"+i,"value"+i);
	}
	for (int i=0;i<10000;i++){
		map.get("Key"+i);
	}
	long end=System.currentTimeMillis();
	System.out.println("耗时:"+(end-start));
	
	 start=System.currentTimeMillis();
	Map<String,String> hashMap =new HashMap<>();
	for (int i=0;i<10000;i++){
		hashMap.put("Key"+i,"value"+i);
	}
	for (int i=0;i<10000;i++){
		hashMap.get("Key"+i);
	}
	end=System.currentTimeMillis();
	System.out.println("耗时:"+(end-start));
}

运行结果如下:

耗时:1815
耗时:14

整整慢了100多倍!

HashMap的实现原理


对于上面的代码,我们应该知道性能最慢的是查找对应的key值,对于ArrayList来说,可能插入也是很大的性能消耗。在JDK中使用一个数组来存储key,索引是根据Key的Hash值来确定,而每一个key对应数据单元是一个链表。用图表示效果如下:

下面我们JDK的原理进行分析:

存值

  1. 首先定义一个数组,其类型是一个Key-Value类型
  2. 根据key的Hash值来确定当前的索引
  3. 根据索引值来判断当前是否有值,如果当前有值则把当前的值插入当前数据之前

取值

1.根据key的Hash值来确定当前的索引,根据索引来找到链表的首节点

2.遍历链表,找到指定的Key对应的节点,取出当前值

具体的实现代码如下(可以利用上面的代码):

public class KeyValuePair<K,V> {
	
	public  K Key;
	public  V Value;
	public KeyValuePair next;
	
	public KeyValuePair getNext() {
		return next;
	}
	
	public void setNext(KeyValuePair next) {
		this.next = next;
	}
	public KeyValuePair(){
	
	}
	public KeyValuePair(K k, V v){
		this.Key=k;
		this.Value=v;
	}
	public K getKey() {
		return Key;
	}
	
	public void setKey(K key) {
		Key = key;
	}
	
	public V getValue() {
		return Value;
	}
	
	public void setValue(V value) {
		Value = value;
	}
}

HashMap的实现:

public class MyHashMap<K, V> {
	
	private  int defalutLength = 16;
	private int size;
	private KeyValuePair<K, V>[] arr;
	public MyHashMap() {
		arr = new KeyValuePair[defalutLength];
		size = 0;
	}
	
	public V put(K k, V v) {
		int index = findIndex(k);
		//todo:find out of index
		if (arr[index] == null) {
			arr[index] = new KeyValuePair(k, v);
		} else {
			KeyValuePair tempPair = arr[index];
			arr[index] = new KeyValuePair(k, v);
			arr[index].setNext(tempPair);
		}
		size++;
		return v;
	}
	
	private int findIndex(K key) {
		int index=key.hashCode() % defalutLength;
		return index>0?index:(-1)*index;
	}
 
	public V get(K k) {
		int index = findIndex(k);
		if (arr[index] == null) {
			return null;
		}
		KeyValuePair<K, V> current = arr[index];
		while (current.next != null) {
			if (current.getKey().equals(k)) {
				return current.getValue();
			}
			current = current.next;
		}
		return null;
	}
	public  int size(){
		return this.size;
	}
	
}

同样我们修改测试的代码:

@Test
public void MapTest(){
		
	long start=System.currentTimeMillis();
	MyMap<String,String> map =new MyMap();
	for (int i=0;i<10000;i++){
		map.put("Key"+i,"value"+i);
	}
	for (int i=0;i<10000;i++){
		map.get("Key"+i);
	}
	long end=System.currentTimeMillis();
	System.out.println("耗时:"+(end-start));
	
	 start=System.currentTimeMillis();
	Map<String,String> hashMap =new HashMap<>();
	for (int i=0;i<10000;i++){
		hashMap.put("Key"+i,"value"+i);
	}
	for (int i=0;i<10000;i++){
		hashMap.get("Key"+i);
	}
	end=System.currentTimeMillis();
	System.out.println("耗时:"+(end-start));
	 
	
	
	start=System.currentTimeMillis();
	MyHashMap<String,String> myhashMap =new MyHashMap<>();
	for (int i=0;i<10000;i++){
		myhashMap.put("Key"+i,"value"+i);
	}
	for (int i=0;i<10000;i++){
		myhashMap.get("Key"+i);
	}
	end=System.currentTimeMillis();
	System.out.println("耗时:"+(end-start));
	 
}

运行结果:

耗时:2337
耗时:26
耗时:337

我们看到我们使用的链表在插入数据的时候进行整理,极大的提高了Map的效率,但离Jdk的性能还有很大的差距。

优化散列算法


对于Map的查找的性能的瓶颈主要在最后的链表的查找,我们可以把Key的数据进行扩大,让Key分布的更加平均,这样就能减少最后链表迭代次数,实现思路:

  1. 添加一个报警百分比,当key的使用率长度大于当前的比例,我们对key的数组进行扩容
  2. 扩容后对原来的Key进行重新散列

修改后代码如下:

public class MyHashMap<K, V> {
	
	private  int defalutLength = 16;
	private final double defaultAlfa = 0.75;
	private int size;
	private int arrLength;
	private KeyValuePair<K, V>[] arr;
	
	public MyHashMap() {
		arr = new KeyValuePair[defalutLength];
		size = 0;
		arrLength=0;
	}
	
	public V put(K k, V v) {
		int index = findIndex(k);
		//todo:find out of index
		if(arrLength>defalutLength*defaultAlfa){
			extentArr();
		}
		if (arr[index] == null) {
			arr[index] = new KeyValuePair(k, v);
			arrLength++;
		} else {
			KeyValuePair tempPair = arr[index];
			arr[index] = new KeyValuePair(k, v);
			arr[index].setNext(tempPair);
		}
		size++;
		return v;
	}
	
	private int findIndex(K key) {
		
		int index=key.hashCode() % defalutLength;
		return index>0?index:(-1)*index;
	}
	private void extentArr(){
		  defalutLength=defalutLength*2;
		KeyValuePair<K, V>[] newArr=new KeyValuePair[defalutLength];
		for (int i=0;i<defalutLength/2;i++){
			if(arr[i]!=null){
				int index= findIndex(arr[i].getKey());
				newArr[index]=arr[i];
			}
		}
		arr=newArr;
	}
	public V get(K k) {
		int index = findIndex(k);
		if (arr[index] == null) {
			return null;
		}
		
		KeyValuePair<K, V> current = arr[index];
		while (current.next != null) {
			if (current.getKey().equals(k)) {
				return current.getValue();
			}
			current = current.next;
		}
		return null;
	}
	public  int size(){
		return this.size;
	}
	
}

最终测试性能结果如下:

耗时:2263
耗时:23
耗时:33

性能已经很接近了,至于为什么有差异,可能jdk有其它更多的优化(比如当链表长度大于8时,使用红黑树),但本文就讨论到这里。

(本文完)

作者:老付 如果觉得对您有帮助,可以下方的订阅,或者选择右侧捐赠作者,如果有问题,请在捐赠后咨询,谢谢合作 如有任何知识产权、版权问题或理论错误,还请指正。 自由转载-非商用-非衍生-保持署名,请遵循:创意共享3.0许可证 交流请加群113249828: 点击加群 或发我邮件 laofu_online@163.com

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸鹏说道

C# 温故而知新: 线程篇(二) 下

首先介绍下Classic Async Pattern: 其实Classic Async Pattern指的就是我们常见的BeginXXX和EndXXX IAsy...

2877
来自专栏蓝天

使用可重入函数进行更安全的信号处理

在早期的编程中,不可重入性对程序员并不构成威胁;函数不会有并发访问,也没有中断。在很多较老的 C 语言实现中,函数被认为是在单线程进程的环境中运行。

772
来自专栏北京马哥教育

做到这二十条,Python程序性能轻松翻倍!

1.优化算法时间复杂度 算法的时间复杂度对程序的执行效率影响最大,在Python中可以通过选择合适的数据结构来优化时间复杂度,如list和set查找某一个元素的...

3617
来自专栏xingoo, 一个梦想做发明家的程序员

【Spring开发】—— AOP之方法级拦截

前言: 前面介绍了Spring的核心模块以及相关的依赖注入等概念。这篇讲解一下spring的另一个重点,AOP面向切面编程。   说道AOP不得不提到几...

2088
来自专栏犀利豆的技术空间

徒手撸框架--实现 RPC 远程调用

微服务已经是每个互联网开发者必须掌握的一项技术。而 RPC 框架,是构成微服务最重要的组成部分之一。趁最近有时间。又看了看 dubbo 的源码。dubbo 为了...

1302
来自专栏.NET技术

.net平台的MongoDB使用

  最近花了点时间玩了下MongoDB.Driver,进行封装了工具库,平常也会经常用到MongoDB,因此写一篇文章梳理知识同时把自己的成果分享给大家。

1262
来自专栏青玉伏案

iOS逆向工程之Hopper中的ARM指令

虽然前段时间ARM被日本软银收购了,但是科技是无国界的,所以呢ARM相关知识该学的学。现在看ARM指令集还是倍感亲切的,毕竟大学里开了ARM这门课,并且做了不少...

2867
来自专栏pangguoming

C# 事件(Event)

事件(Event) 基本上说是一个用户操作,如按键、点击、鼠标移动等等,或者是一些出现,如系统生成的通知。应用程序需要在事件发生时响应事件。例如,中断。事件是用...

3725
来自专栏IT技术精选文摘

ZooKeeper 分布式锁实现

1362
来自专栏逸鹏说道

C#进阶系列——WebApi 接口参数不再困惑:传参详解上

前言:还记得刚使用WebApi那会儿,被它的传参机制折腾了好久,查阅了半天资料。如今,使用WebApi也有段时间了,今天就记录下API接口传参的一些方式方法,算...

4168

扫码关注云+社区