當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

HashMap(2)-----哈希表

發布時間：2023/12/8 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 HashMap(2)-----哈希表小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

自己實現一個哈希表

class Node { int data;String val;Node next;public Node(int data,String val){ this.val=val;this.data=data;} } class myhashtable { Node arr1[];Node head=null;Node tail=null;int count=0;private double load=0.75;public myhashtable() {this.arr1 = new Node[10];}public void reasize(){Node[] arr2=new Node[2*(arr1.length)]; //新創建一個數組，長度為原來長度的二倍,這里面不可以用Arrays.Copy來進行拷貝for(int i=0;i<arr1.length;i++){Node current=arr1[i];while(current!=null){ Node curentnxst=current.next;int key=current.data%(arr2.length);//獲取新的下標current.next=arr1[key];arr2[key].next=current;current=curentnxst;}}this.arr1=arr2;}public int push(int key,String str){ if((1.0)*(count/arr1.length)>load){reasize();}Node node=new Node(key,str);int index=key%arr1.length;Node current=arr1[index];while(current!=null)//先遍歷數組下標的整個鏈表，發現如果key相同，那么就更新val的值{ if(current.data==key){current.val=str;return key;}current=current.next;}node.next=arr1[index];arr1[index]=node;count++;return -1;}}

1)鏈表的長度不會很長，控制在常數范圍內，從JDK1.8開始，當數組長度超過64況且鏈表長度超過8就會轉化成紅黑樹，也就是說雖然哈希表一直在和沖突作斗爭，但是我們認為哈希表的沖突概率是不高的，沖突個數是可控的，也就是說每一個桶中的鏈表長度是一個常數，所以我們通常情況下認為哈希表的插入刪除，查找的時間復雜度是O(1)

2)對于擴容來說:采用擴容之后，原來桶中的所有數據(數組中每一個鏈表的每一個元素必須要進行重新哈希)，要遍歷原來的鏈表，這個一定要注意不能在原來的數組上面進行2倍擴容，假設原來數組長度是10，沒擴容之前數據14是被放在4下標的，但是假設擴容之后變成2倍，數據14就被放在14下標了

3)上面我們的哈希表是整形，但如果是任意類型，怎么辦，如果key是String類型，總不可以讓

一個字符串來對一個數組長度求余數吧；

上代碼：

class Hello{class Node<K,V>{K k;V v;Node next;public Node(K k, V v) {this.k = k;this.v = v;}} public class hasntable<K,V> {Node arr1[];int count=0;public hasntable() {Node arr2[] = (Node[])new Node[10];}public void reasize(){ Node[]arr2=new Node[2*(arr1.length)];for(int j=0;j<arr1.length;j++){Node current=arr1[j];while(current!=null){Node currentnext=current.next;int hash=current.k.hashCode();int index=hash%arr2.length;current.next=arr1[index];arr1[index].next=current;current=currentnext;}}}public void push(K k,V v){ if((1.0)*(count)/(arr1.length)>0.75){reasize();}// int index=k%arr1.length;此時k為引用類型int hash=k.hashCode();int index=hash%arr1.length;Node<K,V> current=arr1[index];while(current!=null){//if(current.k==k)//是引用類型不可以直接比較雖然不報錯，但是比較比較的是地址，而不是自定義類型的內容if(current.k.equals(k)){current.v=v;return;}current=current.next;}Node<K,V> node=new Node<>(k,v);node.next=arr1[index];arr1[index]=node;count++;} }

1)我們在向Map中寫入自定義類型的時候，一定要重寫hashCode和equals方法，當HashMap<Person, String> map=new HashMap<>();我們希望把id相同的Person放到哈希表的相同位置；

2)我們是用hashcode來確定這個k的位置上，使用equals比較哪一個k和我們當前這個k是相同的

1)hashcode一樣，那么equals不一定一樣，hashcode一樣只能證明兩個元素在數組的相同位置,但是一個數組的一個位置下面有多個元素組成的鏈表

2)equals相同，hashcode一定相同

