到底什么是hash

hash算法的概念

Hash:

一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。

這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

例子：

你很想學太極拳，聽說學校有個叫張三豐的人打得特別好，于是你到學校學生處找人， 學生處的工作人員可能會拿出學生名單，一個一個的查找，最終告訴你，學校沒這個人， 并說張三豐幾百年前就已經在武當山作古了。 可如果你找對了人，比如在操場上找那些愛運動的同學，人家會告訴你，"哦，你找張三豐呀， 有有有，我帶你去。于是他把你帶到了體育館內，并告訴你，那個教大家打太極的小伙子就是張三豐'， 原來"張三豐.是因為他太極拳打得好而得到的外號。學生處的老師找張三豐，那就是順序表查找， 依賴的是姓名關鍵字的比較。而通過愛好運動的同學詢問時，沒有遍歷，沒有比較， 就憑他們"欲找太極'張三豐'，必在體育館當中"的經驗，直接告訴你位置。

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

hash表

Hash表也稱散列表，也有直接譯作哈希表，Hash表是一種特殊的數據結構，它同數組、鏈表以及二叉排序樹等相比較有很明顯的區別，它能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關鍵字進行比較來進行查找。

這個源于Hash表設計的特殊性，它采用了函數映射的思想將記錄的存儲位置與記錄的關鍵字關聯起來，從而能夠很快速地進行查找。

Hash表的設計思想

對于一般的線性表，比如鏈表，如果要存儲聯系人信息：

張三

13980593357

李四

15828662334

王五

13409821234

張帥

13890583472

那么可能會設計一個結構體包含姓名，手機號碼這些信息，然后把4個聯系人的信息存到一張鏈表中。

查找數據：

當要查找”李四 15828662334“這條記錄是否在這張鏈表中或者想要得到李四的手機號碼時，可能會從鏈表的頭結點開始遍歷，依次將每個結點中的姓名同”李四“進行比較，直到查找成功或者失敗為止，這種做法的時間復雜度為O(n)。

假設能夠通過”李四“這個信息直接獲取到該記錄在表中的存儲位置，就能省掉中間關鍵字比較的這個環節，復雜度直接降到O(1)。Hash表就能夠達到這樣的效果。

原理：

Hash表采用一個映射函數 f : key —> address 將關鍵字映射到該記錄在表中的存儲位置，從而在想要查找該記錄時，可以直接根據關鍵字和映射關系計算出該記錄在表中的存儲位置.

通常情況下，這種映射關系稱作為Hash函數，而通過Hash函數和關鍵字計算出來的存儲位置(注意這里的存儲位置只是表中的存儲位置，并不是實際的物理地址)稱作為Hash地址.

比如上述例子中，假如聯系人信息采用Hash表存儲，則當想要找到“李四”的信息時，直接根據“李四”和Hash函數計算出Hash地址即可

hash函數

hash函數就是把任意長的輸入字符串變化成固定長的輸出字符串的一種函數。輸出字符串的長度稱為hash函數的位數。

一句話：散列（Hashing）通過散列函數將要檢索的項與索引（散列，散列值）關聯起來，生成一種便于搜索的數據結構（散列表）。

散列函數的性質：

同一函數的散列值不相同，那么其原始輸入也不相同，上圖中k1，k3和k4。（確定性）

散列函數的輸入和輸出不是唯一對應關系的，如果兩個散列值相同，兩個輸入值很可能是不相同的，上圖中的k2，k5這種情況稱為“哈希碰撞”。（不確定性）

hash函數的構造準則：簡單、均勻

1、 散列函數的計算簡單，快速；

2、 散列函數能將關鍵字集合K均勻地分布在地址集{0,1，…，m-1}上，使沖突最小。

對象的獲取

思考：

java虛擬機是如何去內存里面獲取到我們想要的對象呢？

問題：

站在JAVA虛擬機的角度，在內存里面有好多好多個對象，這里用橢圓來代表一個個對象。那么對于JAVA虛擬機來說，它運行的時候需要找到這些對象的地址，這些對象的地址怎么找呢？

解析:

