1. /*
  2. * @(#)HashMap.java 1.57 03/01/23
  3. *
  4. * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util;
  8. import java.io.*;
  9. /**
  10. * Hash table based implementation of the <tt>Map</tt> interface. This
  11. * implementation provides all of the optional map operations, and permits
  12. * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
  13. * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
  14. * unsynchronized and permits nulls.) This class makes no guarantees as to
  15. * the order of the map; in particular, it does not guarantee that the order
  16. * will remain constant over time.
  17. *
  18. * <p>This implementation provides constant-time performance for the basic
  19. * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
  20. * disperses the elements properly among the buckets. Iteration over
  21. * collection views requires time proportional to the "capacity" of the
  22. * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
  23. * of key-value mappings). Thus, it's very important not to set the initial
  24. * capacity too high (or the load factor too low) if iteration performance is
  25. * important.
  26. *
  27. * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
  28. * performance: <i>initial capacity</i> and <i>load factor</i>. The
  29. * <i>capacity</i> is the number of buckets in the hash table, and the initial
  30. * capacity is simply the capacity at the time the hash table is created. The
  31. * <i>load factor</i> is a measure of how full the hash table is allowed to
  32. * get before its capacity is automatically increased. When the number of
  33. * entries in the hash table exceeds the product of the load factor and the
  34. * current capacity, the capacity is roughly doubled by calling the
  35. * <tt>rehash</tt> method.
  36. *
  37. * <p>As a general rule, the default load factor (.75) offers a good tradeoff
  38. * between time and space costs. Higher values decrease the space overhead
  39. * but increase the lookup cost (reflected in most of the operations of the
  40. * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
  41. * expected number of entries in the map and its load factor should be taken
  42. * into account when setting its initial capacity, so as to minimize the
  43. * number of <tt>rehash</tt> operations. If the initial capacity is greater
  44. * than the maximum number of entries divided by the load factor, no
  45. * <tt>rehash</tt> operations will ever occur.
  46. *
  47. * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
  48. * creating it with a sufficiently large capacity will allow the mappings to
  49. * be stored more efficiently than letting it perform automatic rehashing as
  50. * needed to grow the table.
  51. *
  52. * <p><b>Note that this implementation is not synchronized.</b> If multiple
  53. * threads access this map concurrently, and at least one of the threads
  54. * modifies the map structurally, it <i>must</i> be synchronized externally.
  55. * (A structural modification is any operation that adds or deletes one or
  56. * more mappings; merely changing the value associated with a key that an
  57. * instance already contains is not a structural modification.) This is
  58. * typically accomplished by synchronizing on some object that naturally
  59. * encapsulates the map. If no such object exists, the map should be
  60. * "wrapped" using the <tt>Collections.synchronizedMap</tt> method. This is
  61. * best done at creation time, to prevent accidental unsynchronized access to
  62. * the map: <pre> Map m = Collections.synchronizedMap(new HashMap(...));
  63. * </pre>
  64. *
  65. * <p>The iterators returned by all of this class's "collection view methods"
  66. * are <i>fail-fast</i>: if the map is structurally modified at any time after
  67. * the iterator is created, in any way except through the iterator's own
  68. * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
  69. * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
  70. * modification, the iterator fails quickly and cleanly, rather than risking
  71. * arbitrary, non-deterministic behavior at an undetermined time in the
  72. * future.
  73. *
  74. * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  75. * as it is, generally speaking, impossible to make any hard guarantees in the
  76. * presence of unsynchronized concurrent modification. Fail-fast iterators
  77. * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  78. * Therefore, it would be wrong to write a program that depended on this
  79. * exception for its correctness: <i>the fail-fast behavior of iterators
  80. * should be used only to detect bugs.</i>
  81. *
  82. * <p>This class is a member of the
  83. * <a href="{@docRoot}/../guide/collections/index.html">
  84. * Java Collections Framework</a>.
  85. *
  86. * @author Doug Lea
  87. * @author Josh Bloch
  88. * @author Arthur van Hoff
  89. * @version 1.57, 01/23/03
  90. * @see Object#hashCode()
  91. * @see Collection
  92. * @see Map
  93. * @see TreeMap
  94. * @see Hashtable
  95. * @since 1.2
  96. */
  97. public class HashMap extends AbstractMap implements Map, Cloneable,
  98. Serializable
  99. {
  100. /**
  101. * The default initial capacity - MUST be a power of two.
  102. */
  103. static final int DEFAULT_INITIAL_CAPACITY = 16;
  104. /**
  105. * The maximum capacity, used if a higher value is implicitly specified
  106. * by either of the constructors with arguments.
  107. * MUST be a power of two <= 1<<30.
  108. */
  109. static final int MAXIMUM_CAPACITY = 1 << 30;
  110. /**
  111. * The load factor used when none specified in constructor.
  112. **/
  113. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  114. /**
  115. * The table, resized as necessary. Length MUST Always be a power of two.
  116. */
  117. transient Entry[] table;
  118. /**
  119. * The number of key-value mappings contained in this identity hash map.
  120. */
  121. transient int size;
  122. /**
  123. * The next size value at which to resize (capacity * load factor).
  124. * @serial
  125. */
  126. int threshold;
  127. /**
  128. * The load factor for the hash table.
  129. *
  130. * @serial
  131. */
  132. final float loadFactor;
  133. /**
  134. * The number of times this HashMap has been structurally modified
  135. * Structural modifications are those that change the number of mappings in
  136. * the HashMap or otherwise modify its internal structure (e.g.,
  137. * rehash). This field is used to make iterators on Collection-views of
  138. * the HashMap fail-fast. (See ConcurrentModificationException).
  139. */
  140. transient volatile int modCount;
  141. /**
  142. * Constructs an empty <tt>HashMap</tt> with the specified initial
  143. * capacity and load factor.
  144. *
  145. * @param initialCapacity The initial capacity.
  146. * @param loadFactor The load factor.
  147. * @throws IllegalArgumentException if the initial capacity is negative
  148. * or the load factor is nonpositive.
  149. */
  150. public HashMap(int initialCapacity, float loadFactor) {
  151. if (initialCapacity < 0)
  152. throw new IllegalArgumentException("Illegal initial capacity: " +
  153. initialCapacity);
  154. if (initialCapacity > MAXIMUM_CAPACITY)
  155. initialCapacity = MAXIMUM_CAPACITY;
  156. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  157. throw new IllegalArgumentException("Illegal load factor: " +
  158. loadFactor);
  159. // Find a power of 2 >= initialCapacity
  160. int capacity = 1;
  161. while (capacity < initialCapacity)
  162. capacity <<= 1;
  163. this.loadFactor = loadFactor;
  164. threshold = (int)(capacity * loadFactor);
  165. table = new Entry[capacity];
  166. init();
  167. }
  168. /**
  169. * Constructs an empty <tt>HashMap</tt> with the specified initial
  170. * capacity and the default load factor (0.75).
  171. *
  172. * @param initialCapacity the initial capacity.
  173. * @throws IllegalArgumentException if the initial capacity is negative.
  174. */
  175. public HashMap(int initialCapacity) {
  176. this(initialCapacity, DEFAULT_LOAD_FACTOR);
  177. }
  178. /**
  179. * Constructs an empty <tt>HashMap</tt> with the default initial capacity
  180. * (16) and the default load factor (0.75).
  181. */
  182. public HashMap() {
  183. this.loadFactor = DEFAULT_LOAD_FACTOR;
  184. threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  185. table = new Entry[DEFAULT_INITIAL_CAPACITY];
  186. init();
  187. }
  188. /**
  189. * Constructs a new <tt>HashMap</tt> with the same mappings as the
  190. * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
  191. * default load factor (0.75) and an initial capacity sufficient to
  192. * hold the mappings in the specified <tt>Map</tt>.
  193. *
  194. * @param m the map whose mappings are to be placed in this map.
  195. * @throws NullPointerException if the specified map is null.
  196. */
  197. public HashMap(Map m) {
  198. this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
  199. DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
  200. putAllForCreate(m);
  201. }
  202. // internal utilities
  203. /**
  204. * Initialization hook for subclasses. This method is called
  205. * in all constructors and pseudo-constructors (clone, readObject)
  206. * after HashMap has been initialized but before any entries have
  207. * been inserted. (In the absence of this method, readObject would
  208. * require explicit knowledge of subclasses.)
  209. */
  210. void init() {
  211. }
  212. /**
  213. * Value representing null keys inside tables.
  214. */
  215. static final Object NULL_KEY = new Object();
  216. /**
  217. * Returns internal representation for key. Use NULL_KEY if key is null.
  218. */
  219. static Object maskNull(Object key) {
  220. return (key == null ? NULL_KEY : key);
  221. }
  222. /**
  223. * Returns key represented by specified internal representation.
  224. */
  225. static Object unmaskNull(Object key) {
  226. return (key == NULL_KEY ? null : key);
  227. }
  228. /**
  229. * Returns a hash value for the specified object. In addition to
  230. * the object's own hashCode, this method applies a "supplemental
  231. * hash function," which defends against poor quality hash functions.
  232. * This is critical because HashMap uses power-of two length
  233. * hash tables.<p>
  234. *
  235. * The shift distances in this function were chosen as the result
  236. * of an automated search over the entire four-dimensional search space.
  237. */
  238. static int hash(Object x) {
  239. int h = x.hashCode();
  240. h += ~(h << 9);
  241. h ^= (h >>> 14);
  242. h += (h << 4);
  243. h ^= (h >>> 10);
  244. return h;
  245. }
  246. /**
  247. * Check for equality of non-null reference x and possibly-null y.
  248. */
  249. static boolean eq(Object x, Object y) {
  250. return x == y || x.equals(y);
  251. }
  252. /**
  253. * Returns index for hash code h.
  254. */
  255. static int indexFor(int h, int length) {
  256. return h & (length-1);
  257. }
  258. /**
  259. * Returns the number of key-value mappings in this map.
  260. *
  261. * @return the number of key-value mappings in this map.
  262. */
  263. public int size() {
  264. return size;
  265. }
  266. /**
  267. * Returns <tt>true</tt> if this map contains no key-value mappings.
  268. *
  269. * @return <tt>true</tt> if this map contains no key-value mappings.
  270. */
  271. public boolean isEmpty() {
  272. return size == 0;
  273. }
  274. /**
  275. * Returns the value to which the specified key is mapped in this identity
  276. * hash map, or <tt>null</tt> if the map contains no mapping for this key.
  277. * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
  278. * that the map contains no mapping for the key; it is also possible that
  279. * the map explicitly maps the key to <tt>null</tt>. The
  280. * <tt>containsKey</tt> method may be used to distinguish these two cases.
  281. *
  282. * @param key the key whose associated value is to be returned.
  283. * @return the value to which this map maps the specified key, or
  284. * <tt>null</tt> if the map contains no mapping for this key.
  285. * @see #put(Object, Object)
  286. */
  287. public Object get(Object key) {
  288. Object k = maskNull(key);
  289. int hash = hash(k);
  290. int i = indexFor(hash, table.length);
  291. Entry e = table[i];
  292. while (true) {
  293. if (e == null)
  294. return e;
  295. if (e.hash == hash && eq(k, e.key))
  296. return e.value;
  297. e = e.next;
  298. }
  299. }
  300. /**
  301. * Returns <tt>true</tt> if this map contains a mapping for the
  302. * specified key.
  303. *
  304. * @param key The key whose presence in this map is to be tested
  305. * @return <tt>true</tt> if this map contains a mapping for the specified
  306. * key.
  307. */
  308. public boolean containsKey(Object key) {
  309. Object k = maskNull(key);
  310. int hash = hash(k);
  311. int i = indexFor(hash, table.length);
  312. Entry e = table[i];
  313. while (e != null) {
  314. if (e.hash == hash && eq(k, e.key))
  315. return true;
  316. e = e.next;
  317. }
  318. return false;
  319. }
  320. /**
  321. * Returns the entry associated with the specified key in the
  322. * HashMap. Returns null if the HashMap contains no mapping
  323. * for this key.
  324. */
  325. Entry getEntry(Object key) {
  326. Object k = maskNull(key);
  327. int hash = hash(k);
  328. int i = indexFor(hash, table.length);
  329. Entry e = table[i];
  330. while (e != null && !(e.hash == hash && eq(k, e.key)))
  331. e = e.next;
  332. return e;
  333. }
  334. /**
  335. * Associates the specified value with the specified key in this map.
  336. * If the map previously contained a mapping for this key, the old
  337. * value is replaced.
  338. *
  339. * @param key key with which the specified value is to be associated.
  340. * @param value value to be associated with the specified key.
  341. * @return previous value associated with specified key, or <tt>null</tt>
  342. * if there was no mapping for key. A <tt>null</tt> return can
  343. * also indicate that the HashMap previously associated
  344. * <tt>null</tt> with the specified key.
  345. */
  346. public Object put(Object key, Object value) {
  347. Object k = maskNull(key);
  348. int hash = hash(k);
  349. int i = indexFor(hash, table.length);
  350. for (Entry e = table[i]; e != null; e = e.next) {
  351. if (e.hash == hash && eq(k, e.key)) {
  352. Object oldValue = e.value;
  353. e.value = value;
  354. e.recordAccess(this);
  355. return oldValue;
  356. }
  357. }
  358. modCount++;
  359. addEntry(hash, k, value, i);
  360. return null;
  361. }
  362. /**
  363. * This method is used instead of put by constructors and
  364. * pseudoconstructors (clone, readObject). It does not resize the table,
  365. * check for comodification, etc. It calls createEntry rather than
  366. * addEntry.
  367. */
  368. private void putForCreate(Object key, Object value) {
  369. Object k = maskNull(key);
  370. int hash = hash(k);
  371. int i = indexFor(hash, table.length);
  372. /**
  373. * Look for preexisting entry for key. This will never happen for
  374. * clone or deserialize. It will only happen for construction if the
  375. * input Map is a sorted map whose ordering is inconsistent w/ equals.
  376. */
  377. for (Entry e = table[i]; e != null; e = e.next) {
  378. if (e.hash == hash && eq(k, e.key)) {
  379. e.value = value;
  380. return;
  381. }
  382. }
  383. createEntry(hash, k, value, i);
  384. }
  385. void putAllForCreate(Map m) {
  386. for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) {
  387. Map.Entry e = (Map.Entry) i.next();
  388. putForCreate(e.getKey(), e.getValue());
  389. }
  390. }
  391. /**
  392. * Rehashes the contents of this map into a new array with a
  393. * larger capacity. This method is called automatically when the
  394. * number of keys in this map reaches its threshold.
  395. *
  396. * If current capacity is MAXIMUM_CAPACITY, this method does not
  397. * resize the map, but but sets threshold to Integer.MAX_VALUE.
  398. * This has the effect of preventing future calls.
  399. *
  400. * @param newCapacity the new capacity, MUST be a power of two;
  401. * must be greater than current capacity unless current
  402. * capacity is MAXIMUM_CAPACITY (in which case value
  403. * is irrelevant).
  404. */
  405. void resize(int newCapacity) {
  406. Entry[] oldTable = table;
  407. int oldCapacity = oldTable.length;
  408. if (oldCapacity == MAXIMUM_CAPACITY) {
  409. threshold = Integer.MAX_VALUE;
  410. return;
  411. }
  412. Entry[] newTable = new Entry[newCapacity];
  413. transfer(newTable);
  414. table = newTable;
  415. threshold = (int)(newCapacity * loadFactor);
  416. }
  417. /**
  418. * Transfer all entries from current table to newTable.
  419. */
  420. void transfer(Entry[] newTable) {
  421. Entry[] src = table;
  422. int newCapacity = newTable.length;
  423. for (int j = 0; j < src.length; j++) {
  424. Entry e = src[j];
  425. if (e != null) {
  426. src[j] = null;
  427. do {
  428. Entry next = e.next;
  429. int i = indexFor(e.hash, newCapacity);
  430. e.next = newTable[i];
  431. newTable[i] = e;
  432. e = next;
  433. } while (e != null);
  434. }
  435. }
  436. }
  437. /**
  438. * Copies all of the mappings from the specified map to this map
  439. * These mappings will replace any mappings that
  440. * this map had for any of the keys currently in the specified map.
  441. *
  442. * @param m mappings to be stored in this map.
  443. * @throws NullPointerException if the specified map is null.
  444. */
  445. public void putAll(Map m) {
  446. int numKeysToBeAdded = m.size();
  447. if (numKeysToBeAdded == 0)
  448. return;
  449. /*
  450. * Expand the map if the map if the number of mappings to be added
  451. * is greater than or equal to threshold. This is conservative; the
  452. * obvious condition is (m.size() + size) >= threshold, but this
  453. * condition could result in a map with twice the appropriate capacity,
  454. * if the keys to be added overlap with the keys already in this map.
  455. * By using the conservative calculation, we subject ourself
  456. * to at most one extra resize.
  457. */
  458. if (numKeysToBeAdded > threshold) {
  459. int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
  460. if (targetCapacity > MAXIMUM_CAPACITY)
  461. targetCapacity = MAXIMUM_CAPACITY;
  462. int newCapacity = table.length;
  463. while (newCapacity < targetCapacity)
  464. newCapacity <<= 1;
  465. if (newCapacity > table.length)
  466. resize(newCapacity);
  467. }
  468. for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) {
  469. Map.Entry e = (Map.Entry) i.next();
  470. put(e.getKey(), e.getValue());
  471. }
  472. }
  473. /**
  474. * Removes the mapping for this key from this map if present.
  475. *
  476. * @param key key whose mapping is to be removed from the map.
  477. * @return previous value associated with specified key, or <tt>null</tt>
  478. * if there was no mapping for key. A <tt>null</tt> return can
  479. * also indicate that the map previously associated <tt>null</tt>
  480. * with the specified key.
  481. */
  482. public Object remove(Object key) {
  483. Entry e = removeEntryForKey(key);
  484. return (e == null ? e : e.value);
  485. }
  486. /**
  487. * Removes and returns the entry associated with the specified key
  488. * in the HashMap. Returns null if the HashMap contains no mapping
  489. * for this key.
  490. */
  491. Entry removeEntryForKey(Object key) {
  492. Object k = maskNull(key);
  493. int hash = hash(k);
  494. int i = indexFor(hash, table.length);
  495. Entry prev = table[i];
  496. Entry e = prev;
  497. while (e != null) {
  498. Entry next = e.next;
  499. if (e.hash == hash && eq(k, e.key)) {
  500. modCount++;
  501. size--;
  502. if (prev == e)
  503. table[i] = next;
  504. else
  505. prev.next = next;
  506. e.recordRemoval(this);
  507. return e;
  508. }
  509. prev = e;
  510. e = next;
  511. }
  512. return e;
  513. }
  514. /**
  515. * Special version of remove for EntrySet.
  516. */
  517. Entry removeMapping(Object o) {
  518. if (!(o instanceof Map.Entry))
  519. return null;
  520. Map.Entry entry = (Map.Entry)o;
  521. Object k = maskNull(entry.getKey());
  522. int hash = hash(k);
  523. int i = indexFor(hash, table.length);
  524. Entry prev = table[i];
  525. Entry e = prev;
  526. while (e != null) {
  527. Entry next = e.next;
  528. if (e.hash == hash && e.equals(entry)) {
  529. modCount++;
  530. size--;
  531. if (prev == e)
  532. table[i] = next;
  533. else
  534. prev.next = next;
  535. e.recordRemoval(this);
  536. return e;
  537. }
  538. prev = e;
  539. e = next;
  540. }
  541. return e;
  542. }
  543. /**
  544. * Removes all mappings from this map.
  545. */
  546. public void clear() {
  547. modCount++;
  548. Entry tab[] = table;
  549. for (int i = 0; i < tab.length; i++)
  550. tab[i] = null;
  551. size = 0;
  552. }
  553. /**
  554. * Returns <tt>true</tt> if this map maps one or more keys to the
  555. * specified value.
  556. *
  557. * @param value value whose presence in this map is to be tested.
  558. * @return <tt>true</tt> if this map maps one or more keys to the
  559. * specified value.
  560. */
  561. public boolean containsValue(Object value) {
  562. if (value == null)
  563. return containsNullValue();
  564. Entry tab[] = table;
  565. for (int i = 0; i < tab.length ; i++)
  566. for (Entry e = tab[i] ; e != null ; e = e.next)
  567. if (value.equals(e.value))
  568. return true;
  569. return false;
  570. }
  571. /**
  572. * Special-case code for containsValue with null argument
  573. **/
  574. private boolean containsNullValue() {
  575. Entry tab[] = table;
  576. for (int i = 0; i < tab.length ; i++)
  577. for (Entry e = tab[i] ; e != null ; e = e.next)
  578. if (e.value == null)
  579. return true;
  580. return false;
  581. }
  582. /**
  583. * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
  584. * values themselves are not cloned.
  585. *
  586. * @return a shallow copy of this map.
  587. */
  588. public Object clone() {
  589. HashMap result = null;
  590. try {
  591. result = (HashMap)super.clone();
  592. } catch (CloneNotSupportedException e) {
  593. // assert false;
  594. }
  595. result.table = new Entry[table.length];
  596. result.entrySet = null;
  597. result.modCount = 0;
  598. result.size = 0;
  599. result.init();
  600. result.putAllForCreate(this);
  601. return result;
  602. }
  603. static class Entry implements Map.Entry {
  604. final Object key;
  605. Object value;
  606. final int hash;
  607. Entry next;
  608. /**
  609. * Create new entry.
  610. */
  611. Entry(int h, Object k, Object v, Entry n) {
  612. value = v;
  613. next = n;
  614. key = k;
  615. hash = h;
  616. }
  617. public Object getKey() {
  618. return unmaskNull(key);
  619. }
  620. public Object getValue() {
  621. return value;
  622. }
  623. public Object setValue(Object newValue) {
  624. Object oldValue = value;
  625. value = newValue;
  626. return oldValue;
  627. }
  628. public boolean equals(Object o) {
  629. if (!(o instanceof Map.Entry))
  630. return false;
  631. Map.Entry e = (Map.Entry)o;
  632. Object k1 = getKey();
  633. Object k2 = e.getKey();
  634. if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  635. Object v1 = getValue();
  636. Object v2 = e.getValue();
  637. if (v1 == v2 || (v1 != null && v1.equals(v2)))
  638. return true;
  639. }
  640. return false;
  641. }
  642. public int hashCode() {
  643. return (key==NULL_KEY ? 0 : key.hashCode()) ^
  644. (value==null ? 0 : value.hashCode());
  645. }
  646. public String toString() {
  647. return getKey() + "=" + getValue();
  648. }
  649. /**
  650. * This method is invoked whenever the value in an entry is
  651. * overwritten by an invocation of put(k,v) for a key k that's already
  652. * in the HashMap.
  653. */
  654. void recordAccess(HashMap m) {
  655. }
  656. /**
  657. * This method is invoked whenever the entry is
  658. * removed from the table.
  659. */
  660. void recordRemoval(HashMap m) {
  661. }
  662. }
  663. /**
  664. * Add a new entry with the specified key, value and hash code to
  665. * the specified bucket. It is the responsibility of this
  666. * method to resize the table if appropriate.
  667. *
  668. * Subclass overrides this to alter the behavior of put method.
  669. */
  670. void addEntry(int hash, Object key, Object value, int bucketIndex) {
  671. table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);
  672. if (size++ >= threshold)
  673. resize(2 * table.length);
  674. }
  675. /**
  676. * Like addEntry except that this version is used when creating entries
  677. * as part of Map construction or "pseudo-construction" (cloning,
  678. * deserialization). This version needn't worry about resizing the table.
  679. *
  680. * Subclass overrides this to alter the behavior of HashMap(Map),
  681. * clone, and readObject.
  682. */
  683. void createEntry(int hash, Object key, Object value, int bucketIndex) {
  684. table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);
  685. size++;
  686. }
  687. private abstract class HashIterator implements Iterator {
  688. Entry next; // next entry to return
  689. int expectedModCount; // For fast-fail
  690. int index; // current slot
  691. Entry current; // current entry
  692. HashIterator() {
  693. expectedModCount = modCount;
  694. Entry[] t = table;
  695. int i = t.length;
  696. Entry n = null;
  697. if (size != 0) { // advance to first entry
  698. while (i > 0 && (n = t[--i]) == null)
  699. ;
  700. }
  701. next = n;
  702. index = i;
  703. }
  704. public boolean hasNext() {
  705. return next != null;
  706. }
  707. Entry nextEntry() {
  708. if (modCount != expectedModCount)
  709. throw new ConcurrentModificationException();
  710. Entry e = next;
  711. if (e == null)
  712. throw new NoSuchElementException();
  713. Entry n = e.next;
  714. Entry[] t = table;
  715. int i = index;
  716. while (n == null && i > 0)
  717. n = t[--i];
  718. index = i;
  719. next = n;
  720. return current = e;
  721. }
  722. public void remove() {
  723. if (current == null)
  724. throw new IllegalStateException();
  725. if (modCount != expectedModCount)
  726. throw new ConcurrentModificationException();
  727. Object k = current.key;
  728. current = null;
  729. HashMap.this.removeEntryForKey(k);
  730. expectedModCount = modCount;
  731. }
  732. }
  733. private class ValueIterator extends HashIterator {
  734. public Object next() {
  735. return nextEntry().value;
  736. }
  737. }
  738. private class KeyIterator extends HashIterator {
  739. public Object next() {
  740. return nextEntry().getKey();
  741. }
  742. }
  743. private class EntryIterator extends HashIterator {
  744. public Object next() {
  745. return nextEntry();
  746. }
  747. }
  748. // Subclass overrides these to alter behavior of views' iterator() method
  749. Iterator newKeyIterator() {
  750. return new KeyIterator();
  751. }
  752. Iterator newValueIterator() {
  753. return new ValueIterator();
  754. }
  755. Iterator newEntryIterator() {
  756. return new EntryIterator();
  757. }
  758. // Views
  759. private transient Set entrySet = null;
  760. /**
  761. * Returns a set view of the keys contained in this map. The set is
  762. * backed by the map, so changes to the map are reflected in the set, and
  763. * vice-versa. The set supports element removal, which removes the
  764. * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
  765. * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
  766. * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
  767. * <tt>addAll</tt> operations.
  768. *
  769. * @return a set view of the keys contained in this map.
  770. */
  771. public Set keySet() {
  772. Set ks = keySet;
  773. return (ks != null ? ks : (keySet = new KeySet()));
  774. }
  775. private class KeySet extends AbstractSet {
  776. public Iterator iterator() {
  777. return newKeyIterator();
  778. }
  779. public int size() {
  780. return size;
  781. }
  782. public boolean contains(Object o) {
  783. return containsKey(o);
  784. }
  785. public boolean remove(Object o) {
  786. return HashMap.this.removeEntryForKey(o) != null;
  787. }
  788. public void clear() {
  789. HashMap.this.clear();
  790. }
  791. }
  792. /**
  793. * Returns a collection view of the values contained in this map. The
  794. * collection is backed by the map, so changes to the map are reflected in
  795. * the collection, and vice-versa. The collection supports element
  796. * removal, which removes the corresponding mapping from this map, via the
  797. * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
  798. * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
  799. * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
  800. *
  801. * @return a collection view of the values contained in this map.
  802. */
  803. public Collection values() {
  804. Collection vs = values;
  805. return (vs != null ? vs : (values = new Values()));
  806. }
  807. private class Values extends AbstractCollection {
  808. public Iterator iterator() {
  809. return newValueIterator();
  810. }
  811. public int size() {
  812. return size;
  813. }
  814. public boolean contains(Object o) {
  815. return containsValue(o);
  816. }
  817. public void clear() {
  818. HashMap.this.clear();
  819. }
  820. }
  821. /**
  822. * Returns a collection view of the mappings contained in this map. Each
  823. * element in the returned collection is a <tt>Map.Entry</tt>. The
  824. * collection is backed by the map, so changes to the map are reflected in
  825. * the collection, and vice-versa. The collection supports element
  826. * removal, which removes the corresponding mapping from the map, via the
  827. * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
  828. * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
  829. * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
  830. *
  831. * @return a collection view of the mappings contained in this map.
  832. * @see Map.Entry
  833. */
  834. public Set entrySet() {
  835. Set es = entrySet;
  836. return (es != null ? es : (entrySet = new EntrySet()));
  837. }
  838. private class EntrySet extends AbstractSet {
  839. public Iterator iterator() {
  840. return newEntryIterator();
  841. }
  842. public boolean contains(Object o) {
  843. if (!(o instanceof Map.Entry))
  844. return false;
  845. Map.Entry e = (Map.Entry)o;
  846. Entry candidate = getEntry(e.getKey());
  847. return candidate != null && candidate.equals(e);
  848. }
  849. public boolean remove(Object o) {
  850. return removeMapping(o) != null;
  851. }
  852. public int size() {
  853. return size;
  854. }
  855. public void clear() {
  856. HashMap.this.clear();
  857. }
  858. }
  859. /**
  860. * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
  861. * serialize it).
  862. *
  863. * @serialData The <i>capacity</i> of the HashMap (the length of the
  864. * bucket array) is emitted (int), followed by the
  865. * <i>size</i> of the HashMap (the number of key-value
  866. * mappings), followed by the key (Object) and value (Object)
  867. * for each key-value mapping represented by the HashMap
  868. * The key-value mappings are emitted in the order that they
  869. * are returned by <tt>entrySet().iterator()</tt>.
  870. *
  871. */
  872. private void writeObject(java.io.ObjectOutputStream s)
  873. throws IOException
  874. {
  875. // Write out the threshold, loadfactor, and any hidden stuff
  876. s.defaultWriteObject();
  877. // Write out number of buckets
  878. s.writeInt(table.length);
  879. // Write out size (number of Mappings)
  880. s.writeInt(size);
  881. // Write out keys and values (alternating)
  882. for (Iterator i = entrySet().iterator(); i.hasNext(); ) {
  883. Map.Entry e = (Map.Entry) i.next();
  884. s.writeObject(e.getKey());
  885. s.writeObject(e.getValue());
  886. }
  887. }
  888. private static final long serialVersionUID = 362498820763181265L;
  889. /**
  890. * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
  891. * deserialize it).
  892. */
  893. private void readObject(java.io.ObjectInputStream s)
  894. throws IOException, ClassNotFoundException
  895. {
  896. // Read in the threshold, loadfactor, and any hidden stuff
  897. s.defaultReadObject();
  898. // Read in number of buckets and allocate the bucket array;
  899. int numBuckets = s.readInt();
  900. table = new Entry[numBuckets];
  901. init(); // Give subclass a chance to do its thing.
  902. // Read in size (number of Mappings)
  903. int size = s.readInt();
  904. // Read the keys and values, and put the mappings in the HashMap
  905. for (int i=0; i<size; i++) {
  906. Object key = s.readObject();
  907. Object value = s.readObject();
  908. putForCreate(key, value);
  909. }
  910. }
  911. // These methods are used when serializing HashSets
  912. int capacity() { return table.length; }
  913. float loadFactor() { return loadFactor; }
  914. }