1 . 讲一下hashmap的数据结构
HashMap
是一种基于哈希表实现的数据结构,通常用于关联键值对,其中键是唯一的,而值可以重复。在Java中,HashMap
是java.util.Map
接口的一个实现,它提供了快速的查找、插入和删除操作。
数据结构
HashMap
的核心结构包括以下组成部分:
-
数组:
HashMap
的底层是一个数组,这个数组的每个位置(通常称为“桶”或“槽”)可以存放一个或多个键值对。数组的大小通常是2的幂,以便能够高效地进行哈希值到数组索引的转换。 -
链表或红黑树:在数组的每个位置,如果多个键的哈希值映射到同一个数组索引上(这种情况称为哈希冲突),那么这些键值对会被组织成一个链表或者在某些情况下是红黑树。从Java 8开始,当链表中的节点超过一定阈值(默认为8)且数组达到最小大小(默认为64),链表会转换为红黑树,以提高查找效率。
-
节点(Node):每个键值对被封装在一个节点对象中,这个对象包含了键、值、哈希码和指向下一个节点的引用。在Java 8中,为了支持链表和红黑树的转换,引入了更复杂的节点类型,如
TreeNode
。
工作原理
-
哈希函数:当插入一个新的键值对时,首先会计算键的哈希码,这通常由键对象的
hashCode()
方法提供。然后,这个哈希码经过一定的运算(如按位与运算)被转换为数组索引。 -
冲突解决:如果两个或更多键的哈希值映射到同一个索引,它们会被添加到该索引处的链表或红黑树中。
-
查找:当需要查找一个键时,首先计算其哈希码并找到相应的数组索引。然后遍历该位置上的链表或红黑树,使用
equals()
方法比较键,直到找到匹配的键为止。 -
调整大小(Resize):当
HashMap
中的元素数量超过了其容量乘以加载因子(默认为0.75)时,HashMap
会自动调整其大小(通常增加为两倍),并将所有元素重新散列到新的数组中。这个过程称为“rehashing”。