HashMap原理详解及常用API介绍

这篇具有很好参考价值的文章主要介绍了HashMap原理详解及常用API介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

如果你准备面试Java后端方向的工程师,那么HashMap可以说是面试中的重中之重,你去10家公司面试,可能8家公司都会会问道。所以可见HashMap相关的知识点对于我们面试来说有多么重要,接下来就让我们走进HashMap的大门吧!

1.什么是HashMap

HashMap是Java当中一种数据结构,是一个用于存储Key-Value键值对的集合,每一个键值对也叫作Entry实体。
HashMap 数据结构为 数组+链表,其中:链表的节点存储的是一个 Entry 对象,每个Entry 对象存储四个属性(hash,key,value,next)。
java查询哈希表的api,java,面试,哈希算法,java,散列表

2.HashMap存储原理

首先,初始化 HashMap,提供了有参构造和无参构造,具体的关于HashMap的构造函数如下所示,无参构造中,容器默认的数组大小 initialCapacity 为 16,且数组大小只允许为2的整数次幂,默认加载因子loadFactor 为0.75。容器的阈值为 initialCapacity * loadFactor,默认情况下阈值为 16 * 0.75 = 12。当存储在HashMap集合中的Entry数目大于容器的阈值,则容器需要扩容,使其容量变为原来的两倍。

HashMap();//构造一个具有默认 初始容量 (16)  和 默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity);//构造一个带 指定初始容量 和 默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor);//构造一个带指定初始容量和加载因子的空 HashMap。

接下来,我们对HashMap的put方法进行探索!
第一步:通过 HashMap 自己提供的hash 算法算出当前 key 对应的hash 值;

int hash=key.hashCode();

第二步:通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置;

static int indexFor(int hash, int length) { 
       // hash 为key 的 hash值;length 是数组长度
       return hash & (length-1);  
}

