JAVA中的hash

川长思鸟来 2023-10-18 22:19 101阅读 0赞

## 一.hashcode()方法 ##

首先hashcode()方法是万类始祖Object自带的一个方法，翻看源码可以知道是一个native方法，也就是说是调用的操作系统底层函数生成的一个值——hashcode。hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

![20190724161441956.png][]

## 二.hashcode的作用 ##

hashcode主要的作用是为了提高hash系的数据机构的性能。可以理解为JAVA让每个对象带有hashcode()方法就是为了方便生成hashcode，以供hash算法来使用，最后得到数据应该存储的位置。在《手撕JAVA(九)hash》一文中已经讨论过，hash算法其实就是将数据尽量均匀分布的一个过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70][]

整个流程下来我们可以发现，所谓hash系的数据结构其实并没有什么特殊，只是在使用过程中用到了hash值而已。

还有一个发现就是只要保证hash值不一样，每条数据算出来的存储位置是不一样的。这就是hash算法的作用，让数据尽量均匀的分散存储。但是在实际情况中存在两个问题：

1.hash冲突，不同对象运算出来的hash值可能会相同，那么hash算法算出来的位置值也相同。

2.随着需要存储的数据量的增加，hash表不可能无限扩容。

JAVA给出的解决办法就是hashMap

## 三.hashMap ##

先来看一下hashMap长什么样子

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 1][]

观察hashMap的源码可以看到：

kv对存放进来的时候会被封装成Node类型，Node类是一个hashMap封装的内部类

然后调用key的hashcode方法得到哈希码，

将这个hash码传到内置hash（）中进行散列运算，得到一个散列值，然后将散列值与数组length进行运算最终得到该Node存放在位置的下标。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 2][]

![20190724171241365.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 3][]

![20190724171320612.png][]

然后可能有以下三种动作中的一种：

1.如果该位置为null，直接放入。

2.如果该位置有node了，key不同，就直接挂在该node的后面。

**3.****如果key****相同，就equals****，如果equals****还相同，就认为是同个对象，直接替换掉（map****辨重的核心操作）**

**注意：**

**key****，hashcode****肯定相同，运算出的下标肯定也相同**

**key****不同，hashcode****却也可能相同，运算出来的下标可能也相同，**

**元素放入的顺序，在哈希表中被读出的顺序不一定相同。**

[20190724161441956.png]: https://img-blog.csdnimg.cn/20190724161441956.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190724165716982.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190724170949457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190724171556667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[20190724171241365.png]: https://img-blog.csdnimg.cn/20190724171241365.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190724171457963.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[20190724171320612.png]: https://img-blog.csdnimg.cn/20190724171320612.png