依然从我们学习自问三部曲开始，什么是哈希表？哈希表有什么用？哈希表怎么用？
那么既然说能加快查找速度，那么久不得不拿数组与链表进行比较了，数组你要查找一个元素得知道数组的下标，而链表却需要从头开始遍历，直到找到我们所需要的元素为止，这耗费大量的时间。
哈希表是怎么提高查找速度的
我们希望输入一个数的值就可以找到该数所在的位置
哈希函数构造方法
一、关键词为数字
1、直接地址法
公式：index = a*key+b
package test;
public class collectiontdemo {
public static int func(int i){
return (i-3000)/2;
}
public static void main(String []args){
int index;
int []arr = new int[1000];
//3000至3450之间的偶数
for(int i=3000;i<3450;i+=2){
index = func(i);
arr[index] = i;
}
index = func(3200);
System.out.println(index);
System.out.println(arr[index]);
}
}
2、除留余数法
公式：index = key%p
p为表的大小
package test; //将数组arr2中的九个元素进行取模，然后随机存到数组arr中 public class collectiontdemo { public static int func2(int key,int p){ return key%p; } public static void main(String []args){ int index; int p = 9; int []arr = new int[30]; int arr2[] = {999,111,0,256,333,777,9,2546,1024}; for(int i=0;i<arr2.length;i++){ index = func2(arr2[i],p); arr[index] = i; } for(int i=0;i<arr2.length;i++){ System.out.println(arr[i]); } } }
3、数字分析法
比如一个数组存了很多的电话号码，这些号码长度都为11，我们直接取值不太方便，如果我们能够以号码后四位作为判断标准，那么查找起来也比较方便
package test;
public class collectiontdemo {
public static int func3(char []value){
char a =value[1];
char b = value[3];
char c = value[4];
char d = value[2];
return (int)a*100+(int)b*10+(int)c;
}
public static void main(String []args){
String [] arr = new String [30];
int p =29;
int index;
String arr2[]={"15764914325","13846478246","13756445236","18734628132",
"13276482132"};
for(int i=0;i<arr2.length;i++){
char []arr1 = arr2[i].toCharArray();
index = func3(arr1)%p;
arr[index] =arr2[i];
}
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
}
输出结果
二、关键字为字符串
1、ASCLL码加和法
把每个字符的ASCLL码进行相加，进而得到key值
这种方法很大概率会导致哈希冲突
2、前三个字符移位法
index =（key[0]）*27+key[1]*27+key[2])mod TableSize
仍会造成冲突且会造成空间浪费
3、移位法
把所有的字母都进行移位，然后得到key(32进制)
三、哈希冲突解决办法
不同的树在通过哈希函数运算后得到的index相等，就把它们放入了相同的地址，导致数据被覆盖。哈希冲突无法避免，当数据很大而储存空间较小的时候，无论多么完美的哈希函数与方法都会存在哈希冲突，我们可以通过优化哈希函数来降低冲突的概率。
1、开放地址法
当冲突发生时，用某种探测算法在散列表中寻找下一个散列表空的地址，只要列表足够大，总会找到。按照探测序列的方法，一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。
我们用除留余数法将26、35、36记录插入表中，取模为8，然后再将18记录插入表中，发现取模后地址不为空，接下来就介绍这三种方法。
（1）线性探测法
index = a*index +i （i为递增的整数）
当2位置被占领我们就探查3位置，直到探查到5位置为空为止，当数据插入。容易出现越界，即探测完最后一个的时候全部满了，而没探测到前面却为空。
（2）二次探测法
index = a*index +i（i为1^2 , -1^2 , 2^2, -2^2 , 3^2 , -3^2……q^2, -q^2）
缺点是无法探测整个散列空间。
（3）连地址法
将所有的哈希地址相同的记录，都连接到链表当中。当有新的元素进来造成哈希冲突时，在冲突的地址链表后面加。