Tag: hashmap - Enjoy it

首先看一下Map家族四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap。

下面我们主要解读HashMap，结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入解读HashMap的工作原理。

从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：

引入了红黑树是因为它查找、插入、删除的平均时间复杂度为O(log(n))。这是因为当产生hash碰撞时，数据会挂载（尾插），形成链表。链表空间上不连续，逻辑上连续，增删元素快，只需处理节点间的引用，时间复杂度为O(1)，查询慢，需要遍历所有节...

查看全文

HashMap	说明
底层结构	1. JDK1.8之前：数组+链表 2. JDK1.8：数组+链表/红黑树链表与红黑树之间的转换：链表->红黑树：链表长度大于等于8且数组长度（hash桶）大于等于64的时候红黑树->链表：红黑树的节点数量小于等于6的时候退化为链表
元素特性	key、value可以为null，只能有一个key为null的键值对，允许有多个value为null的键值对
hash桶的数量	默认16，加载因子默认0.75（HashMap也许是按照lazy-...

HashMap

说明

底层结构

1. JDK1.8之前：数组+链表
2. JDK1.8：数组+链表/红黑树
链表与红黑树之间的转换：
链表->红黑树：链表长度大于等于8且数组长度（hash桶）大于等于64的时候
红黑树->链表：红黑树的节点数量小于等于6的时候退化为链表

元素特性

key、value可以为null，只能有一个key为null的键值对，允许有多个value为null的键值对

hash桶的数量

默认16，加载因子默认0.75（HashMap也许是按照lazy-...