【Java集合源码剖析】HashMap源码剖析

HashMap简介

HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

HashMap是非线程安全的,只是用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆。

HashMap源码剖析

HashMap的源码如下(加入了比较详细的注释):

  1. package java.util;
  2. import java.io.*;
  3. public class HashMap<K,V>
  4. extends AbstractMap<K,V>
  5. implements Map<K,V>, Cloneable, Serializable
  6. {
  7. // 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂。
  8. static final int DEFAULT_INITIAL_CAPACITY = 16;
  9. // 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换)
  10. static final int MAXIMUM_CAPACITY = 1 << 30;
  11. // 默认加载因子为0.75
  12. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  13. // 存储数据的Entry数组,长度是2的幂。
  14. // HashMap采用链表法解决冲突,每一个Entry本质上是一个单向链表
  15. transient Entry[] table;
  16. // HashMap的底层数组中已用槽的数量
  17. transient int size;
  18. // HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)
  19. int threshold;
  20. // 加载因子实际大小
  21. final float loadFactor;
  22. // HashMap被改变的次数
  23. transient volatile int modCount;
  24. // 指定“容量大小”和“加载因子”的构造函数
  25. public HashMap(int initialCapacity, float loadFactor) {
  26. if (initialCapacity < 0)
  27. throw new IllegalArgumentException("Illegal initial capacity: " +
  28. initialCapacity);
  29. // HashMap的最大容量只能是MAXIMUM_CAPACITY
  30. if (initialCapacity > MAXIMUM_CAPACITY)
  31. initialCapacity = MAXIMUM_CAPACITY;
  32. //加载因此不能小于0
  33. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  34. throw new IllegalArgumentException("Illegal load factor: " +
  35. loadFactor);
  36. // 找出“大于initialCapacity”的最小的2的幂
  37. int capacity = 1;
  38. while (capacity < initialCapacity)
  39. capacity <<= 1;
  40. // 设置“加载因子”
  41. this.loadFactor = loadFactor;
  42. // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。
  43. threshold = (int)(capacity * loadFactor);
  44. // 创建Entry数组,用来保存数据
  45. table = new Entry[capacity];
  46. init();
  47. }
  48. // 指定“容量大小”的构造函数
  49. public HashMap(int initialCapacity) {
  50. this(initialCapacity, DEFAULT_LOAD_FACTOR);
  51. }
  52. // 默认构造函数。
  53. public HashMap() {
  54. // 设置“加载因子”为默认加载因子0.75
  55. this.loadFactor = DEFAULT_LOAD_FACTOR;
  56. // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。
  57. threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  58. // 创建Entry数组,用来保存数据
  59. table = new Entry[DEFAULT_INITIAL_CAPACITY];
  60. init();
  61. }
  62. // 包含“子Map”的构造函数
  63. public HashMap(Map<? extends K, ? extends V> m) {
  64. this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
  65. DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
  66. // 将m中的全部元素逐个添加到HashMap中
  67. putAllForCreate(m);
  68. }
  69. //求hash值的方法,重新计算hash值
  70. static int hash(int h) {
  71. h ^= (h >>> 20) ^ (h >>> 12);
  72. return h ^ (h >>> 7) ^ (h >>> 4);
  73. }
  74. // 返回h在数组中的索引值,这里用&代替取模,旨在提升效率
  75. // h & (length-1)保证返回值的小于length
  76. static int indexFor(int h, int length) {
  77. return h & (length-1);
  78. }
  79. public int size() {
  80. return size;
  81. }
  82. public boolean isEmpty() {
  83. return size == 0;
  84. }
  85. // 获取key对应的value
  86. public V get(Object key) {
  87. if (key == null)
  88. return getForNullKey();
  89. // 获取key的hash值
  90. int hash = hash(key.hashCode());
  91. // 在“该hash值对应的链表”上查找“键值等于key”的元素
  92. for (Entry<K,V> e = table[indexFor(hash, table.length)];
  93. e != null;
  94. e = e.next) {
  95. Object k;
  96. //判断key是否相同
  97. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  98. return e.value;
  99. }
  100. //没找到则返回null
  101. return null;
  102. }
  103. // 获取“key为null”的元素的值
  104. // HashMap将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置!
  105. private V getForNullKey() {
  106. for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  107. if (e.key == null)
  108. return e.value;
  109. }
  110. return null;
  111. }
  112. // HashMap是否包含key
  113. public boolean containsKey(Object key) {
  114. return getEntry(key) != null;
  115. }
  116. // 返回“键为key”的键值对
  117. final Entry<K,V> getEntry(Object key) {
  118. // 获取哈希值
  119. // HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值
  120. int hash = (key == null) ? 0 : hash(key.hashCode());
  121. // 在“该hash值对应的链表”上查找“键值等于key”的元素
  122. for (Entry<K,V> e = table[indexFor(hash, table.length)];
  123. e != null;
  124. e = e.next) {
  125. Object k;
  126. if (e.hash == hash &&
  127. ((k = e.key) == key || (key != null && key.equals(k))))
  128. return e;
  129. }
  130. return null;
  131. }
  132. // 将“key-value”添加到HashMap中
  133. public V put(K key, V value) {
  134. // 若“key为null”,则将该键值对添加到table[0]中。
  135. if (key == null)
  136. return putForNullKey(value);
  137. // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。
  138. int hash = hash(key.hashCode());
  139. int i = indexFor(hash, table.length);
  140. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  141. Object k;
  142. // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
  143. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  144. V oldValue = e.value;
  145. e.value = value;
  146. e.recordAccess(this);
  147. return oldValue;
  148. }
  149. }
  150. // 若“该key”对应的键值对不存在,则将“key-value”添加到table中
  151. modCount++;
  152. //将key-value添加到table[i]处
  153. addEntry(hash, key, value, i);
  154. return null;
  155. }
  156. // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置
  157. private V putForNullKey(V value) {
  158. for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  159. if (e.key == null) {
  160. V oldValue = e.value;
  161. e.value = value;
  162. e.recordAccess(this);
  163. return oldValue;
  164. }
  165. }
  166. // 如果没有存在key为null的键值对,则直接题阿见到table[0]处!
  167. modCount++;
  168. addEntry(0, null, value, 0);
  169. return null;
  170. }
  171. // 创建HashMap对应的“添加方法”,
  172. // 它和put()不同。putForCreate()是内部方法,它被构造函数等调用,用来创建HashMap
  173. // 而put()是对外提供的往HashMap中添加元素的方法。
  174. private void putForCreate(K key, V value) {
  175. int hash = (key == null) ? 0 : hash(key.hashCode());
  176. int i = indexFor(hash, table.length);
  177. // 若该HashMap表中存在“键值等于key”的元素,则替换该元素的value值
  178. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  179. Object k;
  180. if (e.hash == hash &&
  181. ((k = e.key) == key || (key != null && key.equals(k)))) {
  182. e.value = value;
  183. return;
  184. }
  185. }
  186. // 若该HashMap表中不存在“键值等于key”的元素,则将该key-value添加到HashMap中
  187. createEntry(hash, key, value, i);
  188. }
  189. // 将“m”中的全部元素都添加到HashMap中。
  190. // 该方法被内部的构造HashMap的方法所调用。
  191. private void putAllForCreate(Map<? extends K, ? extends V> m) {
  192. // 利用迭代器将元素逐个添加到HashMap中
  193. for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
  194. Map.Entry<? extends K, ? extends V> e = i.next();
  195. putForCreate(e.getKey(), e.getValue());
  196. }
  197. }
  198. // 重新调整HashMap的大小,newCapacity是调整后的容量
  199. void resize(int newCapacity) {
  200. Entry[] oldTable = table;
  201. int oldCapacity = oldTable.length;
  202. //如果就容量已经达到了最大值,则不能再扩容,直接返回
  203. if (oldCapacity == MAXIMUM_CAPACITY) {
  204. threshold = Integer.MAX_VALUE;
  205. return;
  206. }
  207. // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中,
  208. // 然后,将“新HashMap”赋值给“旧HashMap”。
  209. Entry[] newTable = new Entry[newCapacity];
  210. transfer(newTable);
  211. table = newTable;
  212. threshold = (int)(newCapacity * loadFactor);
  213. }
  214. // 将HashMap中的全部元素都添加到newTable中
  215. void transfer(Entry[] newTable) {
  216. Entry[] src = table;
  217. int newCapacity = newTable.length;
  218. for (int j = 0; j < src.length; j++) {
  219. Entry<K,V> e = src[j];
  220. if (e != null) {
  221. src[j] = null;
  222. do {
  223. Entry<K,V> next = e.next;
  224. int i = indexFor(e.hash, newCapacity);
  225. e.next = newTable[i];
  226. newTable[i] = e;
  227. e = next;
  228. } while (e != null);
  229. }
  230. }
  231. }
  232. // 将"m"的全部元素都添加到HashMap中
  233. public void putAll(Map<? extends K, ? extends V> m) {
  234. // 有效性判断
  235. int numKeysToBeAdded = m.size();
  236. if (numKeysToBeAdded == 0)
  237. return;
  238. // 计算容量是否足够,
  239. // 若“当前阀值容量 < 需要的容量”,则将容量x2。
  240. if (numKeysToBeAdded > threshold) {
  241. int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
  242. if (targetCapacity > MAXIMUM_CAPACITY)
  243. targetCapacity = MAXIMUM_CAPACITY;
  244. int newCapacity = table.length;
  245. while (newCapacity < targetCapacity)
  246. newCapacity <<= 1;
  247. if (newCapacity > table.length)
  248. resize(newCapacity);
  249. }
  250. // 通过迭代器,将“m”中的元素逐个添加到HashMap中。
  251. for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
  252. Map.Entry<? extends K, ? extends V> e = i.next();
  253. put(e.getKey(), e.getValue());
  254. }
  255. }
  256. // 删除“键为key”元素
  257. public V remove(Object key) {
  258. Entry<K,V> e = removeEntryForKey(key);
  259. return (e == null ? null : e.value);
  260. }
  261. // 删除“键为key”的元素
  262. final Entry<K,V> removeEntryForKey(Object key) {
  263. // 获取哈希值。若key为null,则哈希值为0;否则调用hash()进行计算
  264. int hash = (key == null) ? 0 : hash(key.hashCode());
  265. int i = indexFor(hash, table.length);
  266. Entry<K,V> prev = table[i];
  267. Entry<K,V> e = prev;
  268. // 删除链表中“键为key”的元素
  269. // 本质是“删除单向链表中的节点”
  270. while (e != null) {
  271. Entry<K,V> next = e.next;
  272. Object k;
  273. if (e.hash == hash &&
  274. ((k = e.key) == key || (key != null && key.equals(k)))) {
  275. modCount++;
  276. size--;
  277. if (prev == e)
  278. table[i] = next;
  279. else
  280. prev.next = next;
  281. e.recordRemoval(this);
  282. return e;
  283. }
  284. prev = e;
  285. e = next;
  286. }
  287. return e;
  288. }
  289. // 删除“键值对”
  290. final Entry<K,V> removeMapping(Object o) {
  291. if (!(o instanceof Map.Entry))
  292. return null;
  293. Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
  294. Object key = entry.getKey();
  295. int hash = (key == null) ? 0 : hash(key.hashCode());
  296. int i = indexFor(hash, table.length);
  297. Entry<K,V> prev = table[i];
  298. Entry<K,V> e = prev;
  299. // 删除链表中的“键值对e”
  300. // 本质是“删除单向链表中的节点”
  301. while (e != null) {
  302. Entry<K,V> next = e.next;
  303. if (e.hash == hash && e.equals(entry)) {
  304. modCount++;
  305. size--;
  306. if (prev == e)
  307. table[i] = next;
  308. else
  309. prev.next = next;
  310. e.recordRemoval(this);
  311. return e;
  312. }
  313. prev = e;
  314. e = next;
  315. }
  316. return e;
  317. }
  318. // 清空HashMap,将所有的元素设为null
  319. public void clear() {
  320. modCount++;
  321. Entry[] tab = table;
  322. for (int i = 0; i < tab.length; i++)
  323. tab[i] = null;
  324. size = 0;
  325. }
  326. // 是否包含“值为value”的元素
  327. public boolean containsValue(Object value) {
  328. // 若“value为null”,则调用containsNullValue()查找
  329. if (value == null)
  330. return containsNullValue();
  331. // 若“value不为null”,则查找HashMap中是否有值为value的节点。
  332. Entry[] tab = table;
  333. for (int i = 0; i < tab.length ; i++)
  334. for (Entry e = tab[i] ; e != null ; e = e.next)
  335. if (value.equals(e.value))
  336. return true;
  337. return false;
  338. }
  339. // 是否包含null值
  340. private boolean containsNullValue() {
  341. Entry[] tab = table;
  342. for (int i = 0; i < tab.length ; i++)
  343. for (Entry e = tab[i] ; e != null ; e = e.next)
  344. if (e.value == null)
  345. return true;
  346. return false;
  347. }
  348. // 克隆一个HashMap,并返回Object对象
  349. public Object clone() {
  350. HashMap<K,V> result = null;
  351. try {
  352. result = (HashMap<K,V>)super.clone();
  353. } catch (CloneNotSupportedException e) {
  354. // assert false;
  355. }
  356. result.table = new Entry[table.length];
  357. result.entrySet = null;
  358. result.modCount = 0;
  359. result.size = 0;
  360. result.init();
  361. // 调用putAllForCreate()将全部元素添加到HashMap中
  362. result.putAllForCreate(this);
  363. return result;
  364. }
  365. // Entry是单向链表。
  366. // 它是 “HashMap链式存储法”对应的链表。
  367. // 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
  368. static class Entry<K,V> implements Map.Entry<K,V> {
  369. final K key;
  370. V value;
  371. // 指向下一个节点
  372. Entry<K,V> next;
  373. final int hash;
  374. // 构造函数。
  375. // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
  376. Entry(int h, K k, V v, Entry<K,V> n) {
  377. value = v;
  378. next = n;
  379. key = k;
  380. hash = h;
  381. }
  382. public final K getKey() {
  383. return key;
  384. }
  385. public final V getValue() {
  386. return value;
  387. }
  388. public final V setValue(V newValue) {
  389. V oldValue = value;
  390. value = newValue;
  391. return oldValue;
  392. }
  393. // 判断两个Entry是否相等
  394. // 若两个Entry的“key”和“value”都相等,则返回true。
  395. // 否则,返回false
  396. public final boolean equals(Object o) {
  397. if (!(o instanceof Map.Entry))
  398. return false;
  399. Map.Entry e = (Map.Entry)o;
  400. Object k1 = getKey();
  401. Object k2 = e.getKey();
  402. if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  403. Object v1 = getValue();
  404. Object v2 = e.getValue();
  405. if (v1 == v2 || (v1 != null && v1.equals(v2)))
  406. return true;
  407. }
  408. return false;
  409. }
  410. // 实现hashCode()
  411. public final int hashCode() {
  412. return (key==null   ? 0 : key.hashCode()) ^
  413. (value==null ? 0 : value.hashCode());
  414. }
  415. public final String toString() {
  416. return getKey() + "=" + getValue();
  417. }
  418. // 当向HashMap中添加元素时,绘调用recordAccess()。
  419. // 这里不做任何处理
  420. void recordAccess(HashMap<K,V> m) {
  421. }
  422. // 当从HashMap中删除元素时,绘调用recordRemoval()。
  423. // 这里不做任何处理
  424. void recordRemoval(HashMap<K,V> m) {
  425. }
  426. }
  427. // 新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。
  428. void addEntry(int hash, K key, V value, int bucketIndex) {
  429. // 保存“bucketIndex”位置的值到“e”中
  430. Entry<K,V> e = table[bucketIndex];
  431. // 设置“bucketIndex”位置的元素为“新Entry”,
  432. // 设置“e”为“新Entry的下一个节点”
  433. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  434. // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小
  435. if (size++ >= threshold)
  436. resize(2 * table.length);
  437. }
  438. // 创建Entry。将“key-value”插入指定位置。
  439. void createEntry(int hash, K key, V value, int bucketIndex) {
  440. // 保存“bucketIndex”位置的值到“e”中
  441. Entry<K,V> e = table[bucketIndex];
  442. // 设置“bucketIndex”位置的元素为“新Entry”,
  443. // 设置“e”为“新Entry的下一个节点”
  444. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  445. size++;
  446. }
  447. // HashIterator是HashMap迭代器的抽象出来的父类,实现了公共了函数。
  448. // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
  449. private abstract class HashIterator<E> implements Iterator<E> {
  450. // 下一个元素
  451. Entry<K,V> next;
  452. // expectedModCount用于实现fast-fail机制。
  453. int expectedModCount;
  454. // 当前索引
  455. int index;
  456. // 当前元素
  457. Entry<K,V> current;
  458. HashIterator() {
  459. expectedModCount = modCount;
  460. if (size > 0) { // advance to first entry
  461. Entry[] t = table;
  462. // 将next指向table中第一个不为null的元素。
  463. // 这里利用了index的初始值为0,从0开始依次向后遍历,直到找到不为null的元素就退出循环。
  464. while (index < t.length && (next = t[index++]) == null)
  465. ;
  466. }
  467. }
  468. public final boolean hasNext() {
  469. return next != null;
  470. }
  471. // 获取下一个元素
  472. final Entry<K,V> nextEntry() {
  473. if (modCount != expectedModCount)
  474. throw new ConcurrentModificationException();
  475. Entry<K,V> e = next;
  476. if (e == null)
  477. throw new NoSuchElementException();
  478. // 注意!!!
  479. // 一个Entry就是一个单向链表
  480. // 若该Entry的下一个节点不为空,就将next指向下一个节点;
  481. // 否则,将next指向下一个链表(也是下一个Entry)的不为null的节点。
  482. if ((next = e.next) == null) {
  483. Entry[] t = table;
  484. while (index < t.length && (next = t[index++]) == null)
  485. ;
  486. }
  487. current = e;
  488. return e;
  489. }
  490. // 删除当前元素
  491. public void remove() {
  492. if (current == null)
  493. throw new IllegalStateException();
  494. if (modCount != expectedModCount)
  495. throw new ConcurrentModificationException();
  496. Object k = current.key;
  497. current = null;
  498. HashMap.this.removeEntryForKey(k);
  499. expectedModCount = modCount;
  500. }
  501. }
  502. // value的迭代器
  503. private final class ValueIterator extends HashIterator<V> {
  504. public V next() {
  505. return nextEntry().value;
  506. }
  507. }
  508. // key的迭代器
  509. private final class KeyIterator extends HashIterator<K> {
  510. public K next() {
  511. return nextEntry().getKey();
  512. }
  513. }
  514. // Entry的迭代器
  515. private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
  516. public Map.Entry<K,V> next() {
  517. return nextEntry();
  518. }
  519. }
  520. // 返回一个“key迭代器”
  521. Iterator<K> newKeyIterator()   {
  522. return new KeyIterator();
  523. }
  524. // 返回一个“value迭代器”
  525. Iterator<V> newValueIterator()   {
  526. return new ValueIterator();
  527. }
  528. // 返回一个“entry迭代器”
  529. Iterator<Map.Entry<K,V>> newEntryIterator()   {
  530. return new EntryIterator();
  531. }
  532. // HashMap的Entry对应的集合
  533. private transient Set<Map.Entry<K,V>> entrySet = null;
  534. // 返回“key的集合”,实际上返回一个“KeySet对象”
  535. public Set<K> keySet() {
  536. Set<K> ks = keySet;
  537. return (ks != null ? ks : (keySet = new KeySet()));
  538. }
  539. // Key对应的集合
  540. // KeySet继承于AbstractSet,说明该集合中没有重复的Key。
  541. private final class KeySet extends AbstractSet<K> {
  542. public Iterator<K> iterator() {
  543. return newKeyIterator();
  544. }
  545. public int size() {
  546. return size;
  547. }
  548. public boolean contains(Object o) {
  549. return containsKey(o);
  550. }
  551. public boolean remove(Object o) {
  552. return HashMap.this.removeEntryForKey(o) != null;
  553. }
  554. public void clear() {
  555. HashMap.this.clear();
  556. }
  557. }
  558. // 返回“value集合”,实际上返回的是一个Values对象
  559. public Collection<V> values() {
  560. Collection<V> vs = values;
  561. return (vs != null ? vs : (values = new Values()));
  562. }
  563. // “value集合”
  564. // Values继承于AbstractCollection,不同于“KeySet继承于AbstractSet”,
  565. // Values中的元素能够重复。因为不同的key可以指向相同的value。
  566. private final class Values extends AbstractCollection<V> {
  567. public Iterator<V> iterator() {
  568. return newValueIterator();
  569. }
  570. public int size() {
  571. return size;
  572. }
  573. public boolean contains(Object o) {
  574. return containsValue(o);
  575. }
  576. public void clear() {
  577. HashMap.this.clear();
  578. }
  579. }
  580. // 返回“HashMap的Entry集合”
  581. public Set<Map.Entry<K,V>> entrySet() {
  582. return entrySet0();
  583. }
  584. // 返回“HashMap的Entry集合”,它实际是返回一个EntrySet对象
  585. private Set<Map.Entry<K,V>> entrySet0() {
  586. Set<Map.Entry<K,V>> es = entrySet;
  587. return es != null ? es : (entrySet = new EntrySet());
  588. }
  589. // EntrySet对应的集合
  590. // EntrySet继承于AbstractSet,说明该集合中没有重复的EntrySet。
  591. private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
  592. public Iterator<Map.Entry<K,V>> iterator() {
  593. return newEntryIterator();
  594. }
  595. public boolean contains(Object o) {
  596. if (!(o instanceof Map.Entry))
  597. return false;
  598. Map.Entry<K,V> e = (Map.Entry<K,V>) o;
  599. Entry<K,V> candidate = getEntry(e.getKey());
  600. return candidate != null && candidate.equals(e);
  601. }
  602. public boolean remove(Object o) {
  603. return removeMapping(o) != null;
  604. }
  605. public int size() {
  606. return size;
  607. }
  608. public void clear() {
  609. HashMap.this.clear();
  610. }
  611. }
  612. // java.io.Serializable的写入函数
  613. // 将HashMap的“总的容量,实际容量,所有的Entry”都写入到输出流中
  614. private void writeObject(java.io.ObjectOutputStream s)
  615. throws IOException
  616. {
  617. Iterator<Map.Entry<K,V>> i =
  618. (size > 0) ? entrySet0().iterator() : null;
  619. // Write out the threshold, loadfactor, and any hidden stuff
  620. s.defaultWriteObject();
  621. // Write out number of buckets
  622. s.writeInt(table.length);
  623. // Write out size (number of Mappings)
  624. s.writeInt(size);
  625. // Write out keys and values (alternating)
  626. if (i != null) {
  627. while (i.hasNext()) {
  628. Map.Entry<K,V> e = i.next();
  629. s.writeObject(e.getKey());
  630. s.writeObject(e.getValue());
  631. }
  632. }
  633. }
  634. private static final long serialVersionUID = 362498820763181265L;
  635. // java.io.Serializable的读取函数:根据写入方式读出
  636. // 将HashMap的“总的容量,实际容量,所有的Entry”依次读出
  637. private void readObject(java.io.ObjectInputStream s)
  638. throws IOException, ClassNotFoundException
  639. {
  640. // Read in the threshold, loadfactor, and any hidden stuff
  641. s.defaultReadObject();
  642. // Read in number of buckets and allocate the bucket array;
  643. int numBuckets = s.readInt();
  644. table = new Entry[numBuckets];
  645. init();  // Give subclass a chance to do its thing.
  646. // Read in size (number of Mappings)
  647. int size = s.readInt();
  648. // Read the keys and values, and put the mappings in the HashMap
  649. for (int i=0; i<size; i++) {
  650. K key = (K) s.readObject();
  651. V value = (V) s.readObject();
  652. putForCreate(key, value);
  653. }
  654. }
  655. // 返回“HashMap总的容量”
  656. int   capacity()     { return table.length; }
  657. // 返回“HashMap的加载因子”
  658. float loadFactor()   { return loadFactor;   }
  659. }

