【C++】HashMap原理、与Map的区别

原理

哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

• 得到key
• 通过hash函数得到hash值
• 得到桶号(一般都为hash值对桶数求模)
• 存放key和value在桶内。

其取值过程是:

• 得到key
• 通过hash函数得到hash值
• 得到桶号(一般都为hash值对桶数求模)
• 比较桶的内部元素是否与key相等，若都不相等，则没有找到。
• 取出相等的记录的value。
• hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).

由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

实现

hashmap的实现用到了数组、链表、红黑树。
数组：查询速度快，可以根据索引查询；但插入和删除比较困难；
链表：查询速度慢，需要遍历整个链表，但插入和删除操作比较容易。
hashmap是数组和链表组成的，数据结构中又叫“链表散列”。单线链表如果长度超过8的话会变成红黑树。


扩容

Hashmap的扩容并不是为单线链表准备的，单线链表只是为了解决hash冲突准备的。也就是说当数组达到一定长度，比如说hashmap默认数组长度是16，那么达到出发条件，数组存储比例达到了75% ，也就是16*0.75=12的时候就会发生扩容

与Map比较

1. STL的map底层是用红黑树实现的，查找时间复杂度是log(n)；
2. STL的hash_map底层是用hash表存储的，查询时间复杂度是O(1)；
3. 什么时候用map，什么时候用hash_map？
   这个要看具体的应用，不一定常数级别的hash_map一定比log(n)级别的map要好，hash_map的hash函数以及解决地址冲突等都要耗时间，而且众所周知hash表是以空间换时间的，因而hash_map的内存消耗肯定要大，一般情况下，如果记录非常大，考虑hash_map，查找效率会高很多，如果要考虑内存消耗，则要谨慎使用hash_map。