hash表 C++的使用以及理解
1、哈希表
定义
哈希表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
优点
可以为寻址带来遍历。由于哈希表的键和值是对应的，查找起来会比较迅速。但是相对的，插入和删除的效率会变低。比如1、2、3、4、5、6、7、8、9、10 这十个数字，通过对3取余的方式获得下标，当我们想知道某个数字存储位置的时候，只需要用数字除以3，就可以获得下标。
目的
hash表是通过映射的方式，将键值计算出下标。如果映射函数会存在多个键值映射成相同的值的时候，可以采取例如向两边存放等方式，充分利用申请的空间。
方式
1、直接定址法：取关键字key的某个线性函数为散列地址，如Hash(key) = key 或 Hash(key) = A*key+B；A,B为常数
2、除留取余法：关键值除以比散列表长度小的素数所得的余数作为散列地址。Hash(key) = key % p;
3、平均取中法：先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。
4、折叠法：把关键码自左到右分为位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到具有关键码的记录的散列地址。分为移位法和分界法。
5、随机数法：选择一个随机函数，取关键字的随机函数作为它的哈希地址。
6、数学分析法：设有N个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种符号出现的机会均等；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
2、STL中的hash表
STL模板中存值和取值
存值：1.得到key
2.通过hash函数得到hash值
3.得到桶号(一般都为hash值对桶数求模)
4.存放key和value在桶内。
取值：1.得到key
2.通过hash函数得到hash值
3.得到桶号(一般都为hash值对桶数求模)
4.比较桶的内部元素是否与key相等，若都不相等，则没有找到。
5.取出相等的记录的value。
哈希冲突
hash表可能多个key值映射为相同的下标，称为哈希冲突，当发生这种情况便需要花费多余的资源去寻找可以存储的下标
时间换空间
在创建hash表的时候要提前知道数据的规模，如果表创建的很大，那么时间上很快，但是浪费空间；如果空间小，造成的冲突次数多，那么会造成查询效率低下
在STL模板中，是为了申请的空间的每一个下标建了一个桶，当多个键值映射为相同的下标，就会把所有的键值在桶中存储起来。当我们通过映射找到桶的编号的时候，去桶中查找是否有自己的键值。
map、hash_map、unordered_map的区别
map：map的内部并不是哈希表，而是通过红黑树来实现的。
hash_map：hash_map内部是上述哈希表。
unordered_map：与hash_map差不多
map与hash_map的差别：区别是实现的方式不一样，map是一个二叉树，它的存储空间要比hash_map小上很多，并且数据是排号序的，map消耗的空间非常多，但是查找起来十分迅速。在使用的时候，若不计较空间时间，用途基本类似
3、哈希表例题：
LeetCode第一题：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size();
cout << length;
vector<int> result;
map<int, int> hash_int;
for(int i = 0; i < length; i++){
hash_int[nums[i]] = i;
}
for(int j = 0; j < length; j++){
if(hash_int.count(target - nums[j])>0){
int another = hash_int[target-nums[j]];
cout << another;
if(j==another){
continue;
}
result = {j, another};
break;
}
}
return result;
}
};