几点总结

1、首先要清楚HashMap的存储结构,如下图所示:

【Java集合源码剖析】HashMap源码剖析

图中,紫色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。

2、首先看链表中节点的数据结构:

  1. // Entry是单向链表。
  2. // 它是 “HashMap链式存储法”对应的链表。
  3. // 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
  4. static class Entry<K,V> implements Map.Entry<K,V> {
  5. final K key;
  6. V value;
  7. // 指向下一个节点
  8. Entry<K,V> next;
  9. final int hash;
  10. // 构造函数。
  11. // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
  12. Entry(int h, K k, V v, Entry<K,V> n) {
  13. value = v;
  14. next = n;
  15. key = k;
  16. hash = h;
  17. }
  18. public final K getKey() {
  19. return key;
  20. }
  21. public final V getValue() {
  22. return value;
  23. }
  24. public final V setValue(V newValue) {
  25. V oldValue = value;
  26. value = newValue;
  27. return oldValue;
  28. }
  29. // 判断两个Entry是否相等
  30. // 若两个Entry的“key”和“value”都相等,则返回true。
  31. // 否则,返回false
  32. public final boolean equals(Object o) {
  33. if (!(o instanceof Map.Entry))
  34. return false;
  35. Map.Entry e = (Map.Entry)o;
  36. Object k1 = getKey();
  37. Object k2 = e.getKey();
  38. if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  39. Object v1 = getValue();
  40. Object v2 = e.getValue();
  41. if (v1 == v2 || (v1 != null && v1.equals(v2)))
  42. return true;
  43. }
  44. return false;
  45. }
  46. // 实现hashCode()
  47. public final int hashCode() {
  48. return (key==null   ? 0 : key.hashCode()) ^
  49. (value==null ? 0 : value.hashCode());
  50. }
  51. public final String toString() {
  52. return getKey() + "=" + getValue();
  53. }
  54. // 当向HashMap中添加元素时,绘调用recordAccess()。
  55. // 这里不做任何处理
  56. void recordAccess(HashMap<K,V> m) {
  57. }
  58. // 当从HashMap中删除元素时,绘调用recordRemoval()。
  59. // 这里不做任何处理
  60. void recordRemoval(HashMap<K,V> m) {
  61. }
  62. }

