Java高级面试之哈希表 哈希表java实现

哈希在java里用的非常多，可能你不经意之间就使用了它。比如我们经常使用的hashset,hashmap。哈希是一种数据结构，它提供了快速插入和查找，基于数组来实现的。

哈希化

哈希化将字母转换为ascii码或者其他编码，然后使用幂的连乘，比如abc，那么幂连乘则为97*27*27+98*27+27，由于乘出来的结果可能很大比如范围在1-9999999，因此需要进行压缩（取余），压缩到比如1-100之间。

压缩后的冲突问题

压缩后，可能出现冲突的问题。即2个不同的数，经过上述计算取余后，得到了相同的结果。如果不进行特别处理，就会使第二个计算值会将第一个值覆盖。

解决冲突问题

解决这个冲突问题，业界有2种方案。

方案一：开放地址法

如下图，一旦发现a和b算出的hash值冲突，那么在数组里找空位置，将数据填入，而不再使用哈希函数得到的数组下标。

方案二：链地址法

一旦发现两个数据计算的hash值一样，则会添加到对应的链表

以上就是哈希的一些原理性的知识。