Hash算法

实现机制

1.hash最常见的实现方法是拉链法：

• hash表是通过数组+链表的方式实现的
• 每一个hash表通过一个含有若干个元素的数组组成，每个元素中储存一个的是一个链表的首节点。通过key%length得到，也就是通过元素的hash值除以数组的长度得到。

2.hashmap中有一个静态内部类叫entry

• 我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。；
• 这个类中一共有四个元素 KEY，Value，Entry类型的next，int类型的hash；
• 存在几个方法一个是equals，这个方法是实现比较两个键值对是否相同的（先比较key，之后再比较value），
• 存在一个方法叫hashcode用于返回这个键值对对应的唯一的hashcode，（hashcode是用于简化存储，优化空间利用率的，即使不用hash算法，也能够得出正确结果）
• 还有其他的比如addEntry，tostring等方法

3.hashcode的实现机制

hashcode源代码

*其实hashcode这个代码是源自object类中的，Java早就把hashcode的实现方法放到了公共基础类object中，所以所有的类都有自己的hashcode

• hashcode通过位运算进行实现：