哈希表是一种常用的数据结构，用于高效地存储和查找数据。在哈希表中，每个元素都有一个对应的键和值，通过计算键的哈希值，将其映射到数组的特定位置上。哈希值的计算是哈希表的关键步骤之一，它决定了元素在数组中的存储位置。

哈希函数

在哈希表底层，常用的算法用于计算哈希值的是散列函数（HashFunction）。散列函数是一种将输入数据映射到固定大小的输出值的函数。它的设计目标是尽可能均匀地将输入值分散到输出范围内的不同位置，以减少冲突的概率。在哈希表中，散列函数负责将键映射到数组的索引位置，使得元素能够均匀地分布在整个数组中。

常见的哈希表底层算法

• 直接寻址法（DirectAddressing）：直接使用键作为数组的索引，将键值对存储在数组中对应的位置上。这种方法在键的范围较小且连续的情况下效果较好，但对于范围较大或不连续的键，会造成空间浪费。
• 除留余数法（DivisionMethod）：将键除以一个固定的数，并取余数作为哈希值。这种方法简单快速，但在键的分布不均匀时容易导致冲突。
• 平方取中法（Mid-squareMethod）：将键的平方数进行截取，取中间的一部分作为哈希值。这种方法可以较好地处理键的分布不均匀的情况，但计算开销较大。
• 乘法散列法（MultiplicativeHashing）：将键乘以一个介于0和1之间的常数，并取结果的小数部分乘以数组长度，再取整数部分作为哈希值。这种方法能够较好地处理键的分布不均匀，且计算开销较小。

其他哈希值计算算法

除了上述常用的哈希表底层算法，还有一些其他的算法可以用于计算哈希值，如：

• MD5（MessageDigestAlgorithm5）：MD5是一种广泛使用的哈希函数，能够将任意长度的输入数据映射为固定长度的哈希值。它具有较高的散列性和抗碰撞能力，但由于其较短的输出长度（128位），可能存在哈希冲突的概率较高。
• SHA-1（SecureHashAlgorithm1）：SHA-1是一种安全哈希函数，能够将任意长度的输入数据映射为160位的哈希值。它具有较高的散列性和抗碰撞能力，但由于其输出长度较长，计算开销较大。

• CRC32（CyclicRedundancyCheck）：CRC32是一种循环冗余校验码，常用于数据校验和错误检测。它能够将输入数据映射为32位的哈希值，具有较高的散列性，但抗碰撞能力较弱。

算法选择

哈希表底层采用的算法用于计算哈希值的选择取决于具体的需求和应用场景。不同的算法具有不同的特点和性能表现，开发者需要根据实际情况选择合适的算法，以保证哈希表的性能和效率。

HashMap底层实现原理解析

我们常见的有集合数据有三种结构：1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点：

而我们常见的HashMap就是这样的一种数据结构

（1）、首先将k,v封装到Node对象当中（节点）。 （2）、然后它的底层会调用K的hashCode()方法得出hash值。 （3）、通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

(1)、先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。 (2)、通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

原因 : 增删是在链表上完成的，而查询只需扫描部分，则效率高。

HashMap集合的key，会先后调用两个方法，hashCode and equals方法，这这两个方法都需要重写。

因为equals方法默认比较的是两个对象的内存地址

哈希值是什么？

哈希值一般指哈希函数。

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。

一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。

理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

哈希值概念简单普及：

1、哈希值其实就是一段数据，只不过这个数据有特殊的含义，它是某个文件或者某个字符串的DNA，或者身份证。

2、哈希算法（典型的有MD5，SHA-1等），将一段较长的数据映射为较短小的数据，这段小数据就是大数据的哈希值。

它有这样一个特点，他是唯一的，一旦数据发生了变化，哪怕是一个微小的变化，它的哈希值也会发生变化。另外一方面，既然是DNA，那就保证了没有两个数据的哈希值是完全相同的。

3、它常常用来判断两个文件是否相同。比如，从网络上下载某个文件，只要把这个文件原来的哈希值同下载后得到的文件的哈希值进行对比，如果相同，则表示两个文件完全一致，下载过程没有损坏文件。

而如果不一致，则表明下载得到的文件跟原来的文件不同，文件在下载过程中受到了损坏。