Hash及HashMap底层的一些理解

分手后的思念是犯贱 2022-04-08 17:48 247阅读 0赞

# 一、铺垫 #

本文不说那些高端名词，我打算用一些问题引出一些接地气的东西

## 问题一： ##

一般我们对hash的理解，是不同对象的hash不同，甚至是同一个对象的不同命实例的hash不同

那么问题是：“如果在一个循环中，对某个对象创建了多个同名的实例，那么它们的hash值会否相同”

要回答这个问题，直接上个图大家就了解了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhcmtkcmFnb25raW5n_size_16_color_FFFFFF_t_70][]

javadoc上说的很明白了，对Object的获取hash值操作，不依赖于java语言。只与实例所在内存的地址有关。

这样就好理解了，为什么同一个实例，它的hash值永远一致。

## 问题二： ##

都在说hash、hash的，那么hash是什么？有人说，hash就是散列。

问题是：“散列又特么的是什么呢？”

我的理解，散列就是把那些实例们分散开排队

比如，超市会设置多个收银员为我们结账。那我们在超市付款，大家一定会找那些人少的队伍去排队。

所以，这种把人分散到不同队伍的操作，就叫散列。

这样一来，由串行改并行，效率提高了有木有。所以大家心情美美哒。

## 问题三： ##

有人感觉Hash容器（比如HashMap），特别是jdk8之后的HashMap的底层实现机制为什么似曾相识呢？

是的，我感觉HashMap的实现机制，遵循的就是桶排序算法的思路。

本来桶排序算法是一个限制多多，诟病多多的算法。

比如，桶排序的待排元素只能是整形；再比如，待排序的数据间跨度不能太大。跨度太大会有大量的空置的桶，造成空间浪费。

但是，java的Object类自带的hashCode()方法为每个实例计算出的hash值的数位，桶排序算法就彻底释放出了它的活力了。

那怎么控制hash桶不会有浪费呢？

HashMap中有一个专门的table，用来记录当前HashMap的hash桶中都记录了哪些键。

这样，就不需要为了适配所有进入HashMap的hash值的可能性，而造成的hash桶浪费了

其作用，是在对HashMap做put和get操作时候，需要先去table中校验一下当前的key是否存在的。

## 问题四： ##

学习hash、HashMap的思想有啥用？

我觉得吧，在分布式架构流行的今天，了解一些map的hash机制、resize扩容机制

对设计分布式系统、考虑系统的水平扩容、负载均衡、session保存什么的都有很好的借鉴意义

比如jdk1.8之后的HashMap的实现方式，是hash桶与链表并存的机制。

同时，hash桶内部的链表还会在相同hash值较多的情况下，由链表进化为红黑树的可能

同时，桶内部的二次查找算法，也由比较算法变为了对树的二分查找

# 二、正题 #

铺垫完毕，说说我的一些理解吧。

## 2.1：HashMap的扩容机制与reHash ##

总听说“reHash”这一叫法，其实，如果真的了解桶排序算法的思想，那么我觉得这个叫法是不准确的。

扩容就是reSize，不是reHash

因为reHash这个叫法会让大家感觉，存入HashMap中的元素的hash值被改变了。其实改变这件事是不存在。

说说我的理解：

2.1.1：hashCode与容器无关

java在向hash容器（比如HashMap、HashTable）中添加对象的时候，首先要获取对象的hashCode。

而hashcode不依赖于hash容器。上面也说了，hashCode这东西基本与对象在内存中的地址什么的有关。

所以，只要内存地址不变，对象的hashCode不变。

所以，HashMap再怎么扩容，与它里面的那些对象们有个毛蛋的关系啊。

2.1.2：hash容器的扩容机制

已经有好多人聊过HashMap的resize这段代码都干了什么了，在此不再详述，感兴趣的诸位可以[从这里进去看看][Link 1]

我对hash容器（以HashMap为例）扩容这件事的理解是这样的

第一，HashMap的初始大小可能是16，扩容因子是0.75。

那么初始状态下，它里面只能存放12个不同的hashCode，如果我们继续向HashMap里面添加元素时

进来的可能会是一个新的hashCode，受扩容因子限制，那么hashMap就要扩容了

所以它扩容的唯一原因，就是因为它里面放不下更多的、不同的hashCode了。就这么简单。

还有的朋友说，当你需要重写某个类的equal方法的时候，需要在一定程度上重写hashCode函数

感兴趣的诸位可以[从这里进去看看 。][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhcmtkcmFnb25raW5n_size_16_color_FFFFFF_t_70]: /images/20220404/9f0725404a314a16920b7a978eec758f.png
[Link 1]: https://blog.csdn.net/u012961566/article/details/72963157
[Link 2]: https://www.cnblogs.com/dolphin0520/p/3681042.html

发表评论取消回复

表情：

评论列表（有 0 条评论，247人围观）

还没有评论，来说两句吧...

相关阅读

相关深入理解hashmap底层实现原理

目录总体介绍 HashMap元素的存储在hashmap中添加元素 HashMap的扩容机制 HashMap的线程安全性 1.添加和删除元素时存在不安全性 2.

桃扇骨/ 2024年03月17日 10:05/ 0 赞/ 72 阅读

相关 HashMap底层实现原理解析

![6225b9e118544330a17ef8314bc9e2d0.png][] 一、 HashMap中的put()和get()的实现原理： 1、map.put(k

阳光穿透心脏的1/2处/ 2023年10月13日 11:03/ 0 赞/ 68 阅读

相关深入理解HashMap的底层原理(二)

> 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Ha

- 日理万妓/ 2023年07月15日 11:25/ 0 赞/ 17 阅读

相关深入理解HashMap的底层原理(一)

> 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Ha

爱被打了一巴掌/ 2023年07月13日 12:28/ 0 赞/ 2 阅读

相关深入理解vue 一些底层原理

一　理解vue的核心理念使用vue会让人感到身心愉悦,它同时具备angular和react的优点,轻量级,api简单,文档齐全,简单强大,麻雀虽小五脏俱全. 倘若用

痛定思痛。/ 2022年12月28日 00:51/ 0 赞/ 158 阅读

相关 java中hashmap的一些简单理解

关于HashMap的一些个人简单理解 1.HashMap中的每个元素是存储在一个Entry类型的数组中，其中数组的下标是通过key的hashcode计算而来，这样就可以很

迷南。/ 2022年08月13日 12:58/ 0 赞/ 226 阅读

相关哈希、HashMap原理及源码、Hash的一些应用面试题

一、哈希定义 Hash，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出

喜欢ヅ旅行/ 2022年08月04日 01:41/ 0 赞/ 180 阅读

相关 HashMap的底层实现

（1）HashMap的构成 HashMap是由数组+链表实现的。它的主干是一个Entry数组，Entry是HashMap的基本组成单元，每一个Entry包含一个 key-v

痛定思痛。/ 2022年05月17日 09:36/ 0 赞/ 250 阅读

相关源码解析-深刻理解Hash HashTable HashMap原理及数据hash碰撞问题

HashMap 前言 Hash HashTable 开地址法线性探测法平方探测法

た入场券/ 2022年04月11日 12:18/ 0 赞/ 273 阅读

相关 Hash及HashMap底层的一些理解

一、铺垫本文不说那些高端名词，我打算用一些问题引出一些接地气的东西问题一：一般我们对hash的理解，是不同对象的hash不同，甚至是同一个对象的不同命实例的

分手后的思念是犯贱/ 2022年04月08日 17:48/ 0 赞/ 248 阅读