JAVA虛擬機會用一張表記錄每一個對象在什么位置上，而這張表一般是用哈希編碼來記錄，每一個對象都有自己獨一無二的哈希編碼，根據這個編碼就可以找到相關的對象，也就是說，根據這個編碼你可以獨一無二地確定這個對象，并且可以非常快地確定這個對象所在的位置，可以簡單這么理解哈希編碼的作用。

hashcode方法

在object類中，hashcode()方法是本地方法，返回的是對象的地址值。

JAVA代碼：

public static void main(String[] args){ Object obj1 = new Object(); Object obj2= new Object(); Object obj3 = obj2; System.out.println("obj1's hashcode: "+obj1.hashCode()); System.out.println("obj1's hashcode: "+obj2.hashCode()); System.out.println("obj1's hashcode: "+obj3.hashCode()); } /* 結果為： obj1's hashcode: 12677476 obj1's hashcode: 33263331 obj1's hashcode: 33263331 */

從這個結果中我們可以看到。obj1和obj2的hashcode編碼不相等，obj2和obj3的hashcode編碼相等。我們可以這樣說，obj2和obj3在內存里面引用的是同一個對象。

equals方法

在object類中有一個方法叫equals()，用于判讀兩個對象是否相等。The requested content cannot be loaded.

Please try again later.

java代碼：

public static void main(String[] args){ Object obj1 = new Object(); Object obj2= new Object(); Object obj3 = obj2; System.out.println("obj1==obj2 ?"+obj1.equals(obj2)); System.out.println("obj2==obj3 ?"+obj2.equals(obj3)); } /* 結果是： obj1==obj2 ? false obj2==obj3 ? true */

API Object類中源代碼：

public boolean equals(Object obj) { return (this == obj); }

也就是當我們寫了一個自己的class，然后用class new了兩個對象，如果在這兩個對象上用equals時，此時比較的兩個引用是不是一樣，也就是他們的物理地址是不是一樣，如果不一樣的話，就會返回false.

Student stu = new Student(); stu.setId(1); stu.setUsername("xiaowang"); Student stu2 = new Student(); stu2.setId(1); stu2.setUsername("xiaowang"); System.out.println(stu.equals(stu2)); // 輸出false

我們實際用的時候，往往不是希望比較兩個對象的物理地址是不是一樣，而比較兩個對象的屬性等東西是不是一樣，所以Object提供的方法往往不能滿足我們要求。

這就需要我們覆蓋Object的equals方法。

如果要覆蓋Object的equals的方法，一定要滿足以下幾個等價關系：

自反性，對于任何非null的引用值x，x.equals(x)必須反回true

對稱性，對于任何非null的引用值x，y,當且僅當y.equals(x)返回true時，x.equals(y),才返回true.

傳遞性，對于任何非null的引用值x，y，z，如果x.equals(y)返回true，并且y.equals(z)返回ture，那
么x.equals(z)也必須返回true.

一致性，對于任何非null的引用值x，y，只要equals比較操作的兩個對象中所用的信息沒有被修改，多次
調用x.equals(y)就會一致的返回true,或者一致的返回false.

對于任何的非null的值x,x.equals(null),必須返回false .

在Student類里面重寫了父類的equals方法：

@Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (!(obj instanceof Student)) return false; Student other = (Student) obj; if (id != other.id) return false; if (username == null) { if (other.username != null) return false; } else if (!username.equals(other.username)) return false; return true; } } //在來執行上面的代碼，輸出結果為：true

HashSet和HashMap

HashMap的工作原理

equals：是否同一個對象實例。注意，是“實例”。比如String s = new String(“test”); s.equals(s), 這就是同一個對象實例的比較；

等號(==)：對比對象實例的內存地址（也即對象實例的ID），來判斷是否是同一對象實例；又可以說是判斷對象實例是否物理相等；

Hashcode：我覺得可以這樣理解：并不是對象的內存地址，而是利用hash算法，對對象實例的一種描述符（或者說對象存儲位置的hash算法映射）——對象實例的哈希碼。

