HashMap O(1) 复杂度的分析

**C++**在使用STL时，经常混淆的几个数据结构，map,hash Map,unordered_map事实上，三个容器，有着比较大的区别.

• Map
  内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。
  所以复杂度为 O(LogN)

• Hash map

基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域(桶)进行保存。

插入

1. 得到key, 通过hash函数得到hash值
2. 根据hash值 找到对应的桶号(区域)， hash值对(桶数)求模
3. 存放key和value 在对应桶内

取值
分四步：

1. 判断key，根据key算出索引。
2. 根据索引获得索引位置所对应的键值对链表。
3. 遍历键值对链表(当每个桶内只有一个元素时,查找时只进行一次比较)，根据key找到对应的Entry键值对。
4. 拿到value。

分析：
以上四步要保证HashMap的时间复杂度O(1)，需要保证每一步都是O(1)，现在看起来就第三步对链表的循环的时间复杂度影响最大，链表查找的时间复杂度为O(n)，与链表长度有关。我们要保证那个链表长度为1，才可以说时间复杂度能满足O(1)。但这么说来只有那个hash算法尽量减少冲突，才能使链表长度尽可能短，理想状态为1。因此可以得出结论：HashMap的查找时间复杂度只有在最理想的情况下才会为O(1)，而要保证这个理想状态不是我们开发者控制的。

hash 冲突
　　通常大家所说的哈希函数也可以称为散列函数，哈希函数的功能只是将你的目标key通过一种映射方法，也可以说是一种函数运算f，最后得到你目标的hashValue = f(key)，这里的函数f就称为哈希函数/散列函数。
　　可以看到哈希函数的选择是一个很关键的步骤。为了引进哈希桶算法，必然要介绍一下哈希冲突，因为哈希桶就是为了解决哈希冲突的。举个例子，有一组序列为[1,2,3,4,5,6,7,8,9]，使用的哈希函数为f(key) = key mod 5，那么依次得到的hasvalue就是[1,2,3,4,0,1,2,3,4]，显然在key值为1，6的时候得到的哈希值都为1，如下所示：

　　这个时候就产生了冲突了，也就是不同的key通过映射后得到了同样值的hashvalue。而所谓的哈希桶算法其实就是链地址解决冲突的方法，如上面的例子所示，就可以设置桶的个数为5，也就是f(key)集合的个数，而这样的话，hashvalue就可以作为桶的索引，将1,2,3,4,5分别通过f(key)得到1,2,3,4,0，则可将这几个key放入桶1,2,3,4,0的首地址所指的内存中，然后处理值为6的key，得到hashvalue值为1，这个时候需要放入桶1中，但桶1的首地址已经有了元素1，怎么办？那么就可以为每个桶开辟一片内存，内存中存放所有hashvalue相同的key，冲突的key之间用单向链表进行存储，这样就解决了哈希冲突，在查找对应key的时候，只需要通过key索引到对应的桶，然后从桶的首地址对应的节点开始查找，就是链表顺序找到，对比key的值，直到找到对应key的信息，所以，在冲突的时候，特别是冲突率比较高的时候，桶内的链表就会很长，使得查找效率比较低，而在最坏的情况下，所有的key都对应同一个hashvalue，当然这种情况不会出现，这样的哈希函数选取的也没有意义了，假设这种情况出现，那么哈希表就退化成了单链表，其他桶内存浪费，且将查找效率从O(1)直接降到了O(N)，所以上面才说，哈希函数的选择也是很关键的。

• Unordered_map
  C++ 11标准中加入了unordered系列的容器。unordered_map记录元素的hash值，根据hash值判断元素是否相同。map相当于java中的TreeMap，unordered_map相当于HashMap。无论从查找、插入上来说，unordered_map的效率都优于hash_map，更优于map；而空间复杂度方面，hash_map最低，unordered_map次之，map最大。