哈希表
概念
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接口触发
网友评论