今天在学习hash值的时候，突然发现了这个现象：//29448764但是这个key的hash值和调用是一样的System.out.println("Key".hashCode());//1179395System.out.println("call".hashCode());//1179395这种情况是hash冲突造成的。为了理解这一点，让我们谈谈哈希冲突以及如何解决哈希冲突。冲突：哈希表实际上是一个存储哈希值的数组。哈希值是通过哈希函数计算的。那么哈希冲突就是两个不同的值。哈希函数计算出的哈希值相同，这样他们存入数组的时候就会发生碰撞，这就是哈希碰撞。如何解决散列冲突：解决散列冲突的方法一般有四种：1.打开地址法这种方法也叫重新散列法。)当发生冲突时，根据p，生成另一个哈希地址p1，如果p1仍然冲突，则根据p，生成另一个哈希地址p2，...直到找到一个不冲突的哈希地址pi，存储对应的元素在里面。也就是说，当发生冲突时，寻找下一个空地址，并将数据存入其中。只要哈希表足够大，这样的空地址总能找到。Hi=(H(key)+di)%mi=1,2,...,n其中H(key)为哈希函数，m为表长，di称为增量序列。增量序列的值不同，对应的re-hashing方法也不同。主要有以下三种：线性检测然后哈希dii=1,2,3,...,m-1这种方法的特点是：当发生冲突时，依次检查表中的下一个单元，直到一个空单元或检查整个表。二次检测再哈希di=12,-12,22,-22,...,k2,-k2(k<=m/2)这种方法的特点是：当发生冲突时，跳转左右表检测更灵活。伪随机探测重新哈希di=伪随机数序列。具体实现时，需要建立一个伪随机数生成器（如i=(i+p)%m），并给出一个随机数作为起点。例如，已知哈希表长度m=11，哈希函数为：H(key)=key%11，则H(47)=3，H(26)=4，H(60)=5，假设Akeyword为69，则H(69)=3，与47冲突。如果使用线性检测，然后hash处理冲突，则下一个hash地址为H1=(3+1)%11=4，如果有还是冲突，那么下一个hash地址为H2=(3+2)%11=5，还是冲突，继续找下一个hash地址为H3=(3+3)%11=6，没有冲突此时，将69填入单元5。如果通过二次检测和哈希处理碰撞，则下一个哈希地址为H1=(3+12)%11=4，如果仍然存在冲突，则下一个哈希地址为H2=(3-12)%11=2。此时没有冲突，将69填入单元2。如果使用伪随机检测和哈希处理冲突，则伪随机数序列为:2,5,9,.....，下一个hash地址为H1=(3+2)%11=5，还是有冲突，再求下一个hash地址为H2=(3+5）%11=8，此时不会再有冲突，将69填入单元8。2）Rehashing这种方法是同时构造多个不同的哈希函数：Hi=RH1(key)i=1,2,...,k当hash地址Hi=RH1(key)发生冲突时，再计算Hi=RH2(key)...直到冲突不再发生。这种方法不太容易聚类，但会增加计算时间。3）链地址法该方法的基本思想是将散列地址为i的所有元素组成一个称为同义词链的单向链表，将单向链表的头指针存放在第i个单元中哈希表，因此查找、插入和删除主要在同义词链中完成。链地址法适用于频繁的插入和删除。4）这种建立普通溢出区的方法的基本思路是：将哈希表分为两部分，基本表和溢出表，所有与基本表冲突的元素都会填充到溢出表中.优缺点开放哈希表（openhashing）/拉链法（针对桶链结构）1）优点：①对于记录总数频繁变化的情况，可以更好的处理（即避免了动态的开销adjustment)②因为record存储在节点中，而且节点是动态分配的，不会造成内存浪费，所以特别适合record本身size大的情况，因为指针的开销可以此时被忽略。③删除记录时，更方便，直接通过指针操作即可2）缺点：①存储的记录在内存中是随机分布的，所以在查询记录时，相对于紧凑型数据类型（如数组），哈希表的跳转访问它会带来额外的时间开销②如果所有的键值对都可以提前预测到以后不会改变（即不允许插入和删除），则可以人为地创建一个不会引起冲突的完美哈希函数（perfecthashfunction），此时closedhashing的性能会比openhashing高很多③因为使用了指针，record不容易进行序列化（serialize）操作。封闭散列（closedhashing）/开放寻址法1）优点：①记录更容易序列化（serialize）操作②如果可以预测记录的总数，可以创建一个完美的散列函数。这时候处理数据的效率很高2）缺点：①存储的记录条数不能超过桶数组的长度，如果超过就需要扩容，扩容会造成一次的时间成本操作飙升，这可能是实时或交互式应用程序中的严重缺陷。②使用检测序列，计算时间成本可能过高，导致希腊表的处理性能降低。③由于记录存储在bucket数组中，而bucket数组必然有空槽，所以当记录本身的大小很大，记录总数也很大时，空槽占用的空间会造成明显的浪费④删除记录时比较麻烦。比如记录a需要删除。b记录在a之后插入到bucket数组中，但是和a冲突。它是通过检测序列再次跳转找到的地址。所以，如果直接删除a，a的位置就变成了一个空槽，而空槽是查询记录失败的终止条件，会导致记录b不可见，直到数据重新插入到a的位置，所以a不能直接删除，但是设置了删除标记。这需要额外的空间和操作。
