【Java数据结构】---哈希表

前言

在顺序结构以及平衡树中，元素对应的关键码与这个元素在电脑中存储的位置没有对应关系，因此，要查找一个元素，必须要经过该元素关键码的多次比较。面对较多的数据，搜索的效率就大大降低了。也就是说： 搜索的效率取决于搜索过程中元素的比较次数。

最理想的搜索方法就是，不经过任何比较，直接从表中得到要搜索的元素

哈希的概念

如果构造一种存储结构，通过某种函数，使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

举个例子：

数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key)=key%capacity;(capacity为存储元素底层空间总大小 != 数组大小)

按照这个哈希函数求得的值，就是这个元素对应要放的下标。

哈希冲突

那么如果这组数据里面加了一个14，此时，要怎么放呢？

显然，此时有两个不同的关键字，使用同一个哈希函数，求得了一个相同的存储位置。此时就发生了哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞

冲突 避免

既然有冲突，那就要防止冲突的发生。

但是实际上，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率

设计合理的哈希函数（第一种方法避免）

设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

比如：前面底层数组长度为10，值域在0~9之间就不会冲突：一旦出现值域之外的值，像是14，就会出现冲突。

1. 哈希函数计算出来的地址能均匀分布在整个空间中
2. 哈希函数应该比较简单

常用的哈希函数

1. 直接定制法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 。适合查找比较小且连续的情况。

优点：简单、均匀 缺点：需要事先知道关键字的分布情况

1. 除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数

哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

1. 还有平方取中法、折叠法、数学分析法…………

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突(我们平时也不会去设计一个哈希函数，直接用原生的可以了)

调节负载因子（第二种方法避免）

负载因子a = 填入表中的元素个数 / 散列表的长度

得出结论：当负载因子越大，冲突率越大。

增加散列表长度，就只能去扩容，Java里面默认负载因子是0.75，也就是说，当负载因子是0.75时，进行扩容

冲突 解决

闭散列（第一种方法解决）

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

像上面出现的14和4冲突，那就可以把14放到4后边的空位置去

如何去找到下一个空位置？

线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

在这里插入图片描述

但是这种方法有一个缺点 ，那就是删除的时候，不好直接删除。

如果把4删去，那么搜索14时该怎么找呢？

解决办法肯定有，伪删除，删除的下标设置为bool类型，删除后为false。但是，这样一来就会很复杂。

二次探测

二次探测：线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题， 找下一个空位置的方法为：H(i)=(H0+i^2)%m。H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小

在这里插入图片描述

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。 为解决这个问题出现了开散列。

开散列（哈希桶）(第二种方法解决)

                        数组+链表的形式

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合(也叫做桶)，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

在这里插入图片描述

通常，哈希表的插入、删除、查找时的时间复杂度为O(1)

与Java类集的关系

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
2. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的

使用HashMap,HashSet

pubilc static void main(String[] args){
     HashMap<String,Integer> map=new HashMap<>();
     map.put("axc",3);
     map.put("hello",13);
     map.put("oca",3);
     
     //Key不能重复，天然去重
     HashSet<String> set=new HashSet<>();
     set.put("axc");
     set.put("hello");
     set.put("oca");  
}

与TreeMap、TreeSet一样，HashSet底层也是一个HashMap，而且方法的使用与TreeMap、TreeSet也一样。

HashMap,HashSet不涉及比较，因为他们底层都是数组+链表，不是搜索树

完结

好了，到这里【Java数据结构】部分就已经结束了~ 如果这个系列博客对你有帮助的话，可以点一个免费的赞并收藏起来哟~ 可以点点关注，避免找不到我~ ，我的主页：optimistic_chen 我们下期不见不散~~Java