哈希取模java,哈希取模分表

本文目錄一覽：

• 1、java 1.哈希算法的實現：
• 2、java哈希值
• 3、java里的取模
• 4、java取模運算
• 5、Hash衝突的解決方法

java 1.哈希算法的實現：

public class Test { /*創建類*/

public static void main(String[] args) {

System.out.println(dg(100));

}

static int dg(int i) { /*定義變量 */

int sum;

if (i == 1) /*假設條件*/

return 1;

else

sum = i + dg(i – 1); /*1~100的和的表達式*/

return sum; /*返回結果*/

}

}

這個腳本語言為 Internet 應用而生，它可以看作是 Haskell 和 Java 的結合。

java哈希值

兩個內容相同的對象具有相同的hashcode；反之不成立。

HashMap對象是根據其Key的hashCode來獲取對應的Value。

map的實現是數組結合鏈表。hashcode決定存放位置，兩個對象位置一樣時比較equals方法。true的話覆蓋（同一個對象），false的添加（不是同一個對象）。

java里的取模

%是取模運算，結果是餘數，和/(除)可以對比。java中int做除運算會把小數部分直接去掉。

7/5=1 （餘2） 7%5=2

12345/10=1234 （餘5） 12345%10=5

java取模運算

如圖，結果分別是1,1，-1,-1

按照我的理解，a%b的結果c就是在（-|b|,|b|）內的a+kb值，k是整數,c的正負取決於a的正負

Hash衝突的解決方法

哈希非哈希區別在於關鍵字在表中位置和它之間是否存在一個確定關係，哈希存在，非哈希不存在。

hash就是散列，就是把任意長度的輸入，通過散列算法，變成固定長度的輸出，輸出就是散列值，該轉換是壓縮轉換，散列值空間遠小於輸入的空間，不同的輸入可能會散列成相同的輸出。

Hash衝突，也就是經過一個函數結果作為地址去存放當前key value鍵值對(這個是hashmap存值方式)。

解決hash衝突發方法有

1）開放定址法，m為表長度，增量di有三種取法，線性探測再散列，平方探測再散列。

2）鏈地址法，就是key值取模再運算，java的HashMap就是這麼實現的，在put()方法裡面。

3）重哈希法，在創建hashmap的時候一般默認初始化容量，創建的hash表是桶的數量，負載因子：map的size/初始化容量，當hash表中負載因子達到負載極限，hash表會自動成倍增加容量，並將原有的對象重新分配加入新的值，成為rehash，rehash非常影響性能，所以初始化容量要設置好，不能太過浪費空間，也不能過小造成rehash情況經常出現。

4）建立一個公共溢出區域，就是把衝突的都放在另一個地方，不在表裡面。

先看HashMap的數據結構，HashMap的底層主要是基於數組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它通過計算散列碼來決定存儲的位置，HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，出來的hash值一樣，不同對象出來的hash值一樣，出現所謂hash衝突，HashMap底層通過鏈表解決hash衝突的。

HashMap其實就是一個Entry數組（類似pair），Entry對象中包含了鏈和值，其中next也是一個Entry對象，它就是用來處理hash衝突的，形成一個鏈表。

在Java8之前，如果發生hash衝突往往是將該value直接鏈接到該位置的其他所有value的頭部，即相互衝突的所有value形成一個鏈表，因此，最壞情況HashMap的查找時間複雜度退化到O(n)，在Java8中做了改進，一個是改頭插法為尾插法，還有一個是當一個位置衝突過多時（大於等於8），存儲的value將形成一排序二叉樹，排序的依據為key的hashCode，這樣在最壞情況下，性能也只退化到O(logn)。

這樣的改進意義重大，一是從O(n)提升到O(logn)的時間開銷（最壞情況），二是如果惡意程序知道我們利用的Hash算法，在純鏈表情況下，發送大量請求導致hash碰撞，不停訪問這些key使HashMap忙於查找，最終癱瘓。