哈希冲突怎么解决
下面假设hash=(x) -> x/2，hash表的长度为10，x可取5，6等，此时hash(5)=hash(6)=3，产生冲突
开放定址法
开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
也被称为再散列法，当出现hash冲突的时候，会将上一次hash的结果和增量序列相加，然后对hash表的长度取模，进行再散列；如当3=hash(5) =hash(6)时，此时hash(6)就需要利用开放定址法解决冲突：hash(6)=(3+d)%length = p1 (d为增量序列)
其中，增量序列的获取方式有三种：
- 线性探测再散列：当发生冲突的时候，顺序查看，直到能够找到空位；d = 1/2/3..../length-1
- 二次探测再散列：当发生冲突时，d正负跳跃，比较灵活；d = 1/-1/2/-2/...../(length-1)/2
- 伪随机探测再散列：d取伪随机数
此时，对于hash(5)和hash(6)的冲突来说，拿线性探测再散列举例：hash(6)=(3+1)%10=4
链地址法
将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
HashMap采用该方法，当出现hash冲突的时候，会使同一个hash的所有值形成一个链表。查询的时候，首先通过hash定位到该链表，然后再遍历链表获得结果。
此时，对于hash(5)和hash(6)的冲突来说，则会在hash表的第三个节点形成链表，如：hash[3]->5->6
优点：
- 处理冲突简单
- 适合经常插入和删除的情况下
- 适合没有预定空间的情况
缺点：
- 当冲突较多的时候，查询复杂度趋近于O(n)
再哈希法
当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。
当发生冲突时，需要更换hash函数，如当hash(5)=hash(6)，此时hash(6)就需要切换成hashNew(6)才行，直到新的hash函数没有冲突
建立公共溢出区
将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。