百度360必应搜狗淘宝本站头条
mqtt服务器xftp6mybatiscollectionkeyerrorc#var
当前位置：网站首页 > 热门文章 > 正文

如何手写一个HaspMap

bigegpt 2024-08-09 11:08 2 浏览

实现简单的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时，使用红黑树），但本文就讨论到这里。

(本文完)

相关推荐

【Docker 新手入门指南】第十章:Dockerfile

Dockerfile是Docker镜像构建的核心配置文件，通过预定义的指令集实现镜像的自动化构建。以下从核心概念、指令详解、最佳实践三方面展开说明，帮助你系统掌握Dockerfile的使用逻...

Windows下最简单的ESP8266_ROTS_ESP-IDF环境搭建与腾讯云SDK编译

前言其实也没啥可说的,只是我感觉ESP-IDF对新手来说很不友好,很容易踩坑,尤其是对业余DIY爱好者搭建环境非常困难,即使有官方文档,或者网上的其他文档,但是还是很容易踩坑,多研究,记住两点就行了,...

python虚拟环境迁移（python虚拟环境conda）

主机A的虚拟环境向主机B迁移。前提条件：主机A和主机B已经安装了virtualenv1.主机A操作如下虚拟环境目录：venv进入虚拟环境：sourcevenv/bin/active(1)记录虚拟环...

Python爬虫进阶教程(二):线程、协程

简介线程线程也叫轻量级进程，它是一个基本的CPU执行单元，也是程序执行过程中的最小单元，由线程ID、程序计数器、寄存器集合和堆栈共同组成。线程的引入减小了程序并发执行时的开销，提高了操作系统的并发性能...

基于网络安全的Docker逃逸（docker）

如何判断当前机器是否为Docker容器环境Metasploit中的checkcontainer模块、（判断是否为虚拟机，checkvm模块）搭配学习教程1.检查根目录下是否存在.dockerenv文...

Python编程语言被纳入浙江高考，小学生都开始学了

今年9月份开始的新学期，浙江省三到九年级信息技术课将同步替换新教材。其中，新初二将新增Python编程课程内容。新高一信息技术编程语言由VB替换为Python，大数据、人工智能、程序设计与算法按照教材...

CentOS 7下安装Python 3.10的完整过程

1.安装相应的编译工具yum-ygroupinstall"Developmenttools"yum-yinstallzlib-develbzip2-develope...

如何在Ubuntu 20.04上部署Odoo 14

Odoo是世界上最受欢迎的多合一商务软件。它提供了一系列业务应用程序，包括CRM，网站，电子商务，计费，会计，制造，仓库，项目管理，库存等等，所有这些都无缝集成在一起。Odoo可以通过几种不同的方式进...

Ubuntu 系统安装 PyTorch 全流程指南

当前环境：Ubuntu22.04，显卡为GeForceRTX3080Ti1、下载显卡驱动驱动网站：https://www.nvidia.com/en-us/drivers/根据自己的显卡型号和...

spark+python环境搭建（python 环境搭建）

最近项目需要用到spark大数据相关技术，周末有空spark环境搭起来...目标spark，python运行环境部署在linux服务器个人通过vscode开发通过远程python解释器执行代码准备...

centos7.9安装最新python-3.11.1（centos安装python环境）

centos7.9安装最新python-3.11.1centos7.9默认安装的是python-2.7.5版本，安全扫描时会有很多漏洞，比如：Python命令注入漏洞(CVE-2015-2010...

Linux系统下，五大步骤安装Python

一、下载Python包网上教程大多是通过官方地址进行下载Python的，但由于国内网络环境问题，会导致下载很慢，所以这里建议通过国内镜像进行下载例如：淘宝镜像http://npm.taobao.or...

centos7上安装python3（centos7安装python3.7.2一键脚本）

centos7上默认安装的是python2，要使用python3则需要自行下载源码编译安装。1.安装依赖yum-ygroupinstall"Developmenttools"...

利用本地数据通过微调方式训练 本地DeepSeek-R1 蒸馏模型

网络上相应的教程基本都基于LLaMA-Factory进行，本文章主要顺着相应的教程一步步实现大模型的微调和训练。训练环境：可自行定义，mac、linux或者window之类的均可以，本文以ma...

【法器篇】天啦噜，库崩了没备份（天啦噜是什么意思?）

背景数据库没有做备份，一天突然由于断电或其他原因导致无法启动了，且设置了innodb_force_recovery=6都无法启动，里面的数据怎么才能恢复出来？本例采用解析建表语句+表空间传输的方式进行...

一周热门
最近发表
标签列表