深入理解Java HashMap实现原理

小蓝 • 2024-12-09 16:30 • 编程

一、HashMap简介

HashMap是Java集合框架的一部分，它提供了一种存储键值对的方式。它是一种基于哈希表的实现，可以提供快速的插入、查找和删除操作。

所有的集合类都实现了Map接口，而HashMap就是Map接口的一个基本实现。在HashMap中，每个键对应一个值。

二、HashMap数据结构

HashMap由数组和链表结构组成。具体来说，它由Entry对象数组和LinkedList对象组成。

Entry是HashMap的一个内部类，它存储了键值对。每个Entry对象包含了一个键对象和一个值对象。LinkedList则是Java提供的标准链表实现，它用于解决哈希冲突的问题。

    static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        int hash;
    }

三、哈希冲突解决方法

当哈希表中出现相同的哈希值时，需要解决冲突。HashMap使用链表法解决哈希冲突的问题。

当多个Entry对象的哈希值相等时，它们会被组织成一个链表结构，链表中的每个元素都包含引用到下一个元素的指针。这样，当发生哈希冲突时，新的Entry对象可以插入到链表中，而不会覆盖原来的Entry对象。

四、HashMap扩容机制

HashMap的扩容机制是在数组大小超过了负载因子*当前数组大小时触发。负载因子默认为0.75，也就是说当数组中的元素达到了数组大小的0.75倍时，就触发扩容。

扩容的过程中，会新创建一个Entry对象数组，并将原数组中的所有元素重新分布到新数组中。这个过程的时间复杂度是O(N)，需要遍历原数组中的所有元素。因此，较大的初始容量和较小的负载因子可以减少扩容的次数，提高HashMap的效率。

    final Entry[] resize() {
        ...
        Entry[] newTab = new Entry[newCap];
        ...
        // Re-hash the contents of the old table into the new table
        for (int j = 0; j < oldCap; ++j) {
            Entry e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else {
                    // 重新分配每个Entry对象的next指向
                    Entry loHead = null, loTail = null;
                    Entry hiHead = null, hiTail = null;
                    Entry next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    ...
                }
            }
        }
        return newTab;
    }

五、HashMap实现原理总结

HashMap通过两个基本的数据结构——数组和链表来实现快速存储、查找和删除操作。在存储键值对时，HashMap会根据键对象的hashCode值将其映射到数组中的一个位置。当出现哈希冲突时，多个Entry对象会组织为一个链表以便于存储和查找。在扩容时，HashMap会重新分配原有Entry对象到新的数组中，同时重新分布每个Entry对象的next指向。

哈希表的查找速度非常快，但是它会浪费一定的空间。因为哈希表的大小是预先分配的，因此如果哈希表中的元素比较少时也需要占用一定的空间。调整哈希表的大小可以解决这个问题。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/227514.html