408第一季 - 数据结构 - 散列表

散列表

概念

散列表本身就是为了查找

原始人思想

散列表思想

6%5 是 1

1%5 也是1 冲突

冲突怎么办？

线性探测法

就往后找，1跑到索引为2

然后查找，可以发现，只要没冲突就只用查找1次

然后你想找10的话，发现索引为0的地方什么都没有，所以查1次为空就结束

然后这个方法空间用的多，但查的快

然后这里失败情况解释一下

1是%之后为0的情况

3是%之后为1的情况，也就是说要往后找3次才看见空

这上面是没有循环的情况下的

当然，这个表是可以循环的，比如我们想插个24，就会到索引为0这里，查找的话也一样

删除

这里把9删了的话，4就查不到了，怎么办

那就可以把9下面弄个False，变成逻辑删除就行，并不是真正的删除

然后还有二种散列表存放的方法

上面这些ab上面的都是题目会给你的

然后还要一些处理冲突的方法

这写的什么玩意，具个例子就知道了

这里9占了索引为4的之后，4不得不去索引为5的地方

因此索引为5的本来是为所有余数为5的数开放，但现在余数为4的也放进去了，所以就是上面说的即向同义词开放，也对非同义词开放

拉链法

这种不仅要串起来，还会排个序，不过也可以不排序

线性探测法的小例子

这里第2行是余数，第三行是查找次数

然后是找失败的，找空位置

装填因子

装填因子就是看表放的多满，这里4/7

 散列函数如果是对2取余肯定比对100取余更容易发生冲突

做题

1

2

这里到索引为4的时候，是逻辑删除，并不是真正的删除，所以还得往后查找，查找到索引0是空，所以查找了2次

c