【你问我答】HashMap如何解决哈希冲突？

        HashMap是一个散列桶（数组和链表），它存储的内容是键值对key-value映射         HashMap采用了数组和链表的数据结构，能在查询和修改方面继承了数组的线性查询和链表的寻址修改         HashMap是非synchronized的，线程不安全，所以很快         HashMap可以接受null键和值，而HashTable不行（因为equals()方法需要对象，因为HashMap是后出的api经过处理才可以） · HashMap的工作原理是什么？         然后讲下HashMap中的实现原理，hashmap是由数组和链表组成的。数组是HashMap的本体，而链表则是为了解决hash冲突而存在的，如果定位到数组位置不存在链表（当前Entry的next指向为null），那么对于查找插入等操作很快，仅仅需要一次寻址即可；如果定位到数组有链表，对于添加操作其时间复杂度为O（n）,首先遍历链表，存在既覆盖，否则新增。对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。 · 减少hash冲突？扰动函数可以减少碰撞         原理是如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些。这就意味着存链表结构减小，这样取值的话就不会频繁调用 equal 方法，从而提高 HashMap 的性能（扰动即 Hash 方法内部的算法实现，目的是让不同对象返回不同hashcode）。         使用不可变的、声明作 final 对象，并且采用合适的 equals() 和 hashCode() 方法，将会减少碰撞的发生不可变性使得能够缓存不同键的 hashcode，这将提高整个获取对象的速度，使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。

0、HashMap工作原理      太复杂的原理我也不是很懂，简单地说就是HashMap是通过一个 哈希算法 将要放入的key的hashcode值进行散列(通过一系列的位操作尽量将不同值在一定区域内分散在不同的位置)，然后再计算出该散列值在hashmap容器中的位置将该元素放到该位置上(具体定位可以看HashMap中putVal()方法第二个iif)。      这时需要记住一个定理: 两个值对象值相同，那么它们的哈希值一定相同。两个对象哈希值相同，它们的值不一定相同。 1、为什么会引起哈希冲突      由于我们不能一开始就设置很大的map内存造成浪费，所以hashmap容量有限的扩容不及时情况下就会出现hash冲突(默认是16，负载因子是0.75，负载因子均衡map消耗时间空间的值，减轻因为容量过少造成的哈希冲突参考resize())，但是频繁扩容是对性能有影响的，所以寻找一个适合当前内容情况的负载因子很有必要，当然默认的0.75基本都是可以的。      如果我们容量较小，元素很多负载因子很大就会造成很多散列值后再进行定位后的地址相同从而造成一个位置有多个散列值的索引这就是哈希冲突。 2、哈希冲突的解决办法      开放定址法、拉链法、再哈希法 3、HashMap解决哈希冲突方法      HashMap使用的是拉链法解决Hash冲突。      当插入元素时当前位置没有元素则直接插入即可      当插入元素时当前位置有元素时则遍历以该节点元素为头节点的链表有该key就更新value没有就添加到链表尾部(1.7的方法，1.8转为链表+红黑树提高查询效率(查看putTreeVal()方法)）       拉链法就是形象的称呼在1.7上很贴切。就是在该位置上以链表形式进行哈希冲突相同的key的堆叠(不知道我总能想起来衣服的拉链哈哈)，但是定址后的遍历会是耗时的原因

1.开放定址法： 其中 m 为表的长度 对增量di有三种取法： 线性探测再散列 di = 1 , 2 , 3 , … , m-1 平方探测再散列 di = 1 2 , -2 , 4 , -4 , 8 , -8 , … , k的平方 , -k平方 随机探测再散列 di 是一组伪随机数列 2.链地址法： 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。 3.再哈希法： 这种方法是同时构造多个不同的哈希函数： Hi=RH1（key） i=1，2，…，k 当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。 4.建立公共溢出区法： 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

哈希冲突：当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2),这种现象称为hash冲突。 开放定址法：一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。 再哈希法：当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。 链地址法：将所有关键字为同义词的记录存储在同一线性链表中。 建立一个公共溢出区：假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。