Hash函数

什么是Hash

散列算法，也称哈希算法。实际中的Hash函数是指将一个大范围映射到小范围。把大范围映射到一个小范围的目的往往是节省空间，使得数据容易保存。除此之外，Hash函数往往应用于加密与查找。

哈希表是一种以键-值（key-indexed）存储的数据结构，通过输入待查找的值，获取到对应的值。

HashMap中的hash算法

算法回顾

1. <<:左移运算符 num << n 丢弃最高位，0补最低位

   在数字没有溢出的前提下，无论正数和负数，左移n位，相当于num乘以2的n次方

   2.>>:右移运算符 num >> n 符号位不变，左边补上符号位

   在数字没有溢出的前提下右移n位，相当于num除以2的n次方，取商

   3.>>>: 无符号右移，忽略符号位，空位都以0补齐

2. %:模运算 取余

3. ^:位异或 第一个操作数的第n位与第二个操作数的第n位相反，那么结果的第n位也为1，否则为0

4. &:与运算 第一个操作数的第n位与第二个操作数的第n位如果都为1，那么结果的第n位也为1，否则为0

5. |:或运算 第一个操作数的第n位与第二个操作数的第n位只要有一个为1，那么结果的第n位也为1，否则为0

6. ~:非运算 操作数的第n位为1，那么结果的第n位为0

前提：HashMap中定义到桶的位置是根据key的hash值与数组的长度取模来计算的。
取模：hash%length=hashCode & （length - 1）

jdk1.8中的hash方法

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

取key的hashCode算法，然后对16进行异或运算和右移运算。
key.hashCode()) ^ (h >>> 16)扰动函数减少了hash冲突的几率。