java的hash演算法

Ⅰ java 為什麼使用hashmap

首先當我們需要存儲數據的時候，動態數組雖然能夠自動擴容，但是必須在初始時刻指定初始容量。而對於那些在編譯時無法確定具體的數量即動態增長的數據，就需要用到Java集合類了。對於ArrayList 和 LinkedList，還有 Vector它們都有一些缺點，要麼插入刪除速度慢、要麼就是遍歷速度慢。那麼有沒有一種插入、刪除、遍歷都比較不錯的集合類呢？於是 HashMap 就出現了。HashMap 是一個散列表，它存儲的是一組鍵值對(key-value)的集合，並實現快速的查找。

（1）為了實現快速查找，HashMap 選擇了數組而不是鏈表。以利用數組的索引實現 O(1) 復雜度的查找效率。

（2）為了利用索引查找，HashMap 引入 Hash 演算法, 將 key 映射成數組下標: key -> Index。

（3）引入 Hash 演算法又導致了 Hash 沖突。為了解決 Hash 沖突，HashMap 採用鏈地址法，在沖突位置轉為使用鏈表存儲。

（4）鏈表存儲過多的節點又導致了在鏈表上節點的查找性能的惡化。為了優化查找性能，HashMap 在鏈表長度超過 8 之後轉而將鏈表轉變成紅黑樹，以將 O(n) 復雜度的查找效率提升至 O(log n)。

【綜上】

HashMap 存在的意義就是實現一種快速的查找並且插入、刪除性能都不錯的一種 K/V（key/value）數據結構。

附上一位博主的高見：網頁鏈接

Ⅱ java的hashCode方法的使用 希望詳細解釋!!!

java的hashCode方法
首先，想要明白hashCode的作用，你必須要先知道Java中的集合。總的來說，Java中的集合（Collection）有兩類，一類是List，再有一類是Set。你知道它們的區別嗎？前者集合內的元素是有序的，元素可以重復；後者元素無序，但元素不可重復。那麼這里就有一個比較嚴重的問題了：要想保證元素不重復，可兩個元素是否重復應該依據什麼來判斷呢？這就是Object.equals方法了。但是，如果每增加一個元素就檢查一次，那麼當元素很多時，後添加到集合中的元素比較的次數就非常多了。也就是說，如果集合中現在已經有1000個元素，那麼第1001個元素加入集合時，它就要調用1000次equals方法。這顯然會大大降低效率。 於是，Java採用了哈希表的原理。哈希演算法也稱為散列演算法，是將數據依特定演算法直接指定到一個地址上。如果詳細講解哈希演算法，那需要更多的文章篇幅，我在這里就不介紹了。初學者可以這樣理解，hashCode方法實際上返回的就是對象存儲的物理地址（實際上並不是真正的在內存的物理地址，不過可以這樣理解）。 這樣一來，當集合要添加新的元素時，先調用這個元素的hashCode方法，就一下子能定位到它應該放置的物理位置上。如果這個位置上沒有元素，它就可以直接存儲在這個位置上，不用再進行任何比較了；如果這個位置上已經有元素了，就調用它的equals方法與新元素進行比較，相同的話就不存了，不相同就散列其它的地址。所以這里存在一個沖突解決的問題。這樣一來實際調用equals方法的次數就大大降低了，幾乎只需要一兩次。 所以，
Java對於eqauls方法和hashCode方法是這樣規定的：

1、如果兩個對象相同，那麼它們的hashCode值一定要相同；

2、如果兩個對象的hashCode相同，它們並不一定相同 上面說的對象相同指的是用eqauls方法比較。 你當然可以不按要求去做了，但你會發現，相同的對象可以出現在Set集合中。同時，增加新元素的效率會大大下降。

如果你改寫了equal()方法，令兩個實際不是一個對象的兩個實例在邏輯上相等了，但是hashcode卻是不等。

所以要記得改寫hashcode。

不改寫會帶來什麼後果呢？當然，比如你在用hashmap,hashtable之類的設計hashcode的類的時候，就會出麻煩了。