它的结构元素除了key、value、hash外,还有next,next指向下一个节点。另外,这里覆写了equals和hashCode方法来保证键值对的独一无二。

3、HashMap共有四个构造方法。构造方法中提到了两个很重要的参数:初始容量和加载因子。这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中槽的数量(即哈希数组的长度),初始容量是创建哈希表时的容量(从构造函数中可以看出,如果不指明,则默认为16),加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 resize 操作(即扩容)。

下面说下加载因子,如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。

另外,无论我们指定的容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方

4、HashMap中key和value都允许为null。

5、要重点分析下HashMap中用的最多的两个方法put和get。先从比较简单的get方法着手,源码如下:

  1. // 获取key对应的value
  2. public V get(Object key) {
  3. if (key == null)
  4. return getForNullKey();
  5. // 获取key的hash值
  6. int hash = hash(key.hashCode());
  7. // 在“该hash值对应的链表”上查找“键值等于key”的元素
  8. for (Entry<K,V> e = table[indexFor(hash, table.length)];
  9. e != null;
  10. e = e.next) {
  11. Object k;
  12. /判断key是否相同
  13. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  14. return e.value;
  15. }
  16. 没找到则返回null
  17. return null;
  18. }
  19. // 获取“key为null”的元素的值
  20. // HashMap将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置!
  21. private V getForNullKey() {
  22. for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  23. if (e.key == null)
  24. return e.value;
  25. }
  26. return null;
  27. }

