散列(hash)
散列或者说哈希，通过学习我知道：
是一种将元素通过散列函数H（）转化为整数，使得整数可以尽量唯一地代表这个元素
那么可以用key代表元素未转化，使用H(key)代表转化后的整数
散列函数
- 直接定址法
恒等变换或是线性变换，即直接使用key作为数组下标，H（key）= a*key+b； - 平方取中法
使用KEY^2的中间若干位来作为hash值，H（key）= key^2的中间几位； - 除留余数法
把key除以一个数mod所得到的余数作为hash值，H（key）= key % mod ；
冲突
我们发现有时候函数并不能代表一个值，通过除留余数法我们可能出现两个不同的key同时取余出相同的哈希值H（key），这时候就产生了冲突。
解决冲突的方法
- 线性探查法（Linear Probing）
当出现冲突时，就检查下一个位置哈希值H（key）+1的位置是否被占用，没有就使用；如果仍然被占用就继续往下查找直到表最大，超过表长返回表的首位继续查找，如此循环；不过此方法效率低下，容易出现连续的被占用情况。 - 平方探查法（Quadratic Probing）
为了避免反复查找位置，可以使用平方顺序进行查找，检查下一个位置H（key）+1^2，H（key）-1^2，H（key）+2^2，H（key）-2^2，H(key)+3^2,H(key+3^2……；当H（key）+k^2大于表长，则使用H（key）+k^2 %表长，H（key）-k^2小于0，则使用（（H(key)-k^2）%表长+表长）%表长，得到一个非负数的哈希值； - 链地址法（拉链法）
将所有hash值相同的key连接成一个单链表，其中的List[h]存放H（key）= h的一条单链表，当冲突发生时就遍历链表来寻找所有H（key） = h的key；
字符串hash
前面的方法都是基于key为整数，那么当想使用一个hash尽可能代表一个字符串就需要其他的方法。
可以浅显的理解字符串是数字、字母、特殊字符组成的，那么字符串随机组合分为七种。
