开源小程序模板,江门关键词优化排名,网站运营及推广,济源建设企业网站公司目录
哈希表
哈希冲突
1. 冲突发生
2. 比较常见的哈希函数
3. 负载因子调节(重点)
散列表的载荷因子概念
负载因子和冲突率的关系
冲突-解决-闭散列
线性探测
二次探测
冲突-解决-开散列
结尾 我们在前面讲解了TerrMap#xff08;Set#xff09;的底层是一个搜索…目录
哈希表
哈希冲突
1. 冲突发生
2. 比较常见的哈希函数
3. 负载因子调节(重点)
散列表的载荷因子概念
负载因子和冲突率的关系
冲突-解决-闭散列
线性探测
二次探测
冲突-解决-开散列
结尾 我们在前面讲解了TerrMapSet的底层是一个搜索二叉树同时Set和Map还存在HashSetMap类但是HahsMapSet到底是什么呢本章来详细介绍以下。
首先来了解以下什么叫做哈希表
哈希表
在学过的诸多数据结构中如果存在一种删除和插入的结构不经过任何比较一次直接从表中搜索到数据其时间复杂度能够达到O(1)那么这将非常恐怖其他数据结构在它面前都不值一提。不错哈希表这种结构就是能够达到O(1)的恐怖结构但是如果它真的那么好用不就说明不用学习其他的结构吗那么它一定存在它的问题。
当向该结构中 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(HashTable)(或者称散列表)。
哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小 当然如果我们再次插入14呢?结果为4啊又该插入在哪里呢
这个就是我们本章的重点哈希冲突4%10 414%10 4此时发生了哈希冲突。
哈希冲突
1. 冲突发生
首先我们得知道哈希冲突是必然的无论怎么插入插入多少都无法杜绝哪怕就插入两个元素414都发生了哈希冲突我们能做的就是尽量避免哈希冲突的发生。
这也就是我们哈希表这种结构存在的问题。
哈希冲突的概念两个不同关键字key通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
引起哈希冲突的一个原因可能是哈希函数设计不够合理那我们来看看哈希函数设计原则 1. 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间 2. 哈希函数计算出来的地址能均匀分布在整个空间中 3. 哈希函数应该比较简单 2. 比较常见的哈希函数 常见哈希函数 直接定制法--(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关 键字的分布情况 使用场景适合查找比较小且连续的情况 除留余数法--(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数 Hash(key) key% p(pm),将关键码转换成哈希地址 平方取中法--(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对 它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分 布而位数又不是很大的情况 等等....... 3. 负载因子调节(重点)
散列表的载荷因子概念 负载因子和冲突率的关系 例如 所以当冲突率达到一个无法忍受的程度时我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的那我们能调整的就只有哈希表中的数组的大小。
冲突-解决-闭散列
解决哈希冲突两种常见的方法是闭散列和开散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢
线性探测
比如上面的场景现在需要插入元素44先通过哈希函数计算哈希地址下标为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入 ·通过哈希函数获取待插入元素在哈希表中的位置 ·如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 这样插入没问题但是我们利用哈希表不只是插入元素我们还有其他操作例如删除 我们第一次删除了4根据我们之前查找的原则我第二次怎么去找到44呢我们是根据4存在才能找到44这时就发生问题了第二次删除时哈希表就认为不存在44这个元素。
那么我们有什么办法解决呢
这时就需要我们标记一下。 这就涉及到了二次探测。
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法 其中 i 123.....是通过散列函数Hashx对元素的关键码key进行计算得到的位置m是表的大小。
那么我们就按照该方法插入进数组中 无论如何二次探测的空间利用率是不高的假设负载因子时0.75那么插入第八个数据时就需要扩容了。
哈希还有一种解决方法开散列。
冲突-解决-开散列
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中所以开散列也可以叫哈希桶。
例如 开散列中每个桶中放的都是发生哈希冲突的元素。
开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。 当数据非常大的时候那么这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化也就是再对其进行树化将其转化为红黑树这个后面再讲。
所以我们的哈希桶也就是由 数组 链表 红黑树 组成的。
上述所有的一切都是为了引出HashSet(Map)的实现逻辑原理就是 数组 链表 红黑树 我们接下来用数组 链表简单模拟实现哈希桶。
模拟实现代码
public class HashBuck{static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key key;this.val val;}}public int usedSize;//存放的数据的个数public static final double DEFAULT_LOAD_FACTOR 0.75;//默认的负载因子public HashBuck () {array new Node[10];}public static final double LOAD_FACTOR 0.75;/**** param key* param val* return 代表你插入的元素的val*/public void put(int key,int val) {int index key % array.length;Node cur array[index];while (cur ! null) {if(cur.key key) {cur.val val;return;}cur cur.next;}//采用头插法进行插入Node node new Node(key,val);node.next array[index];array[index] node;usedSize;if(calculateLoadFactor() LOAD_FACTOR) {//扩容resize();}}private void resize() {Node[] newArray new Node[2* array.length];for (Node node : array) {Node cur node;while (cur ! null) {Node curNext cur.next;int index cur.key % newArray.length;//找到了在新的数组当中的位置cur.next newArray[index];newArray[index] cur;cur curNext;}}array newArray;}//计算负载因子private double calculateLoadFactor() {return usedSize*1.0 / array.length;}public int get(int key) {int index key % array.length;Node cur array[index];while (cur ! null) {if(cur.key key) {return cur.val;}cur cur.next;}return -1;}
}由于在扩容过程中地址映射不在原来的位置了所以要对其进行重新哈希 我们上面代码给的都是数字很好去比较加入我们有其他引用类型怎么比较
例如给一个老师类
class Teacher {public String id;public Teacher() {}public Teacher(String id) {this.id id;}
}
jdk提供了一个方法名叫hashCode我们来简单看看 根据这个方法计算得到一个哈希码值点进去看看 hashCode继承Object类通过这样的一个方法我们就可以把一个引用类型转换为一个整数进而进行比较。
假设还有一个老师id也是“1234”我们认为他们是同一个人但是从系统的角度来看他们又是两个对象 所以我们要对其进行重写hashCode方法通过他们的id去计算哈希码值。 通过快捷键我们重写了两个方法hashCode 和 equals equals是用于两个对象的比较。 再次运行结果如下 简单写一个泛型类型的
public class HashBuck1K,V {static class NodeK,V {public K key;public V value;public NodeK,V next;public Node(K key,V value) {this.key key;this.value value;}}public NodeK,V[] array (NodeK,V[])new Node[10];public int usedSize;public void put(K key,V value) {int hash key.hashCode();int index hash % array.length;NodeK,V cur array[index];while (cur ! null) {if(cur.key.equals(key)) {cur.value value;return;}cur cur.next;}NodeK,V node new Node(key, value);node.next array[index];array[index] node;usedSize;}
}
可以对照上面的那段代码。 结尾 虽然哈希表一直在和冲突做斗争但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个数是可控的也就是每个桶中的链表的长度是一个常数所以通常意义下我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。