首先,如果key为null,则直接从哈希表的第一个位置table[0]对应的链表上查找。记住,key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。

如果key不为null,则先求的key的hash值,根据hash值找到在table中的索引,在该索引对应的单链表中查找是否有键值对的key与目标key相等,有就返回对应的value,没有则返回null。

put方法稍微复杂些,代码如下:

  1. // 将“key-value”添加到HashMap中
  2. public V put(K key, V value) {
  3. // 若“key为null”,则将该键值对添加到table[0]中。
  4. if (key == null)
  5. return putForNullKey(value);
  6. // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。
  7. int hash = hash(key.hashCode());
  8. int i = indexFor(hash, table.length);
  9. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  10. Object k;
  11. // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
  12. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  13. V oldValue = e.value;
  14. e.value = value;
  15. e.recordAccess(this);
  16. return oldValue;
  17. }
  18. }
  19. // 若“该key”对应的键值对不存在,则将“key-value”添加到table中
  20. modCount++;
  21. //将key-value添加到table[i]处
  22. addEntry(hash, key, value, i);
  23. return null;
  24. }

如果key为null,则将其添加到table[0]对应的链表中,putForNullKey的源码如下:

  1. // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置
  2. private V putForNullKey(V value) {
  3. for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  4. if (e.key == null) {
  5. V oldValue = e.value;
  6. e.value = value;
  7. e.recordAccess(this);
  8. return oldValue;
  9. }
  10. }
  11. // 如果没有存在key为null的键值对,则直接题阿见到table[0]处!
  12. modCount++;
  13. addEntry(0, null, value, 0);
  14. return null;
  15. }

