2018-11-04 #little hash table#

哈希表

概念

hash table，key直接映射到存储位置的数据结构，插入和查找需要的计算量跟表的大小没关系，也就是所谓的O(1)。
不同的Key会被分散到表的各个位置，相同的Key总是对应着相同的存储位置。

冲突

常见的解决冲突的方式：link-list 或 open addressing
链表法： 如果产生冲突就在原地形成一个链表，但是这样理论上最坏的情况，所有的key都计算为同一个位置存储，那么哈希表退化成链表，查找和插入的复杂度都变成O(n)。

设计

在手撸了一个简单的hashtable后，总结一些设计上的细节

• 基础的hash函数单独作为一个函数，仅提供尽量随机的索引计算
• 碰撞检测单独作为一个函数(要承载冲突检测，可用索引探查，查重)
  类似于 bool collisiondetect(int& index, const Keytype key)
• 查找接口使用基础hash&碰撞检测加对比逻辑
• key要存储在元素类里面
• insert其实要用到find,哈希表的扩容仅在insert接口触发