Hash函数

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冲突的几率。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容