至於如何改寫一個hashcode，這就有好有壞了，看各人的功底了。現在還有專門的人在研究優秀的hash演算法。

也就是說 List 是一個有序的、可重復的對象容器介面，Set是一個無序的、不可重復的對象容器介面 。後面都講了 Set 是如何實現不重復的 ：為了避免多次重復的使用 equal 方法帶來的系統負擔 ，set 首先調用hashCode 方法來檢測 是否被佔用 如果被佔用 然後調用 equal 方法判斷被佔用的是否相同

Ⅲ JAVA中哈希碼具體是什麼

哈希其實只是一個概念，沒有什麼真實的指向。它的目的是保證數據均勻的分布到一定的范圍內。所以不同數據產生相同的哈希碼是完全可以的。
java中哈希一般是希望自己寫演算法的。隨便返回什麼都可以。如果什麼也不寫的話就會返回地址。如果自己寫，最簡單的做法是把所有欄位拼起一個長串做個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中hash是什麼意思

hash就是哈希（函數），你們老師應該說學過數據結構就應該知道，而不是c語言

Ⅵ 如何正確實現Java中的hashCode方法

正確實現Java中的hashCode方法：
相等和哈希碼

相等是從一般的方面來講，哈希碼更加具有技術性。如果我們在理解方面存在困難,我們可以說,他們通過只是一個實現細節來提高了性能。
大多數的數據結構通過equals方法來判斷他們是否包含一個元素，例如：
List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

這個變數contains結果是true，因為,雖然」b」是不相同的實例(此外,忽略字元串駐留),但是他們是相等的。
通過比較實例的每個元素，然後將比較結果賦值給contains是比較浪費的，雖然整個類的數據結構進行了優化，能夠提升性能。
他們通過使用一種快捷的方式(減少潛在的實例相等)進行比較，從而代替通過比較實例所包含的每個元素。而快捷比較僅需要比較下面這些方面：
快捷方式比較即通過比較哈希值，它可以將一個實例用一個整數值來代替。哈希碼相同的實例不一定相等，但相等的實例一定具有有相同的哈希值。(或應該有,我們很快就會討論這個)這些數據結構經常通過這種這種技術來命名,可以通過Hash來識別他們的,其中，HashMap是其中最著名的代表。
它們通常是這樣這樣運作的
當添加一個元素,它的哈希碼是用來計算內部數組的索引(即所謂的桶)
如果是,不相等的元素有相同的哈希碼,他們最終在同一個桶上並且捆綁在一起,例如通過添加到列表。
當一個實例來進行contains操作時，它的哈希碼將用來計算桶值(索引值)，只有當對應索引值上存在元素時，才會對實例進行比較。
因此equals，hashCode是定義在Object類中。
散列法的思想
如果hashCode作為快捷方式來確定相等，那麼只有一件事我們應該關心:相等的對象應該具有相同的哈希碼，這也是為什麼如果我們重寫了equals方法後，我們必須創建一個與之匹配的hashCode實現的原因!
否則相等的對象是可能不會有相同的哈希碼的,因為它們將調用的是Object's的默認實現。
HashCode 准則
引用自官方文檔
hashCode通用約定:
* 調用運行Java應用程序中的同一對象,hashCode方法必須始終返回相同的整數。這個整數不需要在不同的Java應用程序中保持一致。
* 根據equals(Object)的方法來比較，如果兩個對象是相等的,兩個對象調用hashCode方法必須產生相同的結果。
* 根據equals(Object)的方法是比較，如果兩個對象是不相等的，那麼兩個對象調用hashCode方法並不一定產生不同的整數的結果。但是,程序員應該意識到給不相等的對象產生不同的整數結果將有可能提高哈希表的性能。
第一點反映出了相等的一致性屬性，第二個就是我們上面提出的要求。第三個闡述了一個重要的細節，我們將在稍後討論。
HashCode實現
下面是非常簡單的Person.hashCode的實現
@Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}

