STL——hashtable

这里对侯捷老师讲解的hashtable进行总结。

上图是hashtable解决冲突的重要方法之一：拉链法(链表地址法)，就是将位于同一个桶内的元素放到该桶所对应的链表中。注意当元素个数大于桶的个数时，我们需要将桶扩容两倍，再将原来的元素分配到新的内存中，因此桶的个数永远大于元素个数。

上图是源码中hashtable的实现，我们需要传入键，值，键相等判断条件，hash函数等，底层的桶其实是vector实现的，其中vector中的元素是node类型，每个结点其实是一个链表的结点，因此一个链表节点存储下一个指针和存储的值。hashtable的迭代器包含两个成员，一个是桶结点的位置，一个是位于该桶内相应链表的结点(上图中的cur应该指向链表中的某个节点）。

hashtable的使用，左右图对照着可以更好的观察需要的函数。其中key对应key，value对应value。hash对应着HashFcn,就是如何将key变成hashcode的函数，identity对应ExtractKey，就是如何取出key值。eqstr对应EqualKey就是判断key相等的函数。


以上两图是内部的hashfun，如果key是简单的数或char是如何计算hashcode。

在c++11及之后，均变成了unordered，但是内部实现原理没有改变。