package Demo; import java.util.Objects; class Person{public int age;public String name;public Person(String name,int age){this.name=name;this.age=age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return age == person.age && Objects.equals(name, person.name);}@Overridepublic int hashCode() {return Objects.hash(age, name);} } class MyHashMap<K,V>{public int UsedSize=0;public Node<K,V>[] array=(Node<K, V>[])new Node[10];static class Node<K,V>{public K k;public V v;public Node next;public Node(K k,V v){this.k=k;this.v=v;}}public void put(K k,V v){int index=k.hashCode()%array.length;//得到這個值對應的數組下標,必須重寫hashcode//否則兩個邏輯上相同的值會得到不同的哈希值,就會被放到數組種不同的位置Node current=array[index];while(current!=null){if(current.k.equals(k))//不能使用==//現在k是一個引用類型,使用==默認比較的是地址,所以我們使用equals,但是直接使用equals比較的還是兩個引用的地址《//所以我們要重寫equals方法,來進行比較他們具體的內容{current.v=v;return;}}//我們是頭插法來進行插入元素Node<K,V> node=new Node<>(k,v);node.next=array[index];array[index]=node;UsedSize++;//判斷是否負載因子超過了0.75,如果超過,就進行擴容if(UsedSize/array.length>0.75){CreateBigSizeArray(array);}}private void CreateBigSizeArray(Node<K,V>[] array) {Node[] newArray=new Node[2* array.length];for(int i=0;i<array.length;i++){//遍歷每一個哈希桶,也就是說遍歷數組的每一個元素Node current=array[i];//遍歷數組下的每一個鏈表while(current!=null){Node child=current.next;int index=current.v.hashCode()%newArray.length;current.next=array[index];array[index]=current;current=child;}}} } public class HelloWorld{public static void main(String[] args) {MyHashMap<Person,String> map=new MyHashMap<>();map.put(new Person("李佳偉",90),"bit");map.put(new Person("李嘉欣",100),"kig");System.out.println(map);}}

解析HashMap源碼:

1)public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable,Serializable(是可序列化的)

AbstractMap是一個普通的抽象類，Serializable是可序列化的，說明可以把一個對象變成字符串

2)static final int DEFAULT_INITIAL_CAPACITY=1<<4;說明他的默認容量是16,必須是2的次冪

3)static final int MAXIMUM_CAPACITY=1<<30;說明他的最大長度是2^30;

4)static final float DEFAUIT_LOAD_FACTOR=0.75f;默認的負載因子

5)static final TREEINF_THRESHOLD=8;這是樹化的條件(鏈表長度超過8)

6)static final int UNTREEIFY_THRESHOLD=6;不樹化

這是桶的鏈表還原閾值:即紅黑樹轉化成鏈表的值,當進行擴容之后,此時的HashMap的值會進行重新計算，在進行重新計算存儲位置后當原有的紅黑樹數量小于6之后，會將紅黑樹轉化成鏈表

7)static final int min_treeinfy_capacity=64

8)Node在哈希表中是一個內部類

9)HashMap一共有三個構造方法

1))無參構造方法

2))傳輸一個初始容量

3))傳輸一個初始容量和指定負載因子

位運算算效率高

public V put(K key,V value)

{? ??

? ? ? ? return putVal(hash(key),key,value,false,true);//第四個參數表示是老元素的值不會保留，會進行覆蓋

static final int hash(Object Key)

{

? ? ?int h;

? ? ?return (key==null?0:(h==key.hashcode())^(h>>>16);

//得到的哈希地址已經是32位了，為了混合哈希值的高位和低位，高半區和低半區做異或，混合原始哈希碼的高位和地位，增加低位的隨機性，摻雜了高位的部分特征，混合之后的低位核心目的是為了讓hash值的散列度更高，盡可能減少hash表的hash沖突，從而提升數據查找的性能，并且混合后的值也保持了高位的特征

}

這個哈希函數的作用就是根據key的哈希值來進行計算這個元素在數組中的位置，求解這個哈希值的過程就是哈希算法，異或就是相同為0，不同為1

1)當調用沒有參數的構造方法的時候

當數組長度是0或者數組的引用為空的時候，第一次put操作的時候，就會執行reasize()的方法來進行擴容，默認的初始容量是16；

2)根據哈希值來進行計算索引的時候

(在尋找數組的下標的時候，在咱們之前的代碼中時使用Key的哈希值%數組長度，但是在HashMap的源碼中是用數組下標=(數組長度-1)&hash)

4&15==4%16如果數組的長度是2的次冪，這樣hash%n-1的值(也就是得到位置)相等，位運算的速度更快，效率更高；再會new Node;

