數據哈希值的計算和在table中的存儲位置

Binguner 發布于2019-08-16 10:32 / 983人閱讀

我們知道，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中的”哈希“ 以數據形式存儲在計算機中的信息數據

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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