[Java数据结构]之哈希表如何避免冲突
前言
一、哈希表是what？
这是百度上给出的回答：
简而言之，为什么要有这种数据结构呢？
因为我们想不经过任何比较，一次从表中得到想要搜索的元素。所以就构造出来了哈希表，通过某种函数（哈希函数）使元素的存储位置与它的关键码之间能够建立一一映射的关系，方便我们在查找的时候可以更加快速的查找出来我们想要查找的元素。
在下面的代码演示中，底层就使用了哈希表，使得每一个字母与其在字符串中出现的次数是一一对应的关系；
public static void main(String[] args) {
String s="huddiolabcsjddddop";
int[] count=new int[26];
for(char ch:s.toCharArray()){
int idx=ch-'a';
count[idx]++;
}
System.out.println(Arrays.toString(count));
二、什么是哈希冲突
1.为什么会出现哈希冲突
对于两个数据元素的关键字Ki和Kj(i!=j)，但是存在：Hash(Ki)==Hash(Kj),即：不同的关键字通过哈希函数计算出相同的哈希地址，这种现象就成为哈希冲突或哈希碰撞。
2.哈希冲突能否避免
首先，我们需要明确一点，由于我们哈希表底层数组的容量往往小于实际上要存储的关键字的数量，(就是我们往往存储的元素的范围不确定的时候，可能会出现有多个元素的哈希地址是相同的），这就造成了哈希冲突是不可避免的，所以我们能做的就是尽量降低冲突率。
三、如何解决哈希冲突
1.线性探测
比如给定一个数组，int[] array={4,5,6,9,1,7,44}
其插入操作：1.通过哈希函数获取待插入元素在哈希表中的位置
2.如果该位置没有元素则直接进行插入，如果该位置有元素，则使用线性探测法找到下一个空位置进行插入。
2.拉链法
拉链法，可以认为把一个大的集合中的搜索问题转化为小集合中的搜索问题。
总结
线性探测法的的效率问题：
1.对于所有在哈希表中的元素做查找，平均比较次数是多少？
（1+1+1+1+1+5+1）/7=1.57
2.对于所有不在哈希表中的元素做查找，平均比较次数是多少？
（对每一个下标来判断是否是连续的）
(1+2+1+1+7+6+5+4+3+2)/10=3.2.
本文地址：https://blog.csdn.net/m0_46551861/article/details/109632573