解决哈希冲突的常用方法有哪些？

开放定址法

基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈 希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不 冲突的哈希地址pi ，将相应元素存入其中。

再哈希法

这种方法是同时构造多个不同的哈希函数：Hi=RH1（key） i=1，2，…，k 当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

拉链法的优点:

拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

拉链法的缺点：

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

看图就可以知道Java中的hashMap使用了拉链法处理冲突。 HashMap有一个初始容量大小，默认是16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 为了减少冲突的概率，当hashMap的数组长度到了一个临界值就会触发扩容，把所有元素rehash再放到扩容后的容器中，这是一个非常耗时的操作。

而这个临界值由【加载因子】和当前容器的容量大小来确定：DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR ，即默认情况下是16x0.75=12时，就会触发扩容操作。

所以使用hash容器时尽量预估自己的数据量来设置初始值。具体代码实现自行去研究HashMap的源码。

基础知识补充完毕，回到正题，为什么加载因子要默认是0.75？

使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素个数和概率的对照表。从上面的表中可以看到当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。