初识哈希表【数据结构】
哈希表
- 概念
- 哈希冲突 / 碰撞
- 哈希冲突处理方法：
- 哈希函数设计
- 冲突避免
- 负载因子调节
- 冲突解决
- 1. 闭散列
- 优缺点
- 2. 开散列
- 哈希表具体实现：
- 性能分析：
- 和 Java 类集的关系
概念
前言
举例：
给定多干个整数[0，99]，在给定一个数字 n，判断 n 是否出现在刚才的集合中
1.基于顺序表： 可以用一个数组保存若干个整数，拿着 n 在数组中依次遍历，进行比较 — O(N)
2.基于链表： 可以用一个链表保存若干个整数，拿着 n 在链表中依次遍历，进行比较 — O(N)
3.基于二叉搜索树： 可以用一个二叉搜索树来保存这些整数，按照二叉搜索树的方式进行查找比较 — O(N) (比较理想的情况：OlogN)
更高效的办法：
仍然创建一个 boolea 类型的数组，100个元素位置，初始情况都为 false
现有数组：{9，5，2，7，3，6，8}，将其插入到下标与自身值相等的位置上
即：将本数组中的内容，转换为另一个数组的下标
判断 n 是否在该数组中，直接使用 n 在指定的下标位上，去数组中判断，是否为 true
时间复杂度 — O(1) (下标访问)
那么问题来了，如果数字更大，变成 [10w，10w零99]，此时，难道要创建一个长度为 10w零100 这样的数组吗？？？？如果这样做，就浪费了 [0，10w) 的空间全浪费了
此时，我们仍然可以创建一个长度为 100 的 boolean 类型的数组，将数组中的值，插入时，下标做减法(-10w)，再插入到对应的下标位置；最后再判断 n是否在数组中，仍然使用 n-10w 作为下标，去数组中判断值是否为 true
如果数字区间变成了 [0，10w]，给定数组就只有 10 个元素
此时，难道要创建一个长度为 10w 的数组吗？这样大部分空间都浪费了，我们仍然创建一个长度为 100 的 boolean 类型的数组，让元素去 %100，作为下标再插入到数组中，判断 n 也一样
哈希概念：通过某种方式(哈希函数)，把元素与其存储位置之间建立一一对应关系
把待存储元素进行了一个映射转换，转换成数组下标，我们称为 "哈希函数"
元素经过哈希函数，计算得到哈希地址
哈希冲突 / 碰撞
如果发现两个值不同的元素，计算得到的 hash 值相同，此时就成为 “哈希冲突”
(不同的元素，通过相同的哈希函数，可能会计算出相同的哈希地址)
哈希冲突处理方法：
1.先看哈希函数设计是否合理：
①哈希函数的值域必须在表格范围内
②哈希函数设计应当尽可能简单
③哈希函数产生的哈希地址应该尽可能均匀
哈希函数设计
引起哈希冲突的一个原因可能是：哈希函数设计不够合理
- 直接定制法(常用)
取关键字的某个线性函数为散列地址：Hash(Key) = A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况
- 除留余数法(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(Key) = Key % p (p<=m)，将关键码转换成哈希地址
例如上述： key % capacity
- 平方取中法
- 折叠法
- 随机数法
- 数学分析法
- …
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是哈希冲突是无法避免的
冲突避免
负载因子调节
负载因子： 通过这个指标可以衡量元素冲突的概率，可以通过负载因子的值来决定是否需要对哈希表进行扩容
即，负载因子：当前哈希表中的实际元素个数 / 数组的 capacity
闭散列：负载因子 < 1
开散列：负载因子 可以 > 1
冲突解决
解决哈希冲突的方法，主要有两种方式：
1. 闭散列
核心思路：在冲突位置开始，按照某种方式往后找到一个合适位置来存放这个冲突的元素
- 线性探测
从发生哈希冲突的位置开始，逐个挨个依次往后查找，如果走到空间的末尾就从头开始
下面的图是采取的 [闭散列] 中的 [线性探测] 的方式来进行存放的
一旦涉及到哈希冲突，此时哈希表的基本操作的时间复杂度，就不是严格的O(1)了，随着冲突越严重，效率就会越低
正因为如此，在选择哈希表的长度的时候，就有说法，一般都要选一个比较大的值(例：若集合中有100个元素，就最好整一个1000个元素的数组)，如果数组元素个数选的较大，冲突概率会降低，但浪费的空间也更多了，终究是时间空间之间的权衡~~
- 二次探测
H(i) = H 0 _0 0 ± i2
H 0 _0 0：第一次计算出来的哈希地址
若计算出来的值，越界了，则可以取模，% capacity ，还未找到再继续探测即可
优缺点
- ①线性探测：
优点：处理哈希冲突的方法简单 — 逐个依次往后查找
缺点：容易产生数据的堆积 — 一旦发生冲突，数据就容易连成一片 - ②二次探测：
优点：解决了线性探测数据堆积的问题
缺点：当表格中元素不断增多，二次探测可能需要找的次数更多
2. 开散列
数组+ 链表
核心思路：在冲突位置，存一个 key 的链表，依次往后存节点
对于开散列来说，如果哈希冲突比较严重，可以把每个元素上挂的链表改成一个二叉搜索树(标准库中的HashMap就是采取这种方式)或者另外一个哈希表~
标准库中这种处理方式，若发现链表过长，就会把链表的结构调成 红黑树 的结构
哈希冲突，理论上是避免不了的，但是可以通过开 / 闭散列的方式来处理冲突，虽然出现冲突，只是影响到效率，而不会影响到增删改查结果的正确性
哈希表的 插入、删除、查找的时间复杂度近似为 O(1)，最终是多少，取决于 哈希冲突 的严重程度
如何更接近 O(1) ：
- 让数组长度更长一些
- 选择更合理的哈希函数(例如，%素数…)
- 对于开散列来说，若哈希冲突比较严重，可以把每个元素上挂的链表改成一个二叉搜索树，或者另外一个哈希表
- 开散列 / 哈希桶
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索
冲突严重时的解决办法：
上述说，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题，那如果冲突严重，就意味着小集合的搜索性能其实也是不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：
- 每个桶的背后是另一个哈希表
- 每个桶的背后是一棵搜索树
哈希表具体实现：
package Date20211126;public class MyHashMap {// 节点类static class Node{public int key;public int value;public Node next;public Node(int key, int value) {this.key = key;this.value = value;}}// 负载因子private static final double LOAD_FACTOR = 0.75;private Node[] array;private int size = 0;public MyHashMap(int initCapacity){initCapacity = initCapacity <= 0 ? 16 : initCapacity;array = new Node[initCapacity];}// 哈希函数private int hashFunc(int key){return key % array.length;}// 插入元素// 若 key 已经存在，就修改当前的 value 值// 若 key 不存在，就插入新的键值对public int put(int key,int value){// 1.把 key 映射成数组下标int index = hashFunc(key);// 2.根据下标找到对应的链表Node list = array[index];// 3.当前的 key 在链表中是否存在for (Node cur = list; cur != null;cur = cur.next) {// key 已经存在,直接修改 value 即可if(cur.key == key){int oldValue = cur.value;;cur.value = value;return oldValue;}}// 4.循环结束，没有找到相同 key 的节点，直接插入到指定链表的头部Node newNode = new Node(key,value);newNode.next = list;array[index] = newNode;size++;if(size / array.length > LOAD_FACTOR){resize();}return value;}// 扩容private void resize() {Node[] newArray = new Node[array.length * 2];// 将 原哈希表 中的所有元素搬运到 新数组 中for (int i = 0; i < array.length; i++) {for (Node cur = array[i];cur != null;cur = cur.next){int index = cur.key % newArray.length;Node newNode = new Node(cur.key,cur.value);newNode.next = newArray[index];newArray[index] = newNode;}}// 新数组代替原来数组array = newArray;}// 查找元素// 根据 key 查找指定元素// 如果找到返回对应 value,否则 返回 nullpublic Integer get(int key){// 1.先计算出 key 对应的下标int index = hashFunc(key);// 2.根据下标找到对应的链表Node list = array[index];// 3.在链表中查找指定元素for (Node cur = list;cur != null;cur = cur.next){if(cur.key == key){return cur.value;}}return null;}// 查找到，返回对应值，否则返回 默认值public Integer getOfDefault(Integer key, Integer value){Integer ret = get(key);if(ret != null){return ret;}return value;}// 删除元素public Integer remove(int key){// 1.先计算出 key 对应的下标int index = hashFunc(key);// 2.根据下标找到对应的链表Node list = array[index];// 记录待删除的前一个节点Node prev = null;// 3.在链表中找到指定元素for (Node cur = list;cur != null;cur = cur.next) {if (cur.key == key) {Integer oldValue = cur.value;// 要删除的节点刚好是第一个if (array[index] == cur) {array[index] = cur.next;} else {prev.next = cur.next;}cur.next = null;--size;return oldValue;}// 这样写会 触发空指针异常
// if(cur.next.key == key){
// int oldValue = cur.value;
// cur.next = cur.next.next;
// return oldValue;
// }
// }
// size--;}return null;}// 是否包含keypublic boolean containsKey(Integer key){return null != get(key);}// 是否包含 value// O(n)public boolean containsValue(int value){for(int i = 0; i < array.length; i++){Node cur = array[i];while(cur != null){if(cur.value == value){return true;}cur = cur.next;}}return false;}public int size(){return size;}自行检测：
public static void main(String[] args) {MyHashMap hashMap = new MyHashMap(10);int[] array = {9,5,2,7,3,6,8};for(int i = 0; i < array.length; ++i){hashMap.put(array[i], array[i]);}System.out.println(hashMap.size()); // 7hashMap.put(7, 8);System.out.println(hashMap.size()); // 7System.out.println(hashMap.get(7)); // 8System.out.println(hashMap.getOfDefault(7, 7)); // 8System.out.println(hashMap.getOfDefault(10, 10)); // 10System.out.println(hashMap.containsKey(7)); // trueSystem.out.println(hashMap.containsValue(7)); // falsehashMap.remove(7);System.out.println(hashMap.containsKey(7));}
性能分析：
虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入 / 删除 / 查找时间复杂度是 O(1)
和 Java 类集的关系
- HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
- java 中使用的是哈希桶方式解决冲突的
- java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
- java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法；所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！