如果key不为null,则同样先求出key的hash值,根据hash值得出在table中的索引,而后遍历对应的单链表,如果单链表中存在与目标key相等的键值对,则将新的value覆盖旧的value,比将旧的value返回,如果找不到与目标key相等的键值对,或者该单链表为空,则将该键值对插入到改单链表的头结点位置(每次新插入的节点都是放在头结点的位置),该操作是有addEntry方法实现的,它的源码如下:

  1. // 新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。
  2. void addEntry(int hash, K key, V value, int bucketIndex) {
  3. // 保存“bucketIndex”位置的值到“e”中
  4. Entry<K,V> e = table[bucketIndex];
  5. // 设置“bucketIndex”位置的元素为“新Entry”,
  6. // 设置“e”为“新Entry的下一个节点”
  7. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  8. // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小
  9. if (size++ >= threshold)
  10. resize(2 * table.length);
  11. }

注意这里倒数第三行的构造方法,将key-value键值对赋给table[bucketIndex],并将其next指向元素e,这便将key-value放到了头结点中,并将之前的头结点接在了它的后面。该方法也说明,每次put键值对的时候,总是将新的该键值对放在table[bucketIndex]处(即头结点处)。

两外注意最后两行代码,每次加入键值对时,都要判断当前已用的槽的数目是否大于等于阀值(容量*加载因子),如果大于等于,则进行扩容,将容量扩为原来容量的2倍。

6、关于扩容。上面我们看到了扩容的方法,resize方法,它的源码如下:

  1. // 重新调整HashMap的大小,newCapacity是调整后的单位
  2. void resize(int newCapacity) {
  3. Entry[] oldTable = table;
  4. int oldCapacity = oldTable.length;
  5. if (oldCapacity == MAXIMUM_CAPACITY) {
  6. threshold = Integer.MAX_VALUE;
  7. return;
  8. }
  9. // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中,
  10. // 然后,将“新HashMap”赋值给“旧HashMap”。
  11. Entry[] newTable = new Entry[newCapacity];
  12. transfer(newTable);
  13. table = newTable;
  14. threshold = (int)(newCapacity * loadFactor);
  15. }

很明显,是新建了一个HashMap的底层数组,而后调用transfer方法,将就HashMap的全部元素添加到新的HashMap中(要重新计算元素在新的数组中的索引位置)。transfer方法的源码如下:

  1. // 将HashMap中的全部元素都添加到newTable中
  2. void transfer(Entry[] newTable) {
  3. Entry[] src = table;
  4. int newCapacity = newTable.length;
  5. for (int j = 0; j < src.length; j++) {
  6. Entry<K,V> e = src[j];
  7. if (e != null) {
  8. src[j] = null;
  9. do {
  10. Entry<K,V> next = e.next;
  11. int i = indexFor(e.hash, newCapacity);
  12. e.next = newTable[i];
  13. newTable[i] = e;
  14. e = next;
  15. } while (e != null);
  16. }
  17. }
  18. }

很明显,扩容是一个相当耗时的操作,因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此,我们在用HashMap的时,最好能提前预估下HashMap中元素的个数,这样有助于提高HashMap的性能。

7、注意containsKey方法和containsValue方法。前者直接可以通过key的哈希值将搜索范围定位到指定索引对应的链表,而后者要对哈希数组的每个链表进行搜索。

8、我们重点来分析下求hash值和索引值的方法,这两个方法便是HashMap设计的最为核心的部分,二者结合能保证哈希表中的元素尽可能均匀地散列。

计算哈希值的方法如下:

  1. static int hash(int h) {
  2. h ^= (h >>> 20) ^ (h >>> 12);
  3. return h ^ (h >>> 7) ^ (h >>> 4);
  4. }

它只是一个数学公式,IDK这样设计对hash值的计算,自然有它的好处,至于为什么这样设计,我们这里不去追究,只要明白一点,用的位的操作使hash值的计算效率很高。

由hash值找到对应索引的方法如下:

  1. static int indexFor(int h, int length) {
  2. return h & (length-1);
  3. }

这个我们要重点说下,我们一般对哈希表的散列很自然地会想到用hash值对length取模(即除法散列法),Hashtable中也是这样实现的,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,效率很低,HashMap中则通过h&(length-1)的方法来代替取模,同样实现了均匀的散列,但效率要高很多,这也是HashMap对Hashtable的一个改进。

接下来,我们分析下为什么哈希表的容量一定要是2的整数次幂。首先,length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率;其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。

上一篇:背水一战 Windows 10 (93) - 选取器: FileOpenPicker, FolderPicker, FileSavePicker


下一篇:Java集合源码阅读之HashMap