Hash查找与HashMap

HHash地址的确定

直接hash函数

H(key)=a*key+b

取关键字本身或者关键字的某个线性函数值作为hash地址

数字分析法

通过对数据关键字的提取和观察，结合对数据总量的分析，得出合理的hash地址的大小，以及hash地址的函数

(找出数字的规律，利用数字构造出冲突较小，大小合理的散列地址)

发现4，6两列的数字结合起来可以唯一的标识每个数据值，则将4,6两列的数字结合起来为散列的地址。

平方取中法

H(key)=key^2的中间几位

例子：

请为BASIC源程序中的标识符建立一个hash表，假设BASIC语言中允许的标识符为一个字母，或者一个字母加上一个数字，标识符在计算机中的八进制数为其关键字

ASCII码链接：https://baike.baidu.com/item/ASCII/309296?fromtitle=ascii%E7%A0%81&fromid=99077&fr=aladdin

取简化关键字2-4位为哈希地址

具体取几位需要考虑总的哈希表的大小，比如26个英文字母加上10个数字，总共26+26*10=286个，取3位数字存储足矣。

折叠法

当关键字位数较长，可将关键字分割成位数相同的几部分，将这几部分的和取为hash地址，适合位数特别多的情况

除留余数法

取关键字被某个不大于hash表长度m的数p除后的余数作为哈希地址，即:

H(key)=key MOD p(p<=m)

其中,p的选择很重要，如果选的不好，会产生很多的冲突，比如，key很多是10的倍数，而p为10

这个p一般选择一个质数

冲突处理方法

开放定址法

换个位置放置

h(key)=(h(key)+di) mod tableSize //1<i<tableSize

线性探测，平方探测，双散列

i +=i^2 i*h

性能分析

例子,tableSize取质数11

成功平均查找长度：

ALS=查找次数(冲突次数+1）/总数

即ALS s=(1+1+2+1+1+4+2+4+7)/9=2.56

不成功平均查找长度：

不在散列表中关键字的查找次数，比如我现在放置不在散列表中的数22，那么需要查找11,30，然后确认22,3次

根据哈希函数地址为MOD11，因此任何一个数经散列函数计算以后的初始地址只可能在0~10的位置（11,12的位置原本就是为散列准备的）

ALS u=（3+2+1+2+1+1+1+9+8+7+6)/11=3.73

例2

ALS s=(1*5+2+3+5)/8=1.87

ALS u=(9+8+7+6+5+4+3+2+1*18)/26=2.38

平方探测法

以增量序列1^2,-1^2,2^2,-2^2....

di=+i^2,-i^2...

例：一组数，tableSize=11,MOD 11

ALS s=(1+1+2+1+1+3+1+4+4)/9=2

平方探测的问题：可能一直找不到空位

例如：

插入11，平方探测会一直在0，2之间反复横跳

有定理显示，如果散列表的长度是4k+3(k为正整数)的素数，平方探测法就能够到达整个空间

分离链接法

将相应位置上的所有冲突的元素存储在同一个单链表上

例子：47,7，29,11,16,92,22，8,3,50,37,89，94,21

ALS s=（9*1+2*5)/14=1.36

性能分析

线性探测法

α为散列表的装填因子，其数值为已装填的元素个数/散列表容量

如已装填9个元素，总元素为13，即α为9/13

平方探测法

分离链接法

HashMap

https://blog.csdn.net/hqy1719239337/article/details/83044449?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task