比较并对比散列表和STL map。
如果输入的数据量不大，可以选用哪些数据结构替代散列表？
在散列表里，值的存放是通过将键传入散列函数实现的。值并不以排序后的顺序存放。
此外，散列表以键值找出索引，进而找到存放值的地方，因此，插入或查找操作均摊后可以在O(1)时间内完成。（假定该散列表很少发生碰撞冲突）
散列表还必须处理潜在的碰撞冲突，一般通过拉链法解决（chaining），也就是，创建一个链表来存放值，这些值的键都映射到同一个索引。
STL map的做法是根据键，将键值对插入二叉查找树，不需要处理冲突。因为树是平衡的，插入和查找的时间都是O（logN）。
散列表时如何实现的？
传统上，散列表都是用元素为链表的数组实现的。想要插入键值对时，先用散列函数将键映射为数组索引，随后，将值插入那个索引位置对应的链表。
在数组的特定索引位置的链表中，各个元素的键并不相同，这些值的hashFunction(key)才是相同的。
因此，为了取回某个键对应的值，每个结点都必须存放键和值。
总之，散列表以链表数组的形式实现，链表中每个结点都会存放两块数据：值和原先的键。此外还要注意以下设计准则：
1. 我们希望使用一个优良的散列函数，确保能将键均匀地分散开来。若分散不均匀，就会发生大量碰撞冲突，那么查找元素的效率会变得非常低下。
3. 我们可能还希望设法根据容量动态扩大或缩小散列表的大小。例如，当元素数量和散列表大小之比超过一定阈值时，可能会希望扩大散列表的大小。
这意味着需要新建一个散列表，并将旧的散列表条目转移到新的散列表中。但这种操作开销非常大，不可频繁操作。
如果输入的数据量不大，可以选用哪些数据代替散列表？
可以使用STL map或二叉树。尽管它们的插入需要O(logN)时间，但如果数据量不大，这点时间可以忽略不计。
原文链接：https://www.f2er.com/datastructure/382620.html