一、HashMap简介
HashMap是Java集合框架的一部分,它提供了一种存储键值对的方式。它是一种基于哈希表的实现,可以提供快速的插入、查找和删除操作。
所有的集合类都实现了Map接口,而HashMap就是Map接口的一个基本实现。在HashMap中,每个键对应一个值。
二、HashMap数据结构
HashMap由数组和链表结构组成。具体来说,它由Entry对象数组和LinkedList对象组成。
Entry是HashMap的一个内部类,它存储了键值对。每个Entry对象包含了一个键对象和一个值对象。LinkedList则是Java提供的标准链表实现,它用于解决哈希冲突的问题。
static class Entryimplements 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指向。
哈希表的查找速度非常快,但是它会浪费一定的空间。因为哈希表的大小是预先分配的,因此如果哈希表中的元素比较少时也需要占用一定的空间。调整哈希表的大小可以解决这个问题。