(n-1)&hash保證n是偶數(&都為1才是1，否則就是0）

如果n是偶數，那么n-1的最后一位一定是1，當與hash函數(最后一位有可能是進行0也有可能是1)&運算的時候,得到的最后一位是0或者1；即有可能是奇數也有可能是偶數

如果n是奇數，那么n-1的最后一位是0，那么與hash函數進行&操作的時候，會得到的下標的最后一位為0；最后只能得到偶數下標；

就是說我們以初始容量為16來進行舉例，16-1=15，那么15的二進制序列就是001111，我們可以看出一個奇數二進制最后一位必然是1，當一個hash值參與運算的時候，最后一位可能是1，也有可能是0，當一個偶數和hash值進行與運算的時候最后一位必然是0，會造成有些位置永遠也無法映射上值

3)保證數組容量是偶數，才可以保證最后的下標即是奇數下標又是偶數下標

?HashMap和HashTable的區別？

咱們的hashMap是允許key和value是空值的，但是hashtable這樣的線程安全的集合數不允許插入空的key和value的，在咱們ConcurrentHashMap的源碼當中，如果key為空，或者value為空，直接拋出空指針異常

1)兩者最主要的區別在于Hashtable是線程安全，而HashMap則非線程安全

2)HashMap可以使用null作為key，不過建議還是盡量避免這樣使用。HashMap以null作為key時，總是存儲在table數組的第一個節點上。而Hashtable則不允許null作為key。

3)HashMap繼承了AbstractMap，HashTable繼承Dictionary抽象類，兩者均實現Map接口。
4)HashMap的初始容量為16，Hashtable初始容量為11，兩者的填充因子默認都是0.75。
5)HashMap擴容時是當前容量翻倍即:capacity*2，Hashtable擴容時是容量翻倍+1即:capacity*2+1。
6)HashMap數據結構：數組+鏈表+紅黑樹（jdk1.8里加入了紅黑樹的實現，當鏈表的長度大于8時，轉換為紅黑樹的結構），Hashtable數據結構：數組+鏈表。

7)HashMap和HashTable都實現了Serializable接口，因此它支持序列化，實現了Cloneable接口，能被克隆。

8)計算哈希值也是不同的:hashMap先計算出哈希值，然后無符號右移16位，然后再進行按位與操作，但是hashTable

int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;

總結:?

1)首先查看數組長度是否為空，如果為空，就進行第一次擴容

2)計算索引:通過哈希算法，找到鍵值對在數組中的位置

3)插入元素:

3.1)如果當前元素位置為空，直接插入數據

3.2)不為空，判斷是否為紅黑樹，是紅黑樹直接插入鍵值對

3.3)如果他不是紅黑樹，接下來判斷，若鏈表長度大于8，數組長度超過64，直接將鏈表轉化成紅黑樹，然后將數據插入到樹中

3.4)如果不滿足這兩個條件的任意一個，那么直接遍歷鏈表，key已經存在直接覆蓋value

4)再次擴容，超過負載因子，直接進行擴容，重新哈希

5)超過數組容量進行擴容

HashMap的常見問題:

HashMap的節點有hash值，key，val，next

1)程序問題:

在HashMapJDK1.7的程序里面會出現死循環或者是數據覆蓋的問題；死循環由于是HashMap的自身的運行機制再加上并發操作

1)比如說現在數組中的某一個元素下面掛著鏈表，鏈表中的元素從上到下的順序是A B C? ? ? ? ,但是JDK1.7用的是頭插法，那么進行擴容之后為數據位置是C B A，這是死循環的前提，是由于HashMap并發進行擴容而導致的

2)但是線程1擴容完成之后數據的變化為

2)數據覆蓋問題:

1)線程T1進行添加的時候，判斷某一個位置可以進行插入元素了，但還沒有真正地進行插入操作，時間片就用完了(此時線程1已經判斷好這個位置是空了，剛剛要進行插入操作，就被調度器給搶走了)

2)線程2也想要進行插入操作，并且T2要進行插入的數據產生的哈希值和T1要進行插入的數據是相同的，由于此位置沒有任何元素(T1只是進行判斷，剛想要插入值就被調度器給搶走了)，于是此時線程2就把自己的值存入到當前位置了

3)T1線程恢復執行之后，因為非空判斷已經執行完了，他是無法感知當前位置已經有值了，于是就把自己的值插入到了該位置，于是T2線程插入的值就被覆蓋了

3)HashMap無序性問題------換成LinkedHashMap

總結

以上是生活随笔為你收集整理的HashMap(2)-----哈希表的全部內容，希望文章能夠幫你解決所遇到的問題。

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

上一篇： 2017最新上海市居住证申领流程
下一篇：浏览器起始页设置