Hashmap源码解析-总览&目录

HashMap:

它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。

HashMap最多只允许一条记录的键为null,允许多条记录的值为null。

HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

结构: 数组 + 链表, 链表长度达到8转化成红黑树

扩容: hashMap的容量达到threshold会触发扩容。扩容前后,哈希桶的长度一定会是2的次方, 这样在根据key的hash值寻找对应的哈希桶时,可以用位运算替代取余操作,更加高效。

Hashmap源码解析-与hashtable区别

HashMap是非线程安全的,HashTable是线程安全的。

Hashmap源码解析-get

get

查找过程和删除基本差不多, 找到返回节点,否则返回null

Hashmap源码解析-put

源码解析-put函数

Hashmap源码解析-remove

remove

1.找到待删除节点,也是分第一个节点就是,红黑树中找该节点,普通链表中找该节点

2.删除节点,分红黑树删除,头节点删除,中间节点删除(包括尾)

3.++modCount, –size

Hashmap源码解析-构造函数

系列目录

  1. 总览&目录
  2. 链表节点NODE
  3. 构造函数
  4. 扩容函数
  5. put
  6. remove
  7. get
  8. 遍历
  9. &hashtable

构造函数

构造函数:

默认构造函数什么都不做,只是将加载因子设为默认加载因子。

有初始值大小的构造函数,

​ 会将threshold设置为大于输入参数且最近的2的整数次幂的数,比如10,设置阈值16.

​ 即使有initialCapacity参数的构造,也是设置threshold,不会现在设置cap,如要设置cap就需要new资源了,而原理是在等真的插入的时候才去通过resize操作申请内存资源, 见resize.md,put.md

重点:

1.参数最大容量,默认的加载因子,加载因子,阈值

2.哈希桶, Node<K,V>[] table, 是Node数组, 存放链表, 长度初始化时为0, 之后是2的N次方

3.loadFactor和threshold的关系

4.tableSizeFor函数的原理, 见下面解析

Hashmap源码解析-扩容函数

系列目录

  1. 总览&目录
  2. 链表节点NODE
  3. 构造函数
  4. 扩容函数
  5. put
  6. remove
  7. get
  8. 遍历
  9. &hashtable

扩容函数

1.更新容量和阈值,

​ if cap>0, 不超过上限的情况下cap、thre都乘2

​ if cap=0, oldThr>0, 说明初始化的时候赋初始容量参数了,newCap=oldThr

​ if cap=0, oldthr=0, 直接重新初始化,cap=16,thre=12

2.更新哈希桶, 遍历原桶

​ if 只有一个节点,直接挪过去

​ if 链表有超过8个节点,是红黑树, 复杂, 再说todo

​ if 少于8个的链表,则可能挪到低位,也可能挪到高位,看它本身hash在新容量时应在哪里,代码中巧妙通过与oldCap & 的方式判断需改到高还是低,具体在代码注释中有

Hashmap源码解析-链表节点NODE

系列目录

  1. 总览&目录
  2. 链表节点NODE
  3. 构造函数
  4. 扩容函数
  5. put
  6. remove
  7. get
  8. 遍历
  9. &hashtable

链表节点NODE

重点:

1.单链表

2.hashCode()是将key的hashCode和value的hashCode异或得到

Hashmap源码解析-遍历

系列目录

  1. 总览&目录
  2. 链表节点NODE
  3. 构造函数
  4. 扩容函数
  5. put
  6. remove
  7. get
  8. 遍历
  9. &hashtable

遍历

1.Node implements Map.Entry

2.EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>>

3.迭代器HashIterator实现 expectedModCount = modCount 支持fastfail

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×