什么是HashMap
它是將一個(gè)任意長度的二進(jìn)制值通過一個(gè)映射關(guān)系轉(zhuǎn)換為一個(gè)固定長度的二進(jìn)制值。
1、任意長度的二進(jìn)制值
2、映射關(guān)系(哈希算法)
3、固定的二進(jìn)制值(哈希值)
數(shù)組和鏈表組合成的鏈表散列結(jié)構(gòu)，通過hash算法，盡量將數(shù)組中的數(shù)據(jù)分布均勻，如果hashcode相同再比較equals方法，如果equals方法返回false，那么就將數(shù)據(jù)以鏈表的形式存儲(chǔ)在數(shù)組的對(duì)應(yīng)位置，并將之前在該位置的數(shù)據(jù)往鏈表的后面移動(dòng)，并記錄一個(gè)next屬性，來指示后移的那個(gè)數(shù)據(jù)。注意數(shù)組中保存的是entry,其中保存的是鍵值.
hash表
- 特點(diǎn)： 存儲(chǔ)效率高，取數(shù)據(jù)的時(shí)間復(fù)雜度是1 O(1)
- hash 通過一個(gè)key一個(gè)輸入，通過一個(gè)hash函數(shù)，來找到數(shù)組中與這個(gè)key唯一映射的value
- table aaa = 【 】;
- int index = hash(key);
- int value = aaa[index];
- O(n);
hash函數(shù)
key，找下標(biāo)，有哪些方法可以找打下標(biāo)
-
1、取模法
- 定義了一個(gè) aaa[]數(shù)組，長度是16.
- int index = key%m
- m的取值規(guī)則是： m要取比數(shù)組長度小的最大質(zhì)數(shù)
- 此時(shí) m = 13
- int 1 = 1%13 ;key = 1, value = 23
- key = 17 ,value = 44
- int index = 17%15;
2、平方取中法
hash表處理沖突
- 1、線性探測(cè)法： 探測(cè)的步長是1；
- 2、鏈表形式 新的元素會(huì)在鏈表的頭部。next 指針指向老元素的頭部。
hashmap的put方法
- HashMap基于hashing原理，我們通過put()和get()方法儲(chǔ)存和獲取對(duì)象。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用鍵對(duì)象的hashCode()方法來計(jì)算hashcode，然后找到bucket位置來儲(chǔ)存值對(duì)象。當(dāng)獲取對(duì)象時(shí)，通過鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象。HashMap使用鏈表來解決碰撞問題，當(dāng)發(fā)生碰撞了，對(duì)象將會(huì)儲(chǔ)存在鏈表的下一個(gè)節(jié)點(diǎn)中。 HashMap在每個(gè)鏈表節(jié)點(diǎn)中儲(chǔ)存鍵值對(duì)對(duì)象。
hashmap的get方法
hashmap的擴(kuò)容機(jī)制
- 當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小(數(shù)組總大小length,不是數(shù)組中個(gè)數(shù)size)( defaultLoader = 0.75)時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，defaultLoader的默認(rèn)值為0.75，這是一個(gè)折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap中元素個(gè)數(shù)超過160.75=12（這個(gè)值就是代碼中的threshold值，也叫做臨界值）的時(shí)候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。
以下來自轉(zhuǎn)載：
HashMap的工作原理是近年來常見的Java面試題。幾乎每個(gè)Java程序員都知道HashMap，都知道哪里要用HashMap，知道Hashtable和HashMap之間的區(qū)別，那么為何這道面試題如此特殊呢？是因?yàn)檫@道題考察的深度很深。這題經(jīng)常出現(xiàn)在高級(jí)或中高級(jí)面試中。ConcurrentHashMap和其它同步集合的引入讓這道題變得更加復(fù)雜。讓我們開始探索的旅程吧！
“你用過HashMap嗎？” “什么是HashMap？你為什么用到它？”
幾乎每個(gè)人都會(huì)回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值，而Hashtable則不能；HashMap是非synchronized;HashMap很快；以及HashMap儲(chǔ)存的是鍵值對(duì)等等。這顯示出你已經(jīng)用過HashMap，而且對(duì)它相當(dāng)?shù)氖煜?。但是面試官來個(gè)急轉(zhuǎn)直下，從此刻開始問出一些刁鉆的問題，關(guān)于HashMap的更多基礎(chǔ)的細(xì)節(jié)。面試官可能會(huì)問出下面的問題：
“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？”
你也許會(huì)回答“我沒有詳查標(biāo)準(zhǔn)的Java API，你可以看看Java源代碼或者Open JDK?！薄拔铱梢杂肎oogle找到答案?！?/p>
但一些面試者可能可以給出答案，“HashMap是基于hashing的原理，我們使用put(key, value)存儲(chǔ)對(duì)象到HashMap中，使用get(key)從HashMap中獲取對(duì)象。當(dāng)我們給put()方法傳遞鍵和值時(shí)，我們先對(duì)鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲(chǔ)存Entry對(duì)象?！边@里關(guān)鍵點(diǎn)在于指出，HashMap是在bucket中儲(chǔ)存鍵對(duì)象和值對(duì)象，作為Map.Entry。這一點(diǎn)有助于理解獲取對(duì)象的邏輯。如果你沒有意識(shí)到這一點(diǎn)，或者錯(cuò)誤的認(rèn)為僅僅只在bucket中存儲(chǔ)值的話，你將不會(huì)回答如何從HashMap中獲取對(duì)象的邏輯。這個(gè)答案相當(dāng)?shù)恼_，也顯示出面試者確實(shí)知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始，當(dāng)面試官加入一些Java程序員每天要碰到的實(shí)際場(chǎng)景的時(shí)候，錯(cuò)誤的答案頻現(xiàn)。下個(gè)問題可能是關(guān)于HashMap中的碰撞探測(cè)(collision detection)以及碰撞的解決方法：
“當(dāng)兩個(gè)對(duì)象的hashcode相同會(huì)發(fā)生什么？”
從這里開始，真正的困惑開始了，一些面試者會(huì)回答因?yàn)閔ashcode相同，所以兩個(gè)對(duì)象是相等的，HashMap將會(huì)拋出異常，或者不會(huì)存儲(chǔ)它們。然后面試官可能會(huì)提醒他們有equals()和hashCode()兩個(gè)方法，并告訴他們兩個(gè)對(duì)象就算hashcode相同，但是它們可能并不相等。一些面試者可能就此放棄，而另外一些還能繼續(xù)挺進(jìn)，他們回答“因?yàn)閔ashcode相同，所以它們的bucket位置相同，‘碰撞’會(huì)發(fā)生。因?yàn)镠ashMap使用鏈表存儲(chǔ)對(duì)象，這個(gè)Entry(包含有鍵值對(duì)的Map.Entry對(duì)象)會(huì)存儲(chǔ)在鏈表中?！边@個(gè)答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡(jiǎn)單的，也正是HashMap的處理方法。但故事還沒有完結(jié)，面試官會(huì)繼續(xù)問：
“如果兩個(gè)鍵的hashcode相同，你如何獲取值對(duì)象？”
面試者會(huì)回答：當(dāng)我們調(diào)用get()方法，HashMap會(huì)使用鍵對(duì)象的hashcode找到bucket位置，然后獲取值對(duì)象。面試官提醒他如果有兩個(gè)值對(duì)象儲(chǔ)存在同一個(gè)bucket，他給出答案:將會(huì)遍歷鏈表直到找到值對(duì)象。面試官會(huì)問因?yàn)槟悴]有值對(duì)象去比較，你是如何確定確定找到值對(duì)象的？除非面試者直到HashMap在鏈表中存儲(chǔ)的是鍵值對(duì)，否則他們不可能回答出這一題。
其中一些記得這個(gè)重要知識(shí)點(diǎn)的面試者會(huì)說，找到bucket位置之后，會(huì)調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點(diǎn)，最終找到要找的值對(duì)象。完美的答案！
許多情況下，面試者會(huì)在這個(gè)環(huán)節(jié)中出錯(cuò)，因?yàn)樗麄兓煜薶ashCode()和equals()方法。因?yàn)樵诖酥癶ashCode()屢屢出現(xiàn)，而equals()方法僅僅在獲取值對(duì)象的時(shí)候才出現(xiàn)。一些優(yōu)秀的開發(fā)者會(huì)指出使用不可變的、聲明作final的對(duì)象，并且采用合適的equals()和hashCode()方法的話，將會(huì)減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個(gè)獲取對(duì)象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。
如果你認(rèn)為到這里已經(jīng)完結(jié)了，那么聽到下面這個(gè)問題的時(shí)候，你會(huì)大吃一驚。
“如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦？”
除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認(rèn)的負(fù)載因子大小為0.75，也就是說，當(dāng)一個(gè)map填滿了75%的bucket時(shí)候，和其它集合類(如ArrayList等)一樣，將會(huì)創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小，并將原來的對(duì)象放入新的bucket數(shù)組中。這個(gè)過程叫作rehashing，因?yàn)樗{(diào)用hash方法找到新的bucket位置。
如果你能夠回答這道問題，下面的問題來了：
“你了解重新調(diào)整HashMap大小存在什么問題嗎？”
你可能回答不上來，這時(shí)面試官會(huì)提醒你當(dāng)多線程的情況下，可能產(chǎn)生條件競(jìng)爭(zhēng)(race condition)。
當(dāng)重新調(diào)整HashMap大小的時(shí)候，確實(shí)存在條件競(jìng)爭(zhēng)，因?yàn)槿绻麅蓚€(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會(huì)同時(shí)試著調(diào)整大小。在調(diào)整大小的過程中，存儲(chǔ)在鏈表中的元素的次序會(huì)反過來，因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候，HashMap并不會(huì)將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競(jìng)爭(zhēng)發(fā)生了，那么就死循環(huán)了。這個(gè)時(shí)候，你可以質(zhì)問面試官，為什么這么奇怪，要在多線程的環(huán)境下使用HashMap呢？：）
熱心的讀者貢獻(xiàn)了更多的關(guān)于HashMap的問題：
-
為什么String, Interger這樣的wrapper類適合作為鍵？
String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因?yàn)镾tring是不可變的，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個(gè)特點(diǎn)。不可變性是必要的，因?yàn)闉榱艘?jì)算hashCode()，就要防止鍵值改變，如果鍵值在放入時(shí)和獲取時(shí)返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對(duì)象。不可變性還有其他的優(yōu)點(diǎn)如線程安全。如果你可以僅僅通過將某個(gè)field聲明成final就能保證hashCode是不變的，那么請(qǐng)這么做吧。因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫這兩個(gè)方法是非常重要的。如果兩個(gè)不相等的對(duì)象返回不同的hashcode的話，那么碰撞的幾率就會(huì)小些，這樣就能提高HashMap的性能。
-
我們可以使用自定義的對(duì)象作為鍵嗎？
這是前一個(gè)問題的延伸。當(dāng)然你可能使用任何對(duì)象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當(dāng)對(duì)象插入到Map中之后將不會(huì)再改變了。如果這個(gè)自定義對(duì)象時(shí)不可變的，那么它已經(jīng)滿足了作為鍵的條件，因?yàn)楫?dāng)它創(chuàng)建之后就已經(jīng)不能改變了。
-
我們可以使用CocurrentHashMap來代替Hashtable嗎？
這是另外一個(gè)很熱門的面試題，因?yàn)镃oncurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因?yàn)樗鼉H僅根據(jù)同步級(jí)別對(duì)map的一部分進(jìn)行上鎖。ConcurrentHashMap當(dāng)然可以代替HashTable，但是HashTable提供更強(qiáng)的線程安全性?？纯?a target="_blank" rel="nofollow">這篇博客查看Hashtable和ConcurrentHashMap的區(qū)別。
我個(gè)人很喜歡這個(gè)問題，因?yàn)檫@個(gè)問題的深度和廣度，也不直接的涉及到不同的概念。讓我們?cè)賮砜纯催@些問題設(shè)計(jì)哪些知識(shí)點(diǎn)：
- hashing的概念
- HashMap中解決碰撞的方法
- equals()和hashCode()的應(yīng)用，以及它們?cè)贖ashMap中的重要性
- 不可變對(duì)象的好處
- HashMap多線程的條件競(jìng)爭(zhēng)
- 重新調(diào)整HashMap的大小
HashMap的工作原理
HashMap基于hashing原理，我們通過put()和get()方法儲(chǔ)存和獲取對(duì)象。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用鍵對(duì)象的hashCode()方法來計(jì)算hashcode，讓后找到bucket位置來儲(chǔ)存值對(duì)象。當(dāng)獲取對(duì)象時(shí)，通過鍵對(duì)象的equals()方法找到正確的鍵值對(duì)，然后返回值對(duì)象。HashMap使用鏈表來解決碰撞問題，當(dāng)發(fā)生碰撞了，對(duì)象將會(huì)儲(chǔ)存在鏈表的下一個(gè)節(jié)點(diǎn)中。 HashMap在每個(gè)鏈表節(jié)點(diǎn)中儲(chǔ)存鍵值對(duì)對(duì)象。
當(dāng)兩個(gè)不同的鍵對(duì)象的hashcode相同時(shí)會(huì)發(fā)生什么？ 它們會(huì)儲(chǔ)存在同一個(gè)bucket位置的鏈表中。鍵對(duì)象的equals()方法用來找到鍵值對(duì)。
所有代碼如下：interface DNMap
public interface DNMap <K,V> {
public V put(K k ,V v);
public V get(K k);
public int size();
public interface Entry<K ,V>{
public K getKey();
public V getValue();
}
}
/**
* Created by Kenvin on 2017/11/8.
*/
public class DNHashMap <K,V> implements DNMap<K,V>{
private static int defaultLength = 16;
private static double defaultLoader = 0.75;//警示標(biāo)識(shí)
private Entry<K,V>[] table = null;
private int size = 0;
public DNHashMap(int length ,double loader) {
defaultLength = length;
defaultLoader = loader;
}
public DNHashMap(){
this(defaultLength,defaultLoader);
table = new Entry[defaultLength];
}
private int getIndex(K k){
int m = defaultLength;
int index = k.hashCode() %(m-1);
return index >= 0 ? index : -index;
}
@Override
public V put(K k, V v) {
//判斷size是否達(dá)到擴(kuò)容的標(biāo)準(zhǔn)
if (size>=defaultLength*defaultLoader){
//當(dāng)哈希表的容量超過默認(rèn)容量時(shí)，必須調(diào)整table的大小。
// 當(dāng)容量已經(jīng)達(dá)到最大可能值時(shí)，那么該方法就將容量調(diào)整到Integer.MAX_VALUE返回，
// 這時(shí)，需要?jiǎng)?chuàng)建一張新表，將原表的映射到新表中。
upDateSize();
}
int index = getIndex(k);
Entry<K,V> entry = table[index] ;
if (entry == null){
table[index] = newEntry(k,v,null);
size++;
}else {
//如何index 位置元素不為空，說明有數(shù)據(jù)，指針指向老數(shù)據(jù)
table[index] = newEntry(k,v,entry);
}
return table[index].getValue();
}
private void upDateSize(){
Entry<K,V>[] newTable = new Entry[2*defaultLength];//擴(kuò)容之后表的數(shù)據(jù)或者鏈表的數(shù)據(jù)需要重新放置
againHash(newTable);
}
private void againHash(Entry<K,V>[] newTable){
List<Entry<K,V>> list = new ArrayList<>();
//如何拿之前的老數(shù)據(jù)
for (int i = 0; i <table.length ; i++) {
if (table[i] == null){
continue;
}
findEntryByNext(table[i],list);
}
//不為空可能是一個(gè)鏈表。此時(shí)用一個(gè)集合來處理
if (list.size() > 0 ){
//進(jìn)行新數(shù)組的再散列
size = 0;
defaultLength= 2*defaultLength;
table = newTable;
for (Entry<K,V> entry:list
) {
if (entry.next !=null){
entry.next =null;
}
put(entry.getKey(),entry.getValue());
}
}
}
// 遞歸操作
private void findEntryByNext(Entry<K,V> entry,List<Entry<K,V>> list){
if (entry!= null && entry.next!=null){
list.add(entry);
findEntryByNext(entry.next,list);
}else {
list.add(entry);
}
}
private Entry<K,V> newEntry(K k,V v,Entry<K,V> next){
return new Entry<>(k,v,next);
}
@Override
public V get(K k) {
int index = getIndex(k);
if (table[index] == null){
return null;
}
return findValueByEqualKey(k,table[index]);
}
public V findValueByEqualKey(K k,Entry<K,V> entry){
if (k == entry.getKey() || k.equals(entry.getKey())){
return entry.getValue();
}else {
if (entry.next != null){
return findValueByEqualKey(k,entry.next);
}
}
return entry.getValue();
}
@Override
public int size() {
return size;
}
class Entry<K,V> implements DNMap.Entry<K,V> {
K k;
V v;
Entry<K,V> next ;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
}