第三步:判断size 是否已经达到了当前阈值,如果没有,继续;如果已经达到阈值,则先进行数组扩容,将数组长度扩容为原来的2倍。
请注意:size 是当前容器中已有 Entry 的数量,不是全部Entry所占数组空间的大小。
第四步:将当前对应的 hash,key,value封装成一个 Entry,去数组中查找当前位置有没有元素,如果没有,放在这个位置上;如果此位置上已经存在链表,那么遍历链表,如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true,则把原来节点上的value 返回,将当前新的 value替换掉原来的value,如果遍历完链表,没有找到key 与当前 key equals为 true的,就把刚才封装的新的 Entry插入到对应链表的尾部,即当前链表的最后一个元素。(注意:在JDK1.8之前,是插入到链表的头部,即采用的是头插法
OK!到目前为止,我们已经将当前的 key-value 存储到了容器中。
在put方法的实现原理中,就出现了一个经典的面试题!
即:为什么 HashMap使用这种方式(hash & (length-1))计算在数组中位置呢?
在数据结构中,简单的Hash函数只需要取模就可以了。而HashMap用&运算主要是提升计算性能。那么这又会带来一个新的问题,为什么&运算要与length-1呢?回看HashMap初始化容量大小的时候,数组长度length必须是2的整数次幂(如果手动传参为n,HashMap会自动转换长度为距离n最近的2的整数次幂)。只有这样,hash&(length-1)的值才会和hash%length计算的结果保持一致。这就是它的原因所在。采用这种方式,即提升了CPU计算性能,也保证了数据在Hash表中的均匀分布。
读者如果不理解其中的原理,可以自行编写代码测试一下:

public static void main(String[] args) {
	int	length  = 16; //定义数组长度为2的整次幂,2^4
	//定义key,并计算k的hash值
	String k = "China";
	int hash = k.hashCode();
	//分别使用两种方式计算在数组中的位置
	int index1 = hash % length;
	int index2 = hash & (length - 1);
	//验证结果
	System.out.println(index1 == index2);
	//结果为 true
}

于此同时,这里还可以引申出另外一个问题?
即:为什么hashmap的容量是2的幂次方?
1.计算机内&运算速度较快,至少比%速度要快;
2.当length为2的整数次幂时,会满足一个公式:(length-1)&hash=hash%length;
3.采用(n-1)&hash来计算索引位置时,当n为2的幂次方的时候,n-1转换为二进制时可以保证低位全都是1,所以元素存储在哈希表中的位置完全取决于其hash值,而Java中的hashCode()方法能够满足元素的均匀分布,因此就会导致元素索引分布均匀。

3.HashMap和HashTable 的异同

区别 HashMap HashTable
是否线程安全
数据结构 数组+链表+红黑树 数组+链表
是否允许键值为null
定位算法 采用的是&运算 采用的是%运算
扩容算法 容量扩充为原来的2倍 容量扩充为原来的2倍+1
链表插入 将新节点插入到链表的尾部 将新节点插入到链表的头部
继承的类 继承abstractMap抽象类 继承Dictionary抽象类
实现的接口 实现Map接口 实现Map接口
默认容量大小 16 11
默认负载因子 0.75 0.75

4.HashMap采用的API

java查询哈希表的api,java,面试,哈希算法,java,散列表文章来源地址https://www.toymoban.com/news/detail-568183.html

package a;
import java.util.HashMap;

import java.util.Map.Entry;
public class Main{
    public static void main(String[] args){
    	HashMap<String,Integer> mp = new HashMap<String,Integer>();
    	mp.put("one",1);	//存放键值对
    	System.out.println(mp.get("one"));	//通过键取值,输出 1
    	System.out.println(mp.get("1"));	//通过键取值,不存在,输出 null
    	System.out.println("====================");
    	
    	System.out.println(mp.containsKey("one"));	//HashMap中是否包含该键,输出true
    	System.out.println(mp.containsKey("two"));	//不包含该键,输出false
    	System.out.println("====================");
    	
    	System.out.println(mp.containsValue(1));	//HashMap中是否包含该值,输出true
    	System.out.println(mp.containsValue(2));	//不包含该值,输出false
    	System.out.println("====================");
    	
    	System.out.println(mp.isEmpty());	//判断是否为空,输出false
    	System.out.println(mp.size()); 		//输出 HasMap 的长度,1
    	System.out.println("====================");
    	
    	mp.remove("one");	//从HashMap中删除该键,值也会被删除
    	System.out.println(mp.get("one"));	//输出null
    	System.out.println(mp.containsKey("one"));	//输出false
    	System.out.println(mp.containsValue(1));	//输出false
    	//也可以通过 mp.remove("one",1); 把键和值一起删掉
    	System.out.println("====================");
    	//重新添加键值对
    	mp.put("one", 1);
    	mp.put("two", 2);
    	mp.put("three", 3);
    	System.out.println(mp.values());//输出所有值,[1, 2, 3]
    	System.out.println(mp.keySet());//输出所有键,[one, two, three]
    	System.out.println(mp.entrySet());//输出所有键和值,[one=1, two=2, three=3],中括号
    	System.out.println("====================");
    	
    	HashMap<String,Integer> mp2 = new HashMap<String,Integer>();
    	mp2.put("four", 4);
    	mp.putAll(mp2);	//添加同类型另一个HashMap,放进头部
    	System.out.println(mp);	//输出整个HashMap的键和值,{four=4, one=1, two=2, three=3},大括号
    	System.out.println("====================");
    	
    	mp.replace("one", 5);	//替换键的值,java8才有
    	mp.replace("two", 2 , 6);	//替换键的旧值为新值
    	System.out.println(mp);	//输出{four=4, one=5, two=6, three=3}
    	System.out.println("====================");
    	
    	Object mp3 = mp.clone();	//克隆一个,顺序随机
    	System.out.println(mp3);	//输出{two=6, three=3, four=4, one=5}
    	System.out.println("====================");
    	
    	for(String key:mp.keySet())	//遍历整个HashMap的键
    		System.out.print(key+' ');//输出four one two three 
    	System.out.println();
    	for(Integer values:mp.values())	//遍历整个HashMap的值
    		System.out.print(values+' ');//输出36373835,并不是4 5 6 3 ,说明该方法不能输出值
    	for(Entry<String,Integer> entry:mp.entrySet()) {	//遍历整个HashMap,输出键值
    		String key = entry.getKey();
    		Integer value = entry.getValue();
    		System.out.print(key+'='+value+' ');	//输出four=4 one=5 two=6 three=3 
    	}
    	System.out.println("====================");
    	mp.clear();	//清空数组
    	System.out.println(mp); 	//输出{}
    	System.out.println("====================");
    }
}

到了这里,关于HashMap原理详解及常用API介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【小项目】微信定时推送天气预报Github项目使用及原理介绍-包含cron、天气预报、常用api...

    一、资料链接 1、github地址 https://github.com/qq1534774766/wx-push 2、教程地址 https://blog.csdn.net/qq15347747/article/details/126521774 3、易客云API(自动发送天气) https://yikeapi.com/account/index 4、apispace-各种接口(名人名言) https://www.apispace.com/console/api?orgId=6356 5、微信公众平台 https://mp.weixin.qq.com/d

    2024年02月02日
    浏览(42)
  • 【自学笔记】01Java基础-08Java常用API:03日期类详解

    记录Java基础-常用API-有关时间日期的类。 1.1 什么是Date类 Date 类位于 java.util 包中,代表当前所在系统的日期时间信息或表示特定的瞬间,精确到毫秒。 这个类在早期版本的 Java 中被广泛使用,但由于其功能和设计的局限性,自Java8起,推荐使用 java.time 包中的新日期和时间

    2024年01月22日
    浏览(34)
  • 详解Java HashMap

    HashMap是Map接口的实现类,基于哈希表来存储键值对。 HashMap可以存储null的key和value,可以允许多个value为null,但是只能允许一个key为null。 JDK1.8之前的HashMap底层数据结构采用 数组+链表 实现,JDK1.8之后采用 数组+链表/红黑树 实现。数组是HashMap的主体,采用拉链法(链表)解

    2024年02月08日
    浏览(44)
  • HashMap如何解决哈希冲突?

    了解Hash冲突首先了解Hash算法和Hash表 Hash算法就是把任意长度的输入通过散列算法变成固定长度的输出,这个输出结果就是一个散列值 Hash表又叫做“散列表”,它是通过key直接访问到内存存储位置的数据结构,在具体的实现上,我们通过Hash函数,把key映射到表中的某个位置

    2023年04月12日
    浏览(43)
  • HashMap如何解决哈希冲突

    Hash算法就是把任意长度的输入通过 散列算法 编程固定长度的输出。这个输出结果就是一个 散列值 。 Hash表又称为“ 散列表 ”,它是通过key直接访问到内存存储位置的数据结构。在具体的实现上,我们通过Hash函数把key映射到表中的某个位置,来获取这个位置的数据,从而去

    2023年04月26日
    浏览(45)
  • 【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)

    在阅读了上篇文章《【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)》之后,相信您对HashMap的基本原理和基础结构已经有了初步的认识。接下来,我们将进一步深入探索HashMap的源码,揭示其深层次的技术细节。通过这次解析,您将更深入地

    2024年02月01日
    浏览(47)
  • Rust 笔记:Rust 语言中哈希结构(哈希映射,HashMap)、集合(哈希集,HashSet)及其使用

    Rust 笔记 Rust 语言中映射(HashMap)与集合(HashSet)及其用法 作者 : 李俊才 (jcLee95):https://blog.csdn.net/qq_28550263?spm=1001.2101.3001.5343 邮箱 : 291148484@163.com 本文地址 :https://blog.csdn.net/qq_28550263/article/details/130876735 【介绍】:本文介绍 Rust 中哈希结构相关概念及其使用。在 R

    2024年02月09日
    浏览(50)
  • 哈希表HashMap(基于vector和list)

    C++数据结构与算法实现(目录) 1 什么是HashMap? 我们这里要实现的HashMap接口不会超过标准库的版本(是一个子集)。 HashMap是一种键值对容器( 关联容器 ),又叫 字典 。 和其他容易一样,它可以对存储的元素进行 增删改查 操作。 它之所以叫关联容器,是因为它的每个元

    2024年02月10日
    浏览(41)
  • 面试题(2)-HashMap 是怎么解决哈希冲突的

    Hash函数指将哈希表中元素的关键键值映射为元素存储位置的函数。 把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值。 散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。因此,散

    2024年02月14日
    浏览(41)
  • 哈希表HashMap(基于vector和list)(答案)

    答案如下

    2024年02月15日
    浏览(165)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包