哈希表定义：

哈希表是根据关键码的值而直接进行访问的数据结构。

哈希表一般用来快速判断一个元素是否出现在集合里。

哈西函数：将数据的关键字作为自变量，通过一定的函数关系（哈希函数），计算出的值作为该元素的存储地址。

例：

 通过hashCode将名字转化为数值，利用特定编码方式将其他数据格式转化为不同数值，将名字映射为哈希表上的索引数字。

若学生的数量大于哈希表的数量，则会出现几个学生名字同时映射到哈希表的同一索引下标位置。出现哈希碰撞。

哈西碰撞解决方法：

1）拉链法（链地址法）

数组+链表结构，在一个线性数组里的每一个元素存储一个链表的头结点。

例如： 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，则进行B.next = A，Entry[0] = B。如果又进来C,index也等于0，那么C.next = B，Entry[0] = C。也就是说数组中存储的是最后插入的元素。

2）线性探测法（开发寻址法）

当数组位置1被占用了，就放到位置2上，如果2被占用了，就继续往下找，直到找到空位置。

需保证tableSize大于dataSize。主要依靠哈希表中的空位置解决哈西碰撞。

例：

 哈希结构：

1）数组

若题目限制了数值的大小，可用数组做哈希的题目，但若哈希值比较少、特别分散、跨度很大，使用数组则会造成空间的极大浪费。

2）set（集合）

 set:

按照一定次序有序存储元素，按照内部比较对象所指示的特定排序准则进行排序。

set中只放value，但在底层实际放的是，但在插入元素时，只需插入value即可。

（insert：在set中插入元素x，实际插入的为,若插入成功，返回；若插入失败，返回（说明x在set中已经存在））。

multiset：

按照特定的顺序存储元素，元素可以重复。

与set的区别为multiset中元素可以重复。

（set.count(val)：找到则返回1；

multiset.count(val)：找到则返回multiset中有几个val；

set.erase(val)：找到val后删除；

multiset.erase(val)：找到val后返回有几个并全部删除）。

当要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

3）map（映射）

map：

按照特定的顺序（按照key比较）存储由键值key和值value组合而成的元素。key与value类型不一定相同，在map内部key与value通过成员类型value_type绑定在一起：pair:typedef pair。key是不可以重复的。

（find：找到后返回对应key键位置的迭代器；若未找到返回map：end迭代器） 

multimap：

与map的区别为multimap中元素可以重复。

数组、set、map区别：

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

set是一个集合，里面放的元素只能是一个key。

map为映射，可放key、value两个元素。

242.有效的字母异位词

给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。

首先定义一个数组记录字符串s里字符出现的次数。将s[i]-'a'所在的元素做+1操作即可得到s中字符出现的次数。

接着在遍历字符串t时，对t中出现的字符映射哈希表索引上的数值做-1的操作。

若最后数组中所有元素为0，则为异位词，否则不是。