哈希表原理( 二 )


装载因子越小,填入的元素越少,空间利用率越低,但空间浪费多,而且会提高扩容操作的次数 。
开放地址法
只用数组一种数据结构就可完成存储,继承了数组的优点,对CPU缓存友好,易于序列化操作 。
但是它对内存的利用率不如链地址法,且发生冲突时代价更高 。当数据量明确、装载因子小,适合采用开放寻址法 。
链地址法
1、处理冲突简单,且无堆积现象
2、由于拉链法中各链表上的节点空间在需要时创建,不必像开放地址法事先申请好足够的内存,因此对内存使用率较高,适合造表前无法确定表长的情况
3、对装载因子的容忍度较高,适合存储大对象、大数据量的哈希表
4、删除结点的操作易于实现,只要简单地删去链表上相应的结点即可 。




推荐阅读