跳转到内容

哈希表

哈希函数、链地址与开放寻址、负载因子与扩容、哈希碰撞攻击。本章讲各语言标准库哈希表的实现选择(如 Swiss Table、Robin Hood),以及为什么”O(1)“在最坏情况下会退化。

  • 开放寻址对缓存更友好
  • 负载因子超过阈值就扩容,扩容是摊还的
  • 可预测的哈希函数会招致 DoS 攻击