person』s是通過多個欄位結合來計算哈希碼的。都是通過Object的hash函數來計算。
選擇欄位
但哪些欄位是相關的嗎?需求將會幫助我們回答這個問題:如果相等的對象必須具有相同的哈希碼,那麼計算哈希碼就不應包括任何不用於相等檢查的欄位。(否則兩個對象只是這些欄位不同但是仍然有可能會相等，此時他們這兩個對象哈希碼卻會不相同。)
所以用於哈希組欄位應該相等時使用的欄位的子集。默認情況下都使用相同的欄位,但有一些細節需要考慮。
一致性
首先,有一致性的要求。它應該相當嚴格。雖然它允許如果一些欄位改變對應的哈希碼發生變化(對於可變的類是不可避免的)，但是哈希數據結構並不是為這種場景准備的。
正如我們以上所見的哈希碼用於確定元素的桶。但如果hash-relevant欄位發生了改變,並不會重新計算哈希碼、也不會更新內部數組。
這意味著以後通過相等的對象，甚至同一實例進行查詢也會失敗，數據結構計算當前的哈希碼與之前存儲實例計算的哈希碼並不一致,並是錯誤的桶。
結論:最好不要使用可變欄位計算哈希碼!
性能
哈希碼最終計算的頻率與可能調用equals差不多，那麼這里將是影響性能的關鍵部分，因此考慮此部分性能也是非常有意義的。並且與equals相比，優化之後又更大的上升空間。
除非使用非常復雜的演算法或者涉及非常多的欄位，那麼計算哈希碼的運算成本是微不足道的、同樣也是不可避免的。但是也應該考慮是否需要包含所有的欄位來進行運算。集合需要特別警惕的對待。以Lists和sets為例，將會包含集合裡面的每一個元素來計算哈希碼。是否需要調用它們需要具體情況具體分析。
如果性能是至關重要的，使用Objects.hash因為需要為varargs創建一個數組也許並不是最好的選擇。但一般規則優化是適用的:不要過早地使用一個通用的散列碼演算法,也許需要放棄集合,只有優化分析顯示潛在的改進。
碰撞
總是關注性能,這個實現怎麼呢?
@Override
public int hashCode() {
return 0;
}

快是肯定的。相等的對象將具有相同的哈希碼。並且,沒有可變的欄位!
但是，我們之前說過的桶呢？！這種方式下所有的實例將會有相同的桶！這將會導致一個鏈表來包含所有的元素，這樣一來將會有非常差的性能。每次調用contains將會觸發對整個list線性掃描。
我們希望盡可能少的元素在同一個桶!一個演算法返回變化多端的哈希碼,即使對於非常相似的對象,是一個好的開始。
怎樣才能達到上面的效果部分取決於選取的欄位，我們在計算中包含更多的細節，越有可能獲取到不同的哈希碼。注意：這個與我們所說的性能是完全相反的。因此，有趣的是，使用過多或者過少的欄位都會導致糟糕的性能。
防止碰撞的另一部分是使用實際計算散列的演算法。
計算Hsah
最簡單的方法來計算一個欄位的哈希碼是通過直接調用hashCode，結合的話會自動完成。常見的演算法是首先在以任意數量的數值(通常是基本數據類型)反復進行相乘操作再與欄位哈希碼相加
int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;

這可能導致溢出,但是不是特別有問題的,因為他們並沒有產生Java異常。
注意,即使是非常良好的的哈希演算法也可能因為輸入特定的模式的數據有導致頻繁碰撞。作為一個簡單的例子假設我們會計算點的散列通過增加他們的x和y坐標。當我們處理f(x) = -x線上的點時，線上的點都滿足：x + y == 0，將會有大量的碰撞。
但是:我們可以使用一個通用的演算法，只到分析表明並不正確，才需要對哈希演算法進行修改。
總結
我們了解到計算哈希碼就是壓縮相等的一個整數值：相等的對象必須有相同的哈希碼，而出於對性能的考慮：最好是盡可能少的不相等的對象共享相同的哈希碼。
這就意味著如果重寫了equals方法，那麼就必須重寫hashCode方法
當實現hashCode
使用與equals中使用的相同的欄位(或者equals中使用欄位的子集)
最好不要包含可變的欄位。
對集合不要考慮調用hashCode
如果沒有特殊的輸入特定的模式，盡量採用通用的哈希演算法
記住hashCode性能,所以除非分析表明必要性，否則不要浪費太多的精力。

Ⅶ java之地址值和hash值的關系

首先先說hash值，hash值是通過hashCode()Object有這個方法(個別重寫的先不談如String)，你可以去看Object中的hashCode()方法；這個方法上面有（@.....說明英語不好 反正就是表示非顯示不給看的）（被native修飾過的說明不是用本語言寫的就是不是java來實現的），總的來說這個方法就是通過hash演算法來的(後面一個數永遠等於前面兩個數之和)，這個就是哈希值；而電腦是怎麼算的呢？每一個東西都有一個ASCII碼比如a是97....然後現在都是通過斐波那契演算法來算的(想了解的自己去網路)，應該明白哈希值了吧。
然後說說地址值吧，每一個東西都會被電腦放在硬碟內存裡面，然後電腦通過hash演算法得到hash值，最後你的地址值就hash值的十六進制，所以那些地址值有小寫字母什麼的。
所以你有時候重寫hashCode方法注意返回值是int類型但是不是十進制哦!不然會出現erro異常的。所以一般重寫hashCode都是直接返回1即不會輸入特別復雜的數組，不然你還要轉十六進制；還幫你擴展擴展，equals除了String重寫了不同以外，都是繼承了Object類的equlas方法；注意equals比較的也是是否是同一個對象和"=="一樣的一個比較基本數據類型一個比較引用類型的。但是我們只能重寫「equals」，基本數據類型系統自帶不給你顯示的所以我也看不到，其實equals不重寫的話比較的就是地址碼，就是hashCode方法得來的。集合hashSet有時候不能滿足我們加入的條件需要我們自己重寫equlas和hashCode方法了，前面也說了 其實可以只重寫hashCode方法就可以了，那為什麼都要一起寫呢，因為你不覺得十六進制的轉換很麻煩嗎?為了效率基本上都是直接return1；你的條件都是寫在equals裡面。
你可以去試試重寫hashCode方法，在列印這個類對象，顯示的就是包名加地址碼了，不要超過十六這個數字會拋erro異常的。

Ⅷ java中哪些地方實現了一致性hash演算法

關於一致性Hash演算法，在我之前的博文中已經有多次提到了，MemCache超詳細解讀一文中"一致性Hash演算法"部分，對於為什麼要使用一致性Hash演算法、一致性Hash演算法的演算法原理做了詳細的解讀。

演算法的具體原理這里再次貼上：

先構造一個長度為232的整數環（這個環被稱為一致性Hash環），根據節點名稱的Hash值（其分布為[0, 232-1]）將伺服器節點放置在這個Hash環上，然後根據數據的Key值計算得到其Hash值（其分布也為[0, 232-1]），接著在Hash環上順時針查找距離這個Key值的Hash值最近的伺服器節點，完成Key到伺服器的映射查找。

這種演算法解決了普通余數Hash演算法伸縮性差的問題，可以保證在上線、下線伺服器的情況下盡量有多的請求命中原來路由到的伺服器。

當然，萬事不可能十全十美，一致性Hash演算法比普通的余數Hash演算法更具有伸縮性，但是同時其演算法實現也更為復雜，本文就來研究一下，如何利用Java代碼實現一致性Hash演算法。在開始之前，先對一致性Hash演算法中的幾個核心問題進行一些探究。

Ⅸ java中hash函數都有什麼用啊

Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。

簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

HASH主要用於信息安全領域中加密演算法，他把一些不同長度的信息轉化成雜亂的128位的編碼里,叫做HASH值. 也可以說，hash就是找到一種數據內容和數據存放地址之間的映射關系

了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。那麼他們都是什麼意思呢？
這里簡單說一下：

1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用高速軟體實現--它是基於 32 位操作數的位操作來實現的。

2) MD5
MD5(RFC 1321)是 Rivest 於1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。MD5比MD4來得復雜，並且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好

3) SHA1 及其他
SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小於264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基於和MD4相同原理,並且模仿了該演算法。