散列表下

在上一章我们实现了对数组加链接的基础组合

大量经验丰富的的程序员给除的应用实例，基于拉链法的散列表种使用

大小为M的数组能够将插入和查找的操作效率提高M倍.

但是正常如果数据量比较大的情况下 还需对数组进行动态扩容，然后重新

散列 将数据重新填充

正常来说这个系数是0.5-0.75 ，就是比如说现在数组长度是100，

现在有效的数据是大于50个 就需要对数组进行扩容 ，一般扩容都是

小于比如说1024这个长度 就会扩容一倍，大于可能就会扩容0.5倍  

当然上述的参数都是可以自己定义的

#3 当然如果元素被删除过多的时候 散列表数组也应该进行回容的操作

我们还有一种去解决散列碰撞的方法

就是利用原始数组的空位，比如说如果发现了空间碰撞

我们可以直接将索引+1然后查看有没有空位

但是这样继续查找的成本可能会很大

比如说hash的可以本来不存在，但是我们计算后的hash是有碰撞的

这样我们机会启动一个循环 循环到空位之前 会一直查找，这样就会导致

散列查找的时间复杂度是O(N)  是不符合散列的设计初初衷的