【Java基础】深入HashMap

我不是女神ヾ 2022-07-17 04:14 193阅读 0赞

HashMap 是数组\+ 链表的组合体，底层结构其实就是一个数组结构，数组中的每一项又是一个链表，当新创建一个HashMap的时候，就初始化一个数组。如下图所示:

(**[盗图一张][Link 1])**

![Center][]

**HahMap的存取:**

**Put**： 先根据key的hashcode重新计算hash值，根据hash值得到这个元素在数组中的下标位置，如果这个位置已经存放其他元素，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。

<pre name="code" class="java">public V put(K key, V value) {  
        // HashMap允许存放null键和null值。  
        // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  
        if (key == null)  
            return putForNullKey(value);  
        // 根据key的keyCode重新计算hash值。  
        int hash = hash(key.hashCode());  
        // 搜索指定hash值在对应table中的索引。  
        int i = indexFor(hash, table.length);  
        // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        // 如果i索引处的Entry为null，表明此处还没有Entry。  
        modCount++;  
        // 将key、value添加到i索引处。  
        addEntry(hash, key, value, i);  
        return null;  
    }

<pre name="code" class="java">void addEntry(int hash, K key, V value, int bucketIndex) {  
        // 获取指定 bucketIndex 索引处的 Entry   
        Entry<K,V> e = table[bucketIndex];  
        // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
        // 如果 Map 中的 key-value 对的数量超过了极限  
        if (size++ >= threshold)  
        // 把 table 对象的长度扩充到原来的2倍。  
            resize(2 * table.length);  
    }

在往HashMap中put元素的时候，首先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，**新加入的放在链头**，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是HashMap 提供的一个包访问权限的方法.

**get**： 需要根据key的hash值得到对应数组中的位置，就可以知道这个元素是不是我们想要的，而不用去遍历链表，大大优化了查询的效率

public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            //先定位到数组元素，再遍历该元素处的链表
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e.value;
            }
            return null;
    }

private V putForNullKey(V value) {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }
     
        private V getForNullKey() {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }

从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

**HashMap如何解决冲突？**

Java中hashMap用链地址法来解决;还有开放地址法,尽可能延长寻址时间.

**HashMap扩容？**

HashMap 有三个常量： 默认的容器大小是16，最大长度是2的30次方，loadfactor默认是0.75扩充的临界值是16\*0.75=12  
扩充条件：当hashmap中的元素个数超过loadfactor时，就会进行数组扩容，loadfactor的默认值为0.75，也就是说默认情况下，数组大小为16。当hashmap中的元素个数超过16\*0.75=12 的时候，就会把数组大小扩展为2\*16 = 32，即扩大一倍，然后重新计算每个元素在数组中的位置;

缺点:在数据量大的情况下,成倍扩容会撑爆CPU.

**ConcurrentHashMap?**

在JDK1.5中,新增加了concurrent并发包,ConcurrentHashMap就是其中的线程安全集合类.它的锁分离技术,大大提高了效率和性能. 每个hash区间使用的锁是ReentrantLock

在[ConcurrentHashMap][]中，就是把Map分成了N个Segment，put和get的时候，都是现根据key.hashCode()算出放到哪个 Segment中.

![Center 1][]

ConcurrentHashMap中对这个数据结构，针对并发稍微做了一点调整。它把区间按照concurrentLevel，分成了若干个segment。默认情况下内部按并发级别为16来创建。对于每个segment的容量，默认情况也是16。concurrentLevel和每个segment的初始容量都是可以通过构造函数设定的。

[Link 1]: http://blog.csdn.net/qa962839575/article/details/44889553
[Center]: /images/20220717/d9748903730b436e9d974c554841fcb6.png
[ConcurrentHashMap]: http://www.cnblogs.com/yydcdut/p/3959815.html
[Center 1]: /images/20220717/38a7dd1b081146d1906cc5c76e0f2314.png