HashMap的數據結構是基于數組和鏈表的。（以數組存儲元素，如有hash相同的元素，在數組結構中，創建鏈表結構，再把hash相同的元素放到鏈表的下一個節點）.

hashMap的結構類似這樣

元素0-->[hashCode=0, key.value=x1的數據] 元素1-->[hashCode=1, key.value=y1的數據] ...... 元素n-->[hashCode=n, key.value=z1的數據]

假設沒有hashCode=1的元素加入，但是有兩個hashCode=0的數據，它的結構就變成這樣

元素0-->[hashCode=0, key.value=x1的數據].next-->[hashCode=0, key.value=x2的數據] 元素1-->[null] ...... 元素n-->[hashCode=n, key.value=z1的數據]

put和get都首先會調用hashcode方法，去查找相關的key，當有沖突時，再調用equals（這也是為什么剛開始就重溫hashcode和equals的原因）！

HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，然后找到bucket位置來儲存值對象

當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。

HashMap使用鏈表來解決碰撞問題，當發生碰撞了，對象將會儲存在鏈表的下一個節點中。HashMap在每個鏈表節點中儲存鍵值對對象。

HashSet排除重復原理

Java中的set是一個不包含重復元素的集合，確切地說，是不包含e1.equals(e2)的元素對。Set中允許添加null。Set不能保證集合里元素的順序。

在往set中添加元素時，如果指定元素不存在，則添加成功。也就是說，如果set中不存在(e==null ? e1==null : e.queals(e1))的元素e1,則e1能添加到set中。

下面以set的一個實現類HashSet為例，簡單介紹一下set不重復實現

package com.lovo.test; public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } }

---

public class HashSetTest { public static void main(String[] args) { String a = new String("A"); String b = new String("A"); CustomString c = new CustomString("B"); CustomString d = new CustomString("B"); System.out.println("a.equals(b) == " + a.equals(b)); System.out.println("c.equals(d) == " + c.equals(d)); Set<Object> set = new HashSet<Object>(); set.add(a); set.add(b); set.add(c); set.add(d); System.out.println("set.size() == " + set.size()); for (Object object : set) { System.out.println(object); } } } /* 運行結果如下： a.equals(b) == true c.equals(d) == false set.size() == 3 com.darren.test.overide.CustomString@2c39d2 A com.darren.test.overide.CustomString@5795ce */

通過結果來分析，我們看到a和b返回true那是因為String類重寫了equals方法，但是打印集合里面的數據，卻只輸出了一個A,c和d都輸出了。那我們就要思考，難道set集合排除重復跟equals方法有關嗎？，接下來繼續進行測試。

public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } else if (obj instanceof CustomString) { CustomString customString = (CustomString) obj; return customString.value.equals(value); } else { return false; } } } /* 測試結果： a.equals(b) == true c.equals(d) == true set.size() == 3 com.darren.test.overide.CustomString@12504e0 A com.darren.test.overide.CustomString@1630eb6 */

這次的equals返回值都為true，但是set的size還是3。

通過這個結果我們可以看出，重寫了equals方法可以判斷兩個對象的值相等。所以第二個判斷輸出了true，但是并沒有影響set集合里面的數據。

繼續修改代碼：

public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } @Override public int hashCode() { // return super.hashCode(); return 1; } } /* a.equals(b) == true c.equals(d) == false set.size() == 3 com.darren.test.overide.CustomString@1 com.darren.test.overide.CustomString@1 A */

如果只重寫hashcode方法，set集合里面的數據還是沒有變化。

繼續來測試：

public class CustomString { private String value; public CustomString() { this(""); } public CustomString(String value) { this.value = value; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } else if (obj instanceof CustomString) { CustomString customString = (CustomString) obj; return customString.value.equals(value); } else { return false; } } @Override public int hashCode() { // return super.hashCode(); return 1; } } /* 最后結果： a.equals(b) == true c.equals(d) == true set.size() == 2 com.darren.test.overide.CustomString@1 A */

現在我們獲取到的集合長度為2，已經將重復的數據進行排除了。

總結

以上是生活随笔為你收集整理的hash地址_到底什么是Hash？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。