数据哈希值的计算和在table中的存储位置

Binguner 发布于2019-08-16 10:32 / 782人阅读

我们知道，Objects中定义了hashcode()函数，用于计算对象的哈希值。并且在很多类中都对hashcode()函数进行了覆盖。但是在HashMap中并没有直接使用各个类的hash值，而是使用hash()函数将它再次进行了计算。
一、列举一些基本类型对应的普通类型的hashcode()
Objects

public static int hashCode(Object o) {
    return o != null ? o.hashCode() : 0;
}

Integer

public int hashCode(){
    return Integer.hashCode(value);
}//就是它自己

String

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for(int i=0; i< value.length; i++){
            h = 31 * h + val[i];//①
        }
        hash = h;
    }
    return h;
}//将字符串转换为字符数组，然后对字符的哈希值进行①处的运算

Character

public static int hashCode(char value) {
    return (int)value;
} //为字符对应的asc11码

Date

public int hashCode() {
    long ht = this.getTime();
    return (int)ht^(int)(ht >> 32);
}

二、在HashMap中有hash()函数对Objects的哈希值再进行了一次计算

1.计算方法

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

重新计算的哈希值是用hashCode()计算出的哈希值和它自己左移16位之后的数进行异或
比如：

h = hashCode()-> 1111 0101 1111 1111 1101 1011 1111 0101
h>>>16        -> 0000 0000 0000 0000 1111 0101 1111 1111
h^(h>>>16)    -> 1111 0101 1111 1111 0010 1110 0000 1010 = hash

2.为什么要这么计算

哈希值是32位的二进制数，我们可以看出，将哈希值右移16位正好是32bit的一半，也就是说它将自己的高16位和低16位做异或，那么当table数组的长度较小的时候，哈希值的高位也能参加数组位置的计算

三、table的阈值
在HashMap是什么一节中我们看到table的阈值并不一定是我们自己设定的容量×加载因子，而是经过了tableSizeFor()函数的计算，那么这个函数又是什么

static final int tableSizeFor(int cap) {
    int n = cap - 1;
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
   return (n<0)?1:(n>=MAXIMUM_CAPACITY)? MAXIMUM_CAPACITY:n+1;  }

首先，我们这样做的目的是为了找出大等于用户给出的哈希表的容量的最小的2的幂，比如用户给了7，那我们就要找到8，用户给了14，我们就要找到16. 那为什么通过这种方式就可以找到呢？让我们来看
假设我们要寻找的数是离14最近的且大于它的2的幂，明显这个数是16，为2的4次方

  16的2进制： 0001 0000
  14的2进制： 0000 1100
  15的2进制： 0000 1111

可以这样想，我们想利用14计算出16，那我们可以先计算出15，再加一，而15有一个特点那就是它有四个1，那现在的问题就成为了如何让14从它的第一位非0数开始将后面的数字全部转换成1.
首先14和15的第一位非0数在同一位上，也就是说我们不用管后面的数，只需要管后面的数。那有什么方法可以让所有的数都转换为1呢，那就是和1进行或运算。
于是我们想到可以利14的第一位(或前几位)非零数与后面的数进行或运算。

Cap == 14;
N = cap-1==13;

-1是为了防止若用户给的数本身就是2的幂，如16，那么将16-1后依旧//可以利用下面的方法计算出想要的结果而不会出错

 n |= n >>> 1;  0000 1100 
                0000 0110
                0000 1110
 n |= n >>> 2;  0000 1110
                0000 0011
                0000 1111
 n |= n >>> 4;  ...
 n |= n >>> 8;  ...
 n |= n >>> 16; ...

从举得例子来看，当n做第一次或运算后，n的前两位都转换为了1，那么现在就可以利用前两位将3,4,位转换为1，所以第二次与运算将n右移了两位；同理，进行了第二次运算后，n的前四位都已经是1了可以用它们去改变5,6,7,8位，后面同理。这就是为什么是以1,2,4,8,16的顺序右移。那为什么到右移16位后就停止了呢？
int在java中是4个子节即32位，而向右移动16位后，可以从高位第一个出现1的位置开始向右连续32位为1，已经超越了int的最大值，所以不用在进行位移操作了
在方法最后将n+1即的到了我们想要的2的幂
四、如何根据哈希值计算出在数组中的位置

 if ((p = tab[i = (n - 1) & hash]) == null)
     tab[i] = newNode(hash, key, value, null);
     //n为数组的大小，为2的指数倍

这是putVal函数中的一小段代码。我们发现，在数组中的位置是用n-1和hash做与运算得到的
3.1为什么是n-1?
由于数组的长度n一定为二的指数倍(tableSizeFor()函数中决定)，所以n-1转换二进制时，后几位全部是1，前面全是0. 如 0000 0000 0000 0000 0000 0000 0000 1111(15)
这样，在与哈希值做与运算时(用上面的例子)

0000 0000 0000 0000 0000 0000 0000 1111
1111 0101 1111 1111 0010 1110 0000 1010
0000 0000 0000 0000 0000 0000 0000 1010

在做与运算时，任何数和0与都会成为0，那么这样就可以保证与运算的结果在0~n-1之间，即数组下标的范围，不会发生数组越界
下一节：hashmap的快速存取

云服务器 GPU服务器 js清空table中的数据 js获取table中的数据 java中的”哈希“ 以数据形式存储在计算机中的信息数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69984.html

hashMap的数据结构

摘要：也就是说，红黑树是一种相对平衡的查找二叉树，这使他不仅便于查找，也便于插入和删除，这对于既需要插入也需要查找的是非常有利的下一节数据哈希值的计算和在中的存储位置 showImg(https://segmentfault.com/img/bVNgfR?w=427&h=361); 在jdk8中，HashMap是用了数组和链表以及红黑树这三种数据结构首先，在hashmap类中，都有一个ta...

null1145 2019-08-16 10:32 评论0 收藏0
JS数据结构与算法_集合&字典

摘要：上一篇数据结构与算法链表写在前面说明数据结构与算法系列文章的代码和示例均可在此找到一集合集合数据结构集合是一种包含不同元素的数据结构。集合中的元素成为成员。上一篇：JS数据结构与算法_链表写在前面说明：JS数据结构与算法系列文章的代码和示例均可在此找到一、集合Set 1.1 集合数据结构集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是：...

sf_wangchong 2019-08-26 13:30 评论0 收藏0
hashMap源码分析以及原理

摘要：举个例子，比如我们要在哈希表中执行插入操作查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。这也是数组长度设计为必须为的次幂的原因。前言 hashMap在平时工作和面试中，常常使用到和问到，本文将从一下几个方面进行记录：　什么是哈希表 HashMap实现原理为何HashMap的数组长度一定是2的次幂？ 1. 什么是哈希表在讨论哈希表之前，我们先...

liuyix 2019-08-16 13:59 评论0 收藏0
Java容器之HashMap倾力详解 - 用得那么多，但你真的懂吗？

摘要：哈希碰撞的概率取决于计算方式和空间容量的大小。超过后执行扩容操作。当一个哈希桶存储的链表长度大于会将链表转换成红黑树，小于时则从红黑树转换成链表。换句话来说，就是为了减少哈希碰撞。红黑树相关的操作虽然代码不同，但是实际上要干的事情是一样的。前言学习情况记录学习情况记录时间：week 3 SMART子目标：Java 容器记录在学习Java容器知识点中，关于HashM...

livem 2019-08-19 10:14 评论0 收藏0