1、哈希表解决什么问题？

　　假设有一组记录，每条记录都是学生名，成绩的键值对，在一般的线性表中，每条记录的存放是没有规律的。如果要找Andy的成绩，因为不知道Andy这条记录的存放位置，必须遍历集合，逐个比较，找到Andy这条记录，取出成绩。时间复杂度为O(N)，效率很低。哈希表就是解决这个问题的。

2、如何解决的？

　　上面问题的关键是，根据学生名不能确定存放位置，哈希表是这样做的：设计一个映射函数，把学生名映射到存放的地址。这样就行了，给我一个学生名，我只要根据映射函数计算一下，就知道了存放位置，直接去那个地方去数据，时间复杂度为O(1)。同样当插入记录的时候，根据映射函数计算一下，这条记录应该放在哪个位置，把记录放在那个地方就好了。

3、哈希表中存放的是key-value对。使用映射函数，把key映射一个存放地址（注意：这里的地址可认为是Hash地址，不是真实的物理地址）。对于映射函数，需要注意：a、计算要简单，复杂计算会影响效率。b、散列地址分布均匀，不然会频繁地照成冲突。

4、映射函数引入一个问题，那就是不同的key可能会映射到相同的位置，插入元素的时候，就冲突了。解决冲突的办法有：

　　a、开放定址法：冲突了。就去寻找下一个空的地址。

　　b、再次哈希：再次映射找到一个空的地址。

　　c、链地址法：每个地址可以存放一系列元素，冲突了，就在当前元素后面加。

　　d、公共溢出区法：冲突了，放到公共区内。

　　查找元素的时候，先映射地址，如果地址存放的不是目标元素，说明冲突了，根据解决冲突的算法，继续找。

5、哈希表为了解决查找的效率，把key映射为存放地址，因此可以直接定位。