這篇文章將為大家詳細(xì)講解有關(guān)Java中HashMap的實(shí)現(xiàn)原理是什么，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對相關(guān)知識(shí)有一定的了解。

創(chuàng)新互聯(lián)公司主要從事做網(wǎng)站、成都做網(wǎng)站、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)隆回,10年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108

一、Java中的HashCode 和equals

• 關(guān)于hashcode

    1、hashcode的存在主要是用于查找的快捷性，如Hashtable,HashMap等，hashCode是用來在散列存儲(chǔ)結(jié)構(gòu)中確定對象的存儲(chǔ)地址的。

    2、如果兩個(gè)對象相同，就是適用于equals（java.lang.Object)方法，那么這個(gè)兩個(gè)對象的hashCode一定要相同。

    3、如果對象的equals方法被重寫，那么對象的hashCode也盡量重寫，并且產(chǎn)生hashCode使用的對象，一定要和equals方法中使用的一致，否則就會(huì)違反上面提到的第二點(diǎn)

    4、兩個(gè)對象的hashCode相同，并不一定表示兩個(gè)對象就相同，也就是不一定適用于equals（java.lang.Object)方法，只能夠說明這兩個(gè)對象在散列存儲(chǔ)結(jié)構(gòu)中，如Hashtable.他們存放在同一個(gè)籃子里

hashCode 用于查找使用的，equals是用于比較兩個(gè)對象是否相等。

• 關(guān)于equals

    1、equals 和 ==

==用于比較引用和比較基本數(shù)據(jù)類型時(shí)具有不同的功能：

比較基本數(shù)據(jù)類型，如果兩個(gè)值相同，則結(jié)果為true

而在比較引用時(shí)，如果引用指向內(nèi)存中的同一對象，結(jié)果為true；

equals()作為方法，實(shí)現(xiàn)對象的比較。由于==運(yùn)算符不允許我們進(jìn)行覆蓋，也就是說它限制了我們的表達(dá)。因此我們復(fù)寫（重寫，子類復(fù)寫）equals方法，達(dá)到比較對象內(nèi)容是否相同的目的。而這些通過==運(yùn)算符是做不到的。

    2、Object類的equals（）方法的比較規(guī)則為：如果兩個(gè)對象的類型一致，并且內(nèi)容一致，則返回true，這些類有：

java.io.file,java.util.Date,java.lang.string,包裝類（Integer，Double等）

二、HashMap的實(shí)現(xiàn)原理

1、HashMap概述

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。

在Java編程語言中，最基本的結(jié)構(gòu)就是兩種，一種是數(shù)組，另一個(gè)是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來構(gòu)造，HashMap也不列外。HashMap也不例外。HashMap實(shí)際上是一個(gè)鏈表散列的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

從上圖中可以看出，HashMap底層就是一個(gè)數(shù)組結(jié)構(gòu)，數(shù)組中的每一項(xiàng)又是一個(gè)鏈表。當(dāng)新建一個(gè)HashMap的時(shí)候，就會(huì)初始化一個(gè)數(shù)組。

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=">可以看出，Node就是數(shù)組中的元素，每個(gè) Map.Entry 其實(shí)就是一個(gè)key-value對，它持有一個(gè)指向下一個(gè)元素的引用，這就構(gòu)成了鏈表 2、HashMap實(shí)現(xiàn)存儲(chǔ)和讀取1）存儲(chǔ)/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with key, or
 *         null if there was no mapping for key.
 *         (A null return can also indicate that the map
 *         previously associated null with key.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
} 根據(jù)hash值得到這個(gè)元素在數(shù)組中的位置（即下標(biāo)），如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個(gè)位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上。/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 我們可以看到在hashMap中要找到某個(gè)元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置。如何計(jì)算這個(gè)位置就是hash算法。前面的說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們希望這個(gè)HashMap里面的元素位置盡量的分布均勻些。盡量使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)，那么當(dāng)我們用hash算法求得這個(gè)位置時(shí)，馬上就可以知道對應(yīng)位置的元素都是我們要的，而不用再去遍歷鏈表，這就大大優(yōu)化了查詢效率。HashMap 在底層將 key-value 當(dāng)成一個(gè)整體進(jìn)行處理，這個(gè)整體就是一個(gè) Node 對象。HashMap 底層采用一個(gè) Node[] 數(shù)組來保存所有的 key-value 對，當(dāng)需要存儲(chǔ)一個(gè) Node 對象時(shí)，會(huì)根據(jù)hash算法來決定其在數(shù)組中的存儲(chǔ)位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲(chǔ)位置；當(dāng)需要取出一個(gè)Entry時(shí)，也會(huì)根據(jù)hash算法找到其在數(shù)組中的存儲(chǔ)位置，再根據(jù)equals方法從該位置上的鏈表中取出該Node。3、HashMap的resize    當(dāng)hashmap的元素越來越多的時(shí)候，碰撞的概率就越來越高（因?yàn)閿?shù)組的長度是固定的），所以為了提高查詢的效率，就要對hashMap的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中，所以這是一個(gè)通用的操作，類似均攤。hashmap擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，就是resize。    那么hashmap什么時(shí)候擴(kuò)容？當(dāng)hashmap中的元素個(gè)數(shù)超過數(shù)組大小*loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75，也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)hashmap中元素個(gè)數(shù)超過16*0.75=12的時(shí)候，就把數(shù)組的大小擴(kuò)展為2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在新數(shù)組中的位置，放進(jìn)去，就是resize?？偨Y(jié)：HashMap的實(shí)現(xiàn)原理：    1、實(shí)現(xiàn)key的hashCode重新hash計(jì)算出當(dāng)前對象的元素在數(shù)組中的下標(biāo)。    2、存儲(chǔ)時(shí)，如果出現(xiàn)hash值相同的key,此時(shí)有兩種情況。（1）如果key相同，則覆蓋原始值；（2）如果key不同（出現(xiàn)沖突），則將當(dāng)前的key-value放入鏈表中    3、獲取時(shí)，直接找hash值對應(yīng)的下標(biāo)，在進(jìn)一步判斷key是否相同，從而找到對應(yīng)值。    4、理解以上過程就不難明白HashMap是如何解決hash沖突的問題，核心就是使用了數(shù)組的存儲(chǔ)方式，然后將沖突的key的對象放入鏈表中，一旦發(fā)現(xiàn)沖突就在鏈表中做進(jìn)一步的對比。

關(guān)于Java中HashMap的實(shí)現(xiàn)原理是什么就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。