这一篇主要讲困惑了自己很久的静态哈希和动态哈希的区别！！！！！！！
文中哈希函数计算出来的结果称为地址，也就是$hash(key)$
静态哈希和动态哈希的区别
这里直接给出答案，静态哈希和动态哈希区别并不是容量大小可不可以动态大小的调整，这个只是它们区别带来的结果，不能算根本意义上的区别。根本上的区别是静态哈希的哈希函数所计算出来的索引值永远是在固定的区间内。这就导致静态哈希的扩展的同时，需要对哈希函数进行变化，因为当你区间扩大的时候，你需要改变哈希函数使得它计算出来的索引$key$值对应扩大的区间。而动态哈希的哈希函数会计算出key很大，但是会根据需要取一部分前缀或者后缀来使用。
静态哈希
对于静态哈希，同样的$key$永远映射出唯一的地址(这个得根据动态哈希来理解，静态$hash$函数计算处理的地址是一样的,但是动态哈希计算出来的地址很大，取不同的位数，对应的地址也不一样)，这就出现了一个问题，当出现哈希碰撞，$bucket$就会溢出，静态哈希采用以下两种方式解决。
1.链表:将拥有相同地址的值以链表的形式串联起来。
2.线性探测(开放地址法):如果计算出来的地址有冲突，那么就存到bucket里下一个空白的位置
扩容操作一般是将bucket扩充一倍，静态哈希的特征决定了对空间的管理比较繁琐。
动态哈希
这里介绍两个比较主流的动态哈希，一个是线性哈希，一个是可扩展哈希。其中可扩展哈希需要更着重的理解。
线性哈希
线性哈希的哈希表结构由分裂点，桶编号，桶内存储key，溢出key组成。
假设我们的$hash$函数是$key$ $mod$ $4$，每个桶最多存储5个key，其中4称为散列系数。初始化如下
主要来看扩展操作，现在插如27，计算出来的地址为3，但是3已经满了，需要进行分裂操作。
- 寻找分裂点，此时对0桶进行分裂
- 添加桶，增加分裂桶的散列系数，这里对应将0号桶的哈希函数$key$ $mod$ $4$改为$key$ $mod$ $8$
- 分裂点下移
(这里有个好奇的点)
这时候已经有两个hash函数了，假设h0=key mod 4，h1=key mod 8。那么我们这时候如果要插入一个新的数，用哪一个函数呢，这个时候用h0。
依次类推，现在分裂1号桶，1号桶的散列系数变为$key$ $mod$ $8$，之后分裂2号桶，接着即使3号桶，最后的结果就是
(这里继续扩展好奇的点)
这里的话是进行到第四个桶(编号3)的分裂再回到0，下一次就是第8个桶了(编号7)。这个时候散列系数全为8，这时候注意了h0=key mod 8，h1=key mod 12，下一次分裂的话，散列系数就开始要变为12了
总结一下就是分裂的时候进行计算使用h1，而插入的话使用h0
可扩展哈希
可扩展哈希由目录和桶这两大部分组成。有下面这几个参数。
- 桶的大小，图中是4
- 本地深度($local$ $depth$)，索引这个桶最少需要几个位。
- 全局深度($global$ $depth$)，目录的位数。
注意：只有本地深度等于全局深度的桶进行分裂的时候，才需要进行目录扩展操作，扩展之后，分裂的桶和分裂之后的桶的本地深度都+1.
