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

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

一、Java中的HashCode 和equals

• 關于hashcode

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

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

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

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

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

• 關于equals

    1、equals 和 ==

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

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

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

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

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

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

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

1、HashMap概述

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

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

從上圖中可以看出，HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表。當新建一個HashMap的時候，就會初始化一個數(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ù)組中的元素，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用，這就構(gòu)成了鏈表 2、HashMap實現(xiàn)存儲和讀取1）存儲/**
 * 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值得到這個元素在數(shù)組中的位置（即下標），如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數(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中要找到某個元素，需要根據(jù)key的hash值來求得對應數(shù)組中的位置。如何計算這個位置就是hash算法。前面的說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們希望這個HashMap里面的元素位置盡量的分布均勻些。盡量使得每個位置上的元素數(shù)量只有一個，那么當我們用hash算法求得這個位置時，馬上就可以知道對應位置的元素都是我們要的，而不用再去遍歷鏈表，這就大大優(yōu)化了查詢效率。HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Node 對象。HashMap 底層采用一個 Node[] 數(shù)組來保存所有的 key-value 對，當需要存儲一個 Node 對象時，會根據(jù)hash算法來決定其在數(shù)組中的存儲位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當需要取出一個Entry時，也會根據(jù)hash算法找到其在數(shù)組中的存儲位置，再根據(jù)equals方法從該位置上的鏈表中取出該Node。3、HashMap的resize    當hashmap的元素越來越多的時候，碰撞的概率就越來越高（因為數(shù)組的長度是固定的），所以為了提高查詢的效率，就要對hashMap的數(shù)組進行擴容，數(shù)組擴容這個操作也會出現(xiàn)在ArrayList中，所以這是一個通用的操作，類似均攤。hashmap擴容之后，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進去，就是resize。    那么hashmap什么時候擴容？當hashmap中的元素個數(shù)超過數(shù)組大小*loadFactor時，就會進行數(shù)組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數(shù)組大小為16，那么當hashmap中元素個數(shù)超過16*0.75=12的時候，就把數(shù)組的大小擴展為2*16=32，即擴大一倍，然后重新計算每個元素在新數(shù)組中的位置，放進去，就是resize。總結(jié)：HashMap的實現(xiàn)原理：    1、實現(xiàn)key的hashCode重新hash計算出當前對象的元素在數(shù)組中的下標。    2、存儲時，如果出現(xiàn)hash值相同的key,此時有兩種情況。（1）如果key相同，則覆蓋原始值；（2）如果key不同（出現(xiàn)沖突），則將當前的key-value放入鏈表中    3、獲取時，直接找hash值對應的下標，在進一步判斷key是否相同，從而找到對應值。    4、理解以上過程就不難明白HashMap是如何解決hash沖突的問題，核心就是使用了數(shù)組的存儲方式，然后將沖突的key的對象放入鏈表中，一旦發(fā)現(xiàn)沖突就在鏈表中做進一步的對比。

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