一、哈希表的概念
1.1 哈希表的定义
哈希表建立了一种 关键字 和 存储地址 之间的 直接映射 关系，使每个关键字与结构中的 唯⼀存储位置相对应 。希表是⼀种存储和查找非常快的结构。
举个例子：
1.2 哈希函数
将 关键字 映射 成对应的地址的函数就是哈希函数 ，也叫作散列函数，记为 Hash(key) = Addr哈希函数的本质也是⼀个函数，它的作用是，你给它⼀个关键字，它给你一个该关键字对应的存储位置。
1.3 哈希冲突
哈希函数可能会把两个或两个以上的不同关键字映射到同一地址 ，这种情况称为哈希冲突，也称散列冲突。起冲突的不同关键字，称它们为同义词。
这里是 %7 出现了冲突， 那为什么不 %8 , %10 ？
二、常见的哈希函数
2.1 直接定址法
案例中，统计字符串中，小写字符出现的次数使用的方法，就是直接定址法
直接取关键字的某个线性函数值为散列地址 ，散列函数是 hash(key) = key 或 hash(key）= a× key + b 其中 a 与 b 为常数。这种方式计算比较简单，适合关键字的分布基本连续的情况，但是若关键字分布不连续，空位较多，则会造成存储空间的浪费。
2.2 除留余数法
哈希冲突那里的案例，所用的哈希函数就是除留余数法。M 一般取质数（素数）
2.3 其他方法
上面的两种方法是《算法导论》书籍中讲解的方法，除此之外还有乘法散列法和全域散列法。
《殷人昆 数据结构：用面向对象方法与C++语言描述 （第⼆版）》和 《[数据结构(C语言版)].严蔚敏_ 吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数学分析法等，这些方法相对更适用于⼀些局限的特定场景，有兴趣可以去看看这些书籍。
三、处理哈希函数
有时候哈希表无论选择什么哈希函数都无法避免冲突 ，那么插入数据时，如何解决冲突呢？主要有两种方法，线性探测法 和 链地址法
3.1 线性探测法
线性探测是有弊端的 ， 如果数据过于密集的话 ，则需要探测多次 ， 例如在上面的数组的加个 8 ，那么需要探测多次才能找到存储地址。
那么在创建数组的时候 ， 一般会创造 数组元素个数的两倍 的空间个数 ， 为的是避免数据过于密集 ， 但是依旧会存在一些弊端~
3.2 链地址法
这个也有一点弊端 ， 如果所有的数据都冲突在 8 这个位置上 ， 怎么办？
---> 把冲突的数据 ， 构造成一个红黑树 ， 挂在冲突地址上 ， 此时查找的时间复杂度会变成logN级别的
