《STL基础之hashtable》

【hashtable导读】STL为大家提供了丰富的容器，hashtable也是值得大家学习和掌握的基础容器，而且面试官经常会把它和hashmap混在一起，让同学们做下区分。因此关于hashtable的一些特性，比如：底层的数据结构、插入、查找元素的时间复杂度，这些很有必要和大家一起分享下。

开门见山，hashtable设计的初衷就是为了方便元素的快速插入、查找，到底有多快速呢？查找、删除元素的时间复杂度为O(1)，那支持时间复杂度为O(1)的数据结构，无非就是数组，比如：vector。vector其实就是操作系统为大家分配的一段连续的内存空间，支持随机跳转访问。

因此根据上述推论，hashtable底层的数据结构肯定是含有vector这个数据结构的。但只有vector还是不够的，因为操作系统的内存空间有限，要支持存储海量数据，而且这些海量数据都存放在连续的内存中，肯定不现实，比如：笔者有1000万个，大小为3字节的随机字符串，我们如果把这些数据存放在一段连续的内存空间中，我们就需要申请长度为10000000的指针数组，依次存放这些字符串，总共占用内存大小将近410010000字节，也就是38G多！很恐怖。

char* strArr[1000*10000];
for (int i = 0; i < 1000 * 10000; ++i)
    strArr[i] = "xx" + std::itoa(rand() % 10);

而且strArr还存在一个问题，如何去快速地查找，指定地某个元素？strArr只支持下标访问，比如：strArr[10]、strArr[1000]这种方式去获取第11位、1001位的字符串。

因此为了能实现以下标地方式去获取指定地字符串，hashtable实现了比较完备的hash函数，将指定的字符串计算成特定的哈希值（整数值），再对hashtable底层的vector的大小Size进行求余，便可得到该字符串对应的哈希值再vector中索引值。
在这里插入图片描述
那么就实现了以O(1)的时间复杂度定位到指定字符串的位置，那字符串应该存到哪里？注意上图中的vector并不是一个空的vector，vector中存储的元素类型就是__hashtable_node，STL是这样定义这个节点的。

template <class Value>
struct __hashtable_node
{
  __hashtable_node* next;
  Value val;
}

其中next指针指向下一个节点，val便用来存储指定的字符串。可以这么理解，vector中每个单元便是链表的头节点，如果有其它的字符串的哈希值也是2，那么就在索引值为2的单元下扩展这个单链表。效果图如下：

在这里插入图片描述
假如有其他的字符串“abc”，经过hash计算得到的索引值也是2，那么“abc”应该怎样插到这个链表中。我们直接看STL源码，针对哈希冲突的场景，看字符串是如何被插进去的？


template <class V, class K, class HF, class Ex, class Eq, class A>
pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, bool>
hashtable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const value_type& obj)
{
   //bkt_num就是就算插入对象的哈希值为n
   const size_type n = bkt_num(obj);
   //取出vetor中索引值为n的节点
   node* first = buckets[n];
   for (node* cur = first; cur; cur = cur->next)
   {
       if (equals(get_key(cur->val), get_key(obj))
            return pair<iterator, bool>(iterator(cur, this), false);
   }
   //使用头插法将obj插入到索引值为n的单元下的链表中去
   //使用头插法，所以时间复杂度一直为O(1)
   node* temp = new_node(obj);
   temp->next = first;
   buckets[n] = temp;
   ++num_elements;
   return pair<iterator, bool>(iterator(temp, this), true);
}

有点需要注意，如果插入失败，就返回链表中头结点。介绍完插入节点，那查找节点的流程又是怎样的？


iterator find(const key_type& key)
{
  size_type n = bkt_num_key(key);
  mode* first;
  for (first = buckets[n]; first && !equals(get_key(first->val), key);
  first = first->next)
  {}
  return iterator(first, this);
}