Question

HashMap发生hash冲突怎么办？

HashMap发生hash冲突怎么办

Answer 1

排解hash冲突的方法有很多，大致可以划分为两类：封闭定址法和开放定址法。
封闭定址法：

多槽位 multiple slots：桶单元细分成若干槽位slot，存放冲突的词条；（无法根本解决问题）
独立链法 linked-list chaining：每个桶存放一个指针，冲突的词条组织成列表（效率太低）
公共溢出区 overflow area：单独开辟一块连续空间，发生冲突的词条顺序存入此区域（可能导致冲突次数激增）
开放定址法：每个桶都事先约定若干备用桶，构成一个查找链。
线性试探：一旦冲突，则试探后一紧邻桶单元，直到命中或抵达空桶。
平方试探：以平方数为距离，确定下一个试探的桶单元。

双平方试探：
再散列 double hashing：即用第二个散列函数确定偏移。