java入门，哈希函数

ゝ一世哀愁。 2024-02-20 12:12 12阅读 0赞

#### 一、前言 ####

一听到哈希函数这种东西就感觉是数学，增加了人们的印象它很难。其中在数据结构中的HashMap的存储方式就用到了哈希函数，所以它也算是java的基础。看到哈希别惊慌，首先它只不过是个名称，我们理解它是个函数就行，然后它是散列的，那么就看函数的算法是怎样的。它主要的作用是：通过将关键字(key)映射到表中一个位置， 可以直接访问记录， 以提高查找的速率，相比较其他的查找结构，哈希表查找的时间复杂度更低。

![241a372505794e4dbfc36d7c84b23b1e.png][]

#### 二、哈希函数（散列函数） ####

1、哈希表：

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

那就是可以写成： adrr = f(key)

就是通过一定的算法通过key可以找到地址。

2、散列函数的几种构造方法：

1. 直接定址法

取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。

2. 数字分析法

假设某公司的员工登记表以员工的手机号作为关键字。手机号一共11位。前3位是接入号，对应不同运营商的子品牌；中间4位表示归属地；最后4位是用户号。不同手机号前7位相同的可能性很大，所以可以选择后4位作为散列地址，或者对后4位反转（1234 -> 4321）、循环右移（1234 -> 4123）、循环左移等等之后作为散列地址。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布比较均匀，就可以考虑这个方法。

3. 平方取中法

假设关键字是1234、平方之后是1522756、再抽取中间3位227，用作散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

4. 折叠法

将关键字从左到右分割成位数相等的几部分，最后一部分位数不够时可以短些，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

比如关键字是9876543210，散列表表长是3位，将其分为四组，然后叠加求和：987 + 654 + 321 + 0 = 1962，取后3位962作为散列地址。

折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

5. 除留余数法

f(key) = key mod p (p≤m)，m为散列表长。这种方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数，可以更好的减小冲突。

此方法为最常用的构造散列函数方法。

6. 随机数法

f(key) = random(key)，这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

实际应用中，应该视不同的情况采用不同的散列函数。如果关键字是英文字符、中文字符、各种各样的符号，都可以转换为某种数字来处理，比如其unicode编码。下面这些因素可以作为选取散列函数的参考：（1）计算散列地址所需的时间；（2）关键字长度；（3）散列表大小；（4）关键字的分布情况；（5）查找记录的频率。

####    三、hashcode是什么东西 ####

1、什么是hashcode  
hash code是一种编码方式，在Java中，每个对象都会有一个hashcode，Java可以通过这个hashcode来识别一个对象。至于hashcode的具体编码方式，比较复杂（事实上这个编码是可以由程序员通过继承和接口的实现重写的），可以参考数据结构书籍。而hashtable等结构，就是通过这个哈希实现快速查找键对象。

两个对象值相同(x.[equals][](y) == true)，不一定相等。

1) 对象相等则hashCode一定相等；

2) hashCode相等对象未必相等。

2.hashcode有什么作用

在Java中，HashCode的作用主要有两个方面：

在哈希表中的应用：哈希表（如HashMap、HashSet等）是基于哈希码实现的数据结构，通过哈希码可以确定对象在哈希表中的位置，从而实现高效的数据访问和查找。当我们使用哈希表来存储对象时，会使用对象的哈希码来计算该对象在哈希表中的存储位置。  
对象的标识性：HashCode可以用于判断两个对象是否相等。在Java中，通过equals()方法比较两个对象的内容是否相等，但在某些情况下，如果两个对象的内容相同但是引用不同，equals()方法会返回false。这时可以使用HashCode来辅助判断对象的相等性。一般情况下，如果两个对象的HashCode相等，那么它们的equals()方法也应该返回true。因此，HashCode可以用于快速比较对象的相等性，尤其在使用哈希表、集合和搜索算法时特别有用。  
需要注意的是，HashCode并不是对象的唯一标识符，不同对象的HashCode可能相同。因为HashCode是通过对对象的状态计算而来的，不同对象的状态相同，那么它们的HashCode也会相同。但相同HashCode的对象并不一定相等，因为HashCode是有限的，可能存在哈希冲突。

在Java中，为了正确使用HashCode，应该遵循以下规则：

如果两个对象相等（equals()方法返回true），那么它们的HashCode应该相等。  
如果两个对象的HashCode相等，它们不一定相等（equals()方法返回true）。这是由于HashCode的有限性和可能的哈希冲突。  
在重写equals()方法时，通常也需要重写hashCode()方法，以保证两个相等的对象具有相同的HashCode。  
总之，HashCode在Java中是用于快速查找和比较对象的重要概念，它在哈希表和相等性判断中扮演着重要的角色。

[241a372505794e4dbfc36d7c84b23b1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/fb103dea67c64b2ab7840cdc892323da.png
[equals]: https://baike.baidu.com/item/equals/4481402?fromModule=lemma_inlink