哈希函数特性:
1.离散性 输入仅仅只要有一点点不同便会导致输出完全不一样 即分布离散
2.均匀性 输出均匀分布,将输出比喻为点,即输出范围(圈)内,设定一个范围框,框中点的出现次数一致。
输入范围 无穷 输出范围 有限 存在哈希碰撞 不同输入出现同个输出。
哈希表:
数组+链表实现
[link1,link2,link3,link4…………]
有一个设定扩容数 如 8,当link中个数出现 >= 8 ,说明需要扩容(因为均匀性分布),扩容复杂度为 logN。
每次扩容需重新计算,因此 复杂度O(N)。那么N次扩容需 O(NlogN)次。
平均 O(N logN)/N = O(logN)次
398.随机数索引 待做
