欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HashMap的底层实现原理

程序员文章站 2022-06-28 16:37:27
HashMap的底层实现原理哈希表(hash table)也叫散列表,HashMap是Java语言中用的最频繁的一种数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,而HashMap的实现原理也常常出现在各类的面试题中,重要性可见一斑。1.HashMap的数据结构在java编程语言中最基本的数据结构有两种,数组和链表。数组:查询速度快,可以根据索引查询;但插入和删除比较困难;链表:查询速度慢,需要遍历整个链表,但插入和删除操作比较容易。H...

HashMap的底层实现原理

哈希表(hash table)也叫散列表,HashMap是Java语言中用的最频繁的一种数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,而HashMap的实现原理也常常出现在各类的面试题中,重要性可见一斑。

1.HashMap的数据结构

在java编程语言中最基本的数据结构有两种,数组和链表。
数组:查询速度快,可以根据索引查询;但插入和删除比较困难;
链表:查询速度慢,需要遍历整个链表,但插入和删除操作比较容易。
HashMap是数组和链表组成的,数据结构中又叫“链表散列”。

HashMap的特点:
(1) 快速存储 :比如当我们对hashmap进行get和put的时候速度非常快。
(1) 快速查找(时间复杂度o(1))当我们通过key去get一个value的时候时间复杂度非常的低,效率非常高。
(3) 可伸缩:1数组扩容,边长。2,单线列表如果长度超过8的话会变成红黑树。
Hash值的计算
Hash值=(hashcode)^(hashcode >>> 16)
Hashcode予hashcode自己向右位移16位的异或运算。这样可以确保算出来的值足够随机。因为进行hash计算的时候足够分散,以便于计算数组下标的时候算的值足够分散。前面说过hashmap的底层是由数组组成,数组默认大小是16,那么数组下标是怎么计算出来的呢,那就是:
数组下标:hash&(16-1) = hash%16
对哈市计算得到的hash进行16的求余,得到一个16的位数,比如说是1到15之间的一个数,hashmap会与hash值和15进行予运算。这样可以效率会更高。计算机中会容易识别这种向右位移,向左位移。

Hash冲突
不同的对象算出来的数组下标是相同的这样就会产生hash冲突。
Hash冲突会产生单线链表。在这里插入图片描述
当单线链表达到一定长度后效率会非常低,那么在jdk1.8以后的话,加入了红黑树,也就是说单线列表达到一定长度后就会变成一个红黑树

Hashmap底层原理扩容
扩容
数组长度变成2倍 0.75
触发条件
数组存储比例达到75% – 0.75

一下是需要理解的:
Hashmap的扩容并不是为单线链表准备的,单线链表只是为了解决hash冲突准备的。也就是说当数组达到一定长度,比如说hashmap默认数组长度是16,那么达到出发条件,数组存储比例达到了75% ,也就是16*0.75=12的时候就会发生扩容

红黑树
一种二叉树,高效的检索效率

前面说了,当链表达到一定长度后,链表就会变成红黑树

触发条件
在链表长度大于8的时候,将后面的数据存在二叉树中

本文地址:https://blog.csdn.net/jieun587229/article/details/109729924