无语了... 哈希表， 在编程世界里是个大明星，速度快，查找效率高。但现实是数据有时会“撞车”，这就是哈希表碰撞。要搞清楚怎么处理这些撞车事件，就得看链地址法和开放定址法了。这篇文章咱就用接地气的语言，好好唠唠。

什么是哈希表碰撞？

想象一下你开了一家快递公司，每个包裹都有一个编号。如果两个包裹的编号一样，那可就麻烦了。这就是“撞车”！ 两个不同的键产生的哈希值相同，这就是碰撞。所以解决办法就是把撞进来的包裹放到同一个区域里这样查找起来就方便了。

链地址法：让冲突的包裹都挤到一起

原理

链地址法就像给每个货架挂上一个列表。当有撞车事件发生时所有撞进来的包裹都挤到同一个列表里。 有啥用呢？ 这样查找的时候，先找哈希值对应的货架，然后沿着列表一个个找下去。

实现细节

template  class ChainHashMap { // 改名为ChainHashMap以避免与标准库冲突  //简化示例代码  struct Entry { K key; V val; };  std::vector buckets;  size_t num_elements = 0;
//插入操作简化示例 
//... 实现insert函数等其他方法 

优点

• 实现简单
• 可以存储任意负载因子
• 删除元素时释放内存

缺点

• 需要额外的内存存储链表
• 如果链表太长，查找效率反而下降

开放定址法：让冲突的包裹自己找下一个空位

开放定址法就好比快递公司每个货架都有个排号顺序。当有新的包裹进来时先按照原来的排号找空位。如果没空位，就顺着排号下一个空位再找；以此类推。 这就是“探测”过程。

探测方式

• 线性探测下一个空位直接跳到下一个；
• 二次探测下一个空位是 % size；

代码示例 ： template class OpenAddressingMap { // 改名为OpenAddressingMap以避免与标准库冲突 struct Entry { K key; V val; enum { EMPTY, VALID, DELETED } state;} data; size_t probe const {}; 也是没谁了... // TODO 实现probe函数 ... }. . . . ` . . .. . .. . . .. . . . . . . .. .. .. .` .