MyException - 我的异常网
当前位置:我的异常网» 综合 » java集合-HashMap源码剖析

java集合-HashMap源码剖析

www.MyException.Cn  网友分享于:2013-10-27  浏览:0次
java集合----HashMap源码剖析

HashMap简介

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

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

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

HashMap源码剖析

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

[java] view plain copy

  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的存储结构,如下图所示:

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

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

[java] view plain copy

  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方法着手,源码如下:

[java] view plain copy

  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方法稍微复杂些,代码如下:

[java] view plain copy

  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的源码如下:

[java] view plain copy

  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方法实现的,它的源码如下:

[java] view plain copy

  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方法,它的源码如下:

[java] view plain copy

  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方法的源码如下:

[java] view plain copy

  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设计的最为核心的部分,二者结合能保证哈希表中的元素尽可能均匀地散列。

计算哈希值的方法如下:

[java] view plain copy

  1. static int hash(int h) {

  2. h ^= (h >>> 20) ^ (h >>> 12);

  3. return h ^ (h >>> 7) ^ (h >>> 4);

  4. }

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

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

[java] view plain copy

  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值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。

转载于:http://blog.csdn.net/ns_code/article/details/36034955,谢谢

 

文章评论

不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
 程序员的样子
程序员的样子
程序员的鄙视链
程序员的鄙视链
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Java程序员必看电影
Java程序员必看电影
程序员必看的十大电影
程序员必看的十大电影
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
那些争议最大的编程观点
那些争议最大的编程观点
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
10个调试和排错的小建议
10个调试和排错的小建议
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
编程语言是女人
编程语言是女人
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员都该阅读的书
程序员都该阅读的书
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
我是如何打败拖延症的
我是如何打败拖延症的
我的丈夫是个程序员
我的丈夫是个程序员
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
鲜为人知的编程真相
鲜为人知的编程真相
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
如何成为一名黑客
如何成为一名黑客
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
漫画:程序员的工作
漫画:程序员的工作
每天工作4小时的程序员
每天工作4小时的程序员
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
老程序员的下场
老程序员的下场
旅行,写作,编程
旅行,写作,编程
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
代码女神横空出世
代码女神横空出世
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有