散列表:如何去优化一个可用的散列表

散列表的查询效率并不能笼统地说成O(1),它给散列表函数,装载因子,散列冲突都有关系

问题 如果散列函数将所有的数据都散列到同一个槽里,如果我们使用的开链方式,那么效率从O(1)退化到O(n)

  如何设计散列函数

• 均匀化
• 避免冲突

 装载因子

      装载因子越大,说明散列表中元素越多,空闲位置越少,散列冲突的概率越大,链长,查询慢.

      方法:

      动态扩容:当装载因子过大时,我们可以进行动态扩容,重新申请更大的散列表,将数据搬移到新散列表中,

申请空间为前者的一倍.

     扩容过程

在未孔融时,时间效率为O(1),扩容时,时间复杂度为O(n).

我举一个极端的例子,如果散列表当前大小1GB,要想扩容为原来的两倍大小,那就需要多1GB的数据重hash,并且从原来的散列表转移到新的散列表,一次性 扩容机制 在CPU密集性操作下,会让用户崩溃.

解决方法:当装载因子满载时,我们申请新的空间,但不将老的数据搬移到新的散列表中,

当一个新数据插入时,我们将新数据插入到散列表,,并且从老的散列表拿出一个数据放入到新散列表中.

查找时,我们先从新的散列表中查找,然后在去老的散列表.

 

对比冲突解决的方法

   开放寻址法

      优点:

         散列表存储在数组中,可以有效的利用CPU缓存加快查询速度,

      缺点:

          删除数据的时候比较麻烦,需要标记删除的数据.冲突代价高 ,装载因子的上限不能太大  

    链表法

       优点 :

        内存利用率高,对大装载因子的容忍度更高

        缺点:

       存储至真,对于较小的对象存储是比较消耗内存的      

       改进:  将开链中的链表改造为红黑树结构,提高查询速度 ,优化至O(logn),可以做并发安全,