拉链法和再哈希法实际使用有何区别及优缺点?

1 个回答

  • 张道陵
    须知少日擎云志,曾许人间第一流。

    拉链法是把冲突的关键字挂到同一个桶的链表上,再哈希法是冲突后再换一个哈希函数重算地址,直到不冲突。实际用起来,拉链法适合经常插入删除、事先定不了表长;再哈希法靠多次散列避开冲突,不容易聚集,但计算更贵。
    拉链法每个桶用链表存放映射到同一位置的关键字。插入和查询最多看装载因子那么多项,可以当成常数时间。要删除的话,这条链得做成双向链表,改前驱指针就能把结点摘掉,同样是常数时间。它处理冲突简单,不是同义词的关键字不会互相撞,所以没有堆积,平均查找更短。结点是用到才申请的,造表前不知道有多少元素也行,装载因子可以大于等于1。记录本身比较大、数量又经常变时,多出来的指针几乎可以忽略,也不用整表调整。缺点是指针要额外占空间,记录很小的时候并不划算。记录散在内存各处,查找要顺着指针跳,比紧凑数组多一次开销,用了指针也不容易序列化。
    再哈希法会同时准备多个不同的哈希函数。第一个函数算出的位置已经有元素,就用下一个函数再算,直到不再冲突。这样不容易产生聚集,但每次冲突都要重新散列,计算时间会增加。

    参考来源:https://www.cnblogs.com/papering/p/10019505.html
    发布于 2026-11-11 04:35 •IP属地 青海
    举报
    评论
    收藏