概述

• 空间足够时：每个元素独自占据空间中的一个位置
• 空间不足时（哈希表）：元素映射到空间中的某个位置，当元素数量多时可能发生碰撞

基于链表的优化

通过链表将碰撞的元素串在一起

• 基于链表优化的搜索性能：
  • 如果链表长度较短，搜索速度仍然较快
  • 如果链表变得很长，则性能会大幅下降
• 判断链表是不是过长的标准：
  • 当元素个数大于篮子（bucket）数量时，说明链表过长了
• 链表过长时需要重新打散：

  • 篮子数量增长（增长到两倍原长度附近的一个质数，增长规则被硬编码）

    

  • 所有元素进行重新映射（rehashing）

容器hashtable

模板参数

• Value：值的类型
• Key：key的类型
• HashFcn：函数对象，将元素进行映射的方式（计算hash code）
• ExtractKey：函数对象，从value中提取出key的方式（类似红黑树中的KeyOfValue）
• EqualKey：函数对象，key的比较规则（类似红黑树中的Compare）
• Alloc：分配器

数据成员