算法思维(长期更)

哈希思想(散列表)

• 根据关键字的值来计算出关键字在表中的地址

• 解决哈希冲突

  • 直接定址 取关键字或关键字的某个线性函数为Hash地址，即H(key)=key 或 H(key)=a x key + b

  • 数字分析 分析原则是尽量取冲突少的字段，适用于关键字位数比较多，且关键字已知

  • 平方取中 取关键字平方后中间几位数的值作为Hash值，因为中间几位数和数的每一位数都相关，随机性更大

  • 除留余数 取关键字被某个不大于Hash表表长m的数p除后所得的余数即为hash地址，H(key)=key mod p (p<=m=lenth) ，一般p 选不于表长的最大素数

  • 链地址法 根据以上方法如果算出重复的Hash值，则将该Hash值对应的数以链表形式追加到末尾，若Hash值相等且key也相等则进行替换

抽屉思想

• 把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件(定理1)

• 应用

  • 去重。将包含一个重复数的连续的6个数字分别放进5个盒子里，找出重复数。

布隆过滤

• 概述：布隆过滤器，本身是一个很长的二进制向量，存放的不是0，就是1。当存入数据时经过不同的算法算出数据的地址，并存入则位置向量值为1，查询一个数据是否存在时，就使用相同的算法算出该数据在二进制向量中对应地址处值是否为1，为1 则数据极高可能存在，否则不存在；因为hash冲突无法避免，所以海量数据时同一向量位置值可能已经为1了。

• 意义：海量请求请求缓存中不存在的id，就会去向数据库发起请求，利用布隆过滤，可以在访问数据库之前判断该id是否不存在数据库中，若不存在则不会访问数据库；

• 弊端：只能判断数据一定不存在数据库，而无法判断数据一定存在数据库，并且随着访问量巨增，误判率也会增加

非常思想

1. (最小正整数)若数组的长度大于等于数组中的最小值，则最小值一定包含在数组长度内部，for循环0~lenth 即可得最小值；若数组的长度小于数组中的最大值，则最下正整数为1。缺失的第一个正数