散列表(哈希表)

1 散列表的引入

如果我们叭者几个学生按照顺序存储存入到下面这个数组的话，那么每一次的查找方法只有顺序查找或者折半查找，最低的时间复杂度也就只可以下降到(logn)，但是时间复杂度还是可以下降，下降到O(1)

我们只要把对应的学号当成对应的数组小标，然后按照学号放入到数组下标就可以找到对应的学生，这样时间复杂度为O(1)

这个表就是散列表，也叫哈希表

2 散列表的散列函数

散列函数分为两种函数
1 直接定制法
f( x ) = kx + b f( x ) = a这种
 

这种方法一般是用到关键字一般都是基本连续的情况，否则会浪费大量的空间

2 除留余数法

我们可以运用除留余数法来进行映射到对应的位置，但是这方法很容易发生冲突，也就是哈希冲突，当我们P可以设置成小于等于表长的最大质数

装填因子就是表中的元素 / 表长 = 装填因子，装填因子越大的话，冲突可能性会更大
装填因子越笑，肯可能越小，但是空间浪费就比较高，所以我们可以指定这个装填因子的大小来设计我们的表

3 应对哈希冲突的方法

当我们进行删除操作的时候，要标记为删除的标记，初始化的标记与删除的标记不一样，删除的标记是你下一次填入值还可填入，查找的时候不会断层

1 线性探测法
 

我们根据我们设计的求余，对应到对应的表格位置，然后把数字放入进去，然后当下一次数字放的时候冲突了，就往后面进行走，走到没有放置的位置，如果从7开始走到11都没有位置就走到0开始放入，找一个空闲的位置

ASL的计算
 

ASL成功 = （1 + 7 + 1 + 2 + 1 + 2 + 1 + 4 + 4）/ 9 = 23 / 9

ASL失败 = (3 + 2 + 1 + 1 + 3 + 2 + 1 + 8 + 7 + 6 + 5) / 11 = 39 / 11

注意为什么要除以11，这里的11是表示的为哈希表所映射的范围
但是这种方法容易发生聚集的现象，就是把很多的数字放到一起

2 平方探测法

就是没放一个数字，如果放生冲突就按照上面给我们数字的顺序给key加值，这样就可以放到各个不同的位置

3 拉链法

就是在对应的位置构建一个链表，这样就可以避免很多的冲突，这里是可以删除对应的元素的