HashMap的详细解读

人不走空

发布于 2024-02-20 19:30:04

740

发布于 2024-02-20 19:30:04

文章被收录于专栏：学习与分享学习与分享

HashMap是Java语言中的一个重要数据结构，它实现了Map接口，允许我们存储键值对，并且可以根据键直接访问对应的值。

特性

键值对存储：HashMap存储的是键值对数据，可以方便的通过键来获取值。
无序：HashMap中的元素没有顺序，每次输出的顺序都可能不一样。这是因为HashMap内部是通过哈希表来实现的，元素存储在哈希表中，其位置取决于键的哈希值。
允许null键和null值：HashMap允许一个null键和一个null值。
扩容：当HashMap中的元素数量达到一定的阈值（默认是桶(bucket)的个数，每个桶是一个链表或者红黑树）时，会进行扩容，扩容会导致原有的数据重新计算哈希值并重新放置

HashMap的工作原理

HashMap的工作原理主要涉及以下几个部分：

哈希函数：当我们将键值对插入到HashMap中时，HashMap会使用哈希函数（hash function）将键（key）转换成一个哈希码（hash code），这个哈希码用来确定键值对应该放在哪个桶（bucket）中。
桶和链表：在HashMap中，每个桶都是一个链表，链表中的每个节点都包含一个键值对。如果多个键哈希到同一个桶，那么这些键值对就会在链表中顺序存储。
扩容和再哈希：当某个桶中的链表长度超过一个阈值（例如8）时，HashMap会将这个桶拆分成两个或更多的桶，这个过程就叫做扩容。扩容会使得HashMap的内部数据结构发生变化，可能会导致查询性能下降。
红黑树：当某个桶中的链表长度超过一定阈值（例如16）时，链表会转化成红黑树以提高查询效率。

源码

public class HashMap<K,V> extends AbstractMap<K,V>  
    implements Map<K,V>, Cloneable, Serializable {  
  
    // 其他常量  
  
    /**  
     * The default initial capacity - MUST be a power of two.  
     */  
    static final int DEFAULT_INITIAL_CAPACITY = 16;  
  
    /**  
     * The load factor used when none specified in constructor.  
     */  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
  
    /**  
     * The table, resized as necessary. Length MUST Always be a power of two.  
     */  
    transient Node<K,V>[] table;  
  
    /**  
     * The number of key-value mappings contained in this map.  
     */  
    transient int size;  
  
    /**  
     * The next size value at which to resize (capacity * load factor).  
     */  
    transient int threshold;  
  
    /**  
     * The load factor for the hash table.  When the capacity is multiplied by  
     * this factor, it is incremented.  
     */  
    transient float loadFactor;  
  
    // 其他变量和方法  
}

其中，HashMap的核心是它的哈希表（由table数组实现），每个元素都是一个Node对象，其中包含键值对。HashMap还维护了一些其他变量，如size（映射数量）、threshold（下一次扩容的阈值）和loadFactor（哈希表的加载因子）。

HashMap的主要方法包括：构造函数、put（插入键值对）、get（获取键对应的值）、remove（删除键值对）、isEmpty（判断是否为空）等。其中，put和get方法是HashMap中最常用的方法，它们的实现涉及到哈希表的查找和插入操作。以下是put方法的源码：

public V put(K key, V value) {  
    return putVal(hash(key), key, value, false, true);  
}  
  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  
    Node<K,V>[] tab; Node<K,V> p; int n, i;  
    if ((tab = table) == null || (n = tab.length) == 0)  
        n = (tab = resize()).length;  
    if ((p = tab[i = (n - 1) & hash]) == null) { // ①如果哈希表为空，将当前元素插入到第一个位置。p为null。则直接在第一个位置插入元素。同时n++。  
        tab[i] = new Node<>(hash, key, value, null); // 创建新的节点插入到哈希表中。同时n++。如果超过阈值，则进行扩容。并重新计算哈希值和位置。并将元素插入到新的位置中。同时n++。如果超过阈值，则进行扩容。并重新计算哈希值和位置。
}}

如果哈希表已经满了，那么会进行扩容，即创建一个新的哈希表，大小是原来的两倍，并将原来哈希表中的所有元素重新插入到新的哈希表中。扩容会导致性能的损失，因为每次插入操作都需要重新计算元素的哈希值和位置。因此，在设计HashMap时，需要考虑哈希表的大小和加载因子，以平衡性能和内存使用。

在插入元素时，如果哈希表中已经存在相同的哈希值，那么会进行冲突处理。HashMap采用链表或红黑树来处理冲突。当冲突发生时，会将当前元素插入到链表的尾部或红黑树的叶节点上。当链表的长度超过一定阈值（如8）时，会将链表转换为红黑树，以提高查询效率。

在查询元素时，HashMap会根据给定的键计算出哈希值，并找到对应的桶。然后，在该桶中查找链表或红黑树，直到找到对应的元素或到达链表的尾部或红黑树的叶节点。如果找不到指定的元素，则返回null。

总之，HashMap是一种高效的键值对存储数据结构，通过哈希表实现了O(1)时间复杂度的插入、删除和查询操作。但是，由于哈希表的不确定性，HashMap不支持线程安全。如果需要线程安全，可以使用ConcurrentHashMap或者通过Collections.synchronizedMap方法将Map包装为线程安全。

除了基本的操作，HashMap还提供了其他一些有用的方法，例如：