Java 中的HashMap详解和使用示例_动力节点Java学院整理

// 默认构造函数。HashMap()// 指定“容量大小”的构造函数HashMap(int capacity)// 指定“容量大小”和“加载因子”的构造函数HashMap(int capacity, float loadFactor)// 包含“子Map”的构造函数HashMap(Map<? extends K, ? extends V> map)

void   clear()Object  clone()boolean  containsKey(Object key)boolean  containsValue(Object value)Set<Entry<K, V>> entrySet()V   get(Object key)boolean  isEmpty()Set<K>  keySet()V   put(K key, V value)void   putAll(Map<? extends K, ? extends V> map)V   remove(Object key)int   size()Collection<V> values() 

java.lang.Object java.util.AbstractMap<K, V>  java.util.HashMap<K, V>public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { } 

 package java.util; import java.io.*; public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 默认的初始容量是16，必须是2的幂。 static final int DEFAULT_INITIAL_CAPACITY = 16; // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换） static final int MAXIMUM_CAPACITY = 1 << 30; // 默认加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 存储数据的Entry数组，长度是2的幂。 // HashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表 transient Entry[] table; // HashMap的大小，它是HashMap保存的键值对的数量 transient int size; // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子） int threshold; // 加载因子实际大小 final float loadFactor; // HashMap被改变的次数 transient volatile int modCount; // 指定“容量大小”和“加载因子”的构造函数 public HashMap(int initialCapacity, float loadFactor) {  if (initialCapacity < 0)  throw new IllegalArgumentException("Illegal initial capacity: " +       initialCapacity);  // HashMap的最大容量只能是MAXIMUM_CAPACITY  if (initialCapacity > MAXIMUM_CAPACITY)  initialCapacity = MAXIMUM_CAPACITY;  if (loadFactor <= 0 || Float.isNaN(loadFactor))  throw new IllegalArgumentException("Illegal load factor: " +       loadFactor);  // 找出“大于initialCapacity”的最小的2的幂 int capacity = 1; while (capacity < initialCapacity)  capacity <<= 1;  // 设置“加载因子”  this.loadFactor = loadFactor;  // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。  threshold = (int)(capacity * loadFactor);  // 创建Entry数组，用来保存数据  table = new Entry[capacity];  init(); } // 指定“容量大小”的构造函数 public HashMap(int initialCapacity) {  this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 默认构造函数。 public HashMap() {  // 设置“加载因子”  this.loadFactor = DEFAULT_LOAD_FACTOR;  // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。  threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  // 创建Entry数组，用来保存数据  table = new Entry[DEFAULT_INITIAL_CAPACITY];  init(); } // 包含“子Map”的构造函数 public HashMap(Map<? extends K, ? extends V> m) {  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + ,   DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  // 将m中的全部元素逐个添加到HashMap中  putAllForCreate(m); } static int hash(int h) {  h ^= (h >>> 20) ^ (h >>> 12);  return h ^ (h >>> ) ^ (h >>> ); } // 返回索引值 // h & (length-)保证返回值的小于length static int indexFor(int h, int length) {  return h & (length-); } public int size() {  return size; } public boolean isEmpty() { return size == 0; } // 获取key对应的value public V get(Object key) {  if (key == null)  return getForNullKey();  // 获取key的hash值  int hash = hash(key.hashCode());  // 在“该hash值对应的链表”上查找“键值等于key”的元素  for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  Object k;  if (e.hash == hash && ((k = e.key) == key || key.equals(k)))   return e.value;  }  return null; } // 获取“key为null”的元素的值 // HashMap将“key为null”的元素存储在table[]位置！ private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) {  if (e.key == null)   return e.value;  }  return null; } // HashMap是否包含key public boolean containsKey(Object key) {  return getEntry(key) != null; } // 返回“键为key”的键值对 final Entry<K,V> getEntry(Object key) {  // 获取哈希值  // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值 int hash = (key == null) ? 0 : hash(key.hashCode());  // 在“该hash值对应的链表”上查找“键值等于key”的元素  for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  Object k;  if (e.hash == hash &&   ((k = e.key) == key || (key != null && key.equals(k))))   return e;  }  return null; } // 将“key-value”添加到HashMap中 public V put(K key, V value) {  // 若“key为null”，则将该键值对添加到table[]中。  if (key == null)  return putForNullKey(value);  // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。  int hash = hash(key.hashCode());  int i = indexFor(hash, table.length);  for (Entry<K,V> e = table[i]; e != null; e = e.next) {  Object k;  // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {   V oldValue = e.value;   e.value = value;   e.recordAccess(this);   return oldValue;  }  }  // 若“该key”对应的键值对不存在，则将“key-value”添加到table中  modCount++;  addEntry(hash, key, value, i);  return null; } // putForNullKey()的作用是将“key为null”键值对添加到table[]位置 private V putForNullKey(V value) {  for (Entry<K,V> e = table[]; e != null; e = e.next) {  if (e.key == null) {   V oldValue = e.value;   e.value = value;   e.recordAccess(this);   return oldValue;  }  }  // 这里的完全不会被执行到!  modCount++;  addEntry(0, null, value, 0);  return null; } // 创建HashMap对应的“添加方法”， // 它和put()不同。putForCreate()是内部方法，它被构造函数等调用，用来创建HashMap // 而put()是对外提供的往HashMap中添加元素的方法。 private void putForCreate(K key, V value) { int hash = (key == null) ? 0 : hash(key.hashCode());  int i = indexFor(hash, table.length);  // 若该HashMap表中存在“键值等于key”的元素，则替换该元素的value值  for (Entry<K,V> e = table[i]; e != null; e = e.next) {  Object k;  if (e.hash == hash &&   ((k = e.key) == key || (key != null && key.equals(k)))) {   e.value = value;   return;  }  }  // 若该HashMap表中不存在“键值等于key”的元素，则将该key-value添加到HashMap中  createEntry(hash, key, value, i); } // 将“m”中的全部元素都添加到HashMap中。 // 该方法被内部的构造HashMap的方法所调用。 private void putAllForCreate(Map<? extends K, ? extends V> m) {  // 利用迭代器将元素逐个添加到HashMap中  for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {  Map.Entry<? extends K, ? extends V> e = i.next();  putForCreate(e.getKey(), e.getValue());  } } // 重新调整HashMap的大小，newCapacity是调整后的单位 void resize(int newCapacity) {  Entry[] oldTable = table;  int oldCapacity = oldTable.length;  if (oldCapacity == MAXIMUM_CAPACITY) {  threshold = Integer.MAX_VALUE;  return;  }  // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，  // 然后，将“新HashMap”赋值给“旧HashMap”。  Entry[] newTable = new Entry[newCapacity];  transfer(newTable);  table = newTable;  threshold = (int)(newCapacity * loadFactor); } // 将HashMap中的全部元素都添加到newTable中 void transfer(Entry[] newTable) {  Entry[] src = table;  int newCapacity = newTable.length;  for (int j = ; j < src.length; j++) {  Entry<K,V> e = src[j];  if (e != null) {   src[j] = null;   do {   Entry<K,V> next = e.next;   int i = indexFor(e.hash, newCapacity);   e.next = newTable[i];   newTable[i] = e;   e = next;   } while (e != null);  }  } } // 将"m"的全部元素都添加到HashMap中 public void putAll(Map<? extends K, ? extends V> m) {  // 有效性判断  int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0)  return;  // 计算容量是否足够，  // 若“当前实际容量 < 需要的容量”，则将容量x。  if (numKeysToBeAdded > threshold) {  int targetCapacity = (int)(numKeysToBeAdded / loadFactor + );  if (targetCapacity > MAXIMUM_CAPACITY)   targetCapacity = MAXIMUM_CAPACITY;  int newCapacity = table.length;  while (newCapacity < targetCapacity)   newCapacity <<= ;  if (newCapacity > table.length)   resize(newCapacity);  }  // 通过迭代器，将“m”中的元素逐个添加到HashMap中。  for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {  Map.Entry<? extends K, ? extends V> e = i.next();  put(e.getKey(), e.getValue());  } } // 删除“键为key”元素 public V remove(Object key) {  Entry<K,V> e = removeEntryForKey(key);  return (e == null ? null : e.value); } // 删除“键为key”的元素 final Entry<K,V> removeEntryForKey(Object key) {  // 获取哈希值。若key为null，则哈希值为；否则调用hash()进行计算  int hash = (key == null) ? : hash(key.hashCode());  int i = indexFor(hash, table.length);  Entry<K,V> prev = table[i];  Entry<K,V> e = prev;  // 删除链表中“键为key”的元素  // 本质是“删除单向链表中的节点”  while (e != null) {  Entry<K,V> next = e.next;  Object k;  if (e.hash == hash &&   ((k = e.key) == key || (key != null && key.equals(k)))) {   modCount++;   size--;   if (prev == e)   table[i] = next;   else   prev.next = next;   e.recordRemoval(this);   return e;  }  prev = e;  e = next;  }  return e; } // 删除“键值对” final Entry<K,V> removeMapping(Object o) {  if (!(o instanceof Map.Entry))  return null;  Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  Object key = entry.getKey();  int hash = (key == null) ? : hash(key.hashCode());  int i = indexFor(hash, table.length);  Entry<K,V> prev = table[i];  Entry<K,V> e = prev;  // 删除链表中的“键值对e”  // 本质是“删除单向链表中的节点”  while (e != null) {  Entry<K,V> next = e.next;  if (e.hash == hash && e.equals(entry)) {   modCount++;   size--;   if (prev == e)   table[i] = next;   else   prev.next = next;   e.recordRemoval(this);   return e;  }  prev = e;  e = next;  }  return e; } // 清空HashMap，将所有的元素设为null public void clear() {  modCount++;  Entry[] tab = table;  for (int i = 0; i < tab.length; i++)  tab[i] = null;  size = 0; } // 是否包含“值为value”的元素 public boolean containsValue(Object value) { // 若“value为null”，则调用containsNullValue()查找 if (value == null)  return containsNullValue(); // 若“value不为null”，则查找HashMap中是否有值为value的节点。 Entry[] tab = table; for (int i = 0; i < tab.length ; i++)  for (Entry e = tab[i] ; e != null ; e = e.next)   if (value.equals(e.value))   return true; return false; } // 是否包含null值 private boolean containsNullValue() { Entry[] tab = table;  for (int i = ; i < tab.length ; i++)  for (Entry e = tab[i] ; e != null ; e = e.next)   if (e.value == null)   return true; return false; } // 克隆一个HashMap，并返回Object对象 public Object clone() {  HashMap<K,V> result = null;  try {  result = (HashMap<K,V>)super.clone();  } catch (CloneNotSupportedException e) {  // assert false;  }  result.table = new Entry[table.length];  result.entrySet = null;  result.modCount = 0;  result.size = 0;  result.init();  // 调用putAllForCreate()将全部元素添加到HashMap中  result.putAllForCreate(this);  return result; } // Entry是单向链表。 // 它是 “HashMap链式存储法”对应的链表。 // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 static class Entry<K,V> implements Map.Entry<K,V> {  final K key;  V value;  // 指向下一个节点  Entry<K,V> next;  final int hash;  // 构造函数。  // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"  Entry(int h, K k, V v, Entry<K,V> n) {  value = v;  next = n;  key = k;  hash = h;  }  public final K getKey() {  return key;  }  public final V getValue() {  return value;  }  public final V setValue(V newValue) {  V oldValue = value;  value = newValue;  return oldValue;  }  // 判断两个Entry是否相等  // 若两个Entry的“key”和“value”都相等，则返回true。  // 否则，返回false  public final boolean equals(Object o) {  if (!(o instanceof Map.Entry))   return false;  Map.Entry e = (Map.Entry)o;  Object k1 = getKey();  Object k2 = e.getKey();  if (k1 == k2 || (k1 != null && k1.equals(k2))) {   Object v1 = getValue();  Object v2 = e.getValue();  if (v1 == v2 || (v1 != null && v1.equals(v2)))   return true;  }  return false;  }  // 实现hashCode()  public final int hashCode() {  return (key==null ? 0 : key.hashCode()) ^   (value==null ? 0 : value.hashCode());  }  public final String toString() {  return getKey() + "=" + getValue();  }  // 当向HashMap中添加元素时，绘调用recordAccess()。  // 这里不做任何处理  void recordAccess(HashMap<K,V> m) {  }  // 当从HashMap中删除元素时，绘调用recordRemoval()。  // 这里不做任何处理  void recordRemoval(HashMap<K,V> m) {  } } // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。 void addEntry(int hash, K key, V value, int bucketIndex) {  // 保存“bucketIndex”位置的值到“e”中  Entry<K,V> e = table[bucketIndex];  // 设置“bucketIndex”位置的元素为“新Entry”，  // 设置“e”为“新Entry的下一个节点”  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小  if (size++ >= threshold)  resize( * table.length); } // 创建Entry。将“key-value”插入指定位置，bucketIndex是位置索引。 // 它和addEntry的区别是： // () addEntry()一般用在 新增Entry可能导致“HashMap的实际容量”超过“阈值”的情况下。 // 例如，我们新建一个HashMap，然后不断通过put()向HashMap中添加元素； // put()是通过addEntry()新增Entry的。 // 在这种情况下，我们不知道何时“HashMap的实际容量”会超过“阈值”； // 因此，需要调用addEntry() // () createEntry() 一般用在 新增Entry不会导致“HashMap的实际容量”超过“阈值”的情况下。 // 例如，我们调用HashMap“带有Map”的构造函数，它绘将Map的全部元素添加到HashMap中； // 但在添加之前，我们已经计算好“HashMap的容量和阈值”。也就是，可以确定“即使将Map中 // 的全部元素添加到HashMap中，都不会超过HashMap的阈值”。 // 此时，调用createEntry()即可。 void createEntry(int hash, K key, V value, int bucketIndex) {  // 保存“bucketIndex”位置的值到“e”中  Entry<K,V> e = table[bucketIndex];  // 设置“bucketIndex”位置的元素为“新Entry”，  // 设置“e”为“新Entry的下一个节点”  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  size++; } // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。 // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”个子类。 private abstract class HashIterator<E> implements Iterator<E> {  // 下一个元素  Entry<K,V> next;  // expectedModCount用于实现fast-fail机制。  int expectedModCount;  // 当前索引  int index;  // 当前元素  Entry<K,V> current;  HashIterator() {  expectedModCount = modCount;  if (size > ) { // advance to first entry   Entry[] t = table;   // 将next指向table中第一个不为null的元素。   // 这里利用了index的初始值为，从开始依次向后遍历，直到找到不为null的元素就退出循环。   while (index < t.length && (next = t[index++]) == null)   ;  }  }  public final boolean hasNext() {  return next != null;  }  // 获取下一个元素  final Entry<K,V> nextEntry() {  if (modCount != expectedModCount)   throw new ConcurrentModificationException();  Entry<K,V> e = next;  if (e == null)   throw new NoSuchElementException();  // 注意！！！  // 一个Entry就是一个单向链表  // 若该Entry的下一个节点不为空，就将next指向下一个节点;  // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。  if ((next = e.next) == null) {   Entry[] t = table;   while (index < t.length && (next = t[index++]) == null)   ;  }  current = e;  return e;  }  // 删除当前元素  public void remove() {  if (current == null)   throw new IllegalStateException();  if (modCount != expectedModCount)   throw new ConcurrentModificationException();  Object k = current.key;  current = null;  HashMap.this.removeEntryForKey(k);  expectedModCount = modCount;  } } // value的迭代器 private final class ValueIterator extends HashIterator<V> {  public V next() {  return nextEntry().value;  } } // key的迭代器 private final class KeyIterator extends HashIterator<K> {  public K next() {  return nextEntry().getKey();  } } // Entry的迭代器 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {  public Map.Entry<K,V> next() {  return nextEntry();  } } // 返回一个“key迭代器” Iterator<K> newKeyIterator() {  return new KeyIterator(); } // 返回一个“value迭代器” Iterator<V> newValueIterator() {  return new ValueIterator(); } // 返回一个“entry迭代器” Iterator<Map.Entry<K,V>> newEntryIterator() {  return new EntryIterator(); } // HashMap的Entry对应的集合 private transient Set<Map.Entry<K,V>> entrySet = null; // 返回“key的集合”，实际上返回一个“KeySet对象” public Set<K> keySet() {  Set<K> ks = keySet;  return (ks != null ? ks : (keySet = new KeySet())); } // Key对应的集合 // KeySet继承于AbstractSet，说明该集合中没有重复的Key。 private final class KeySet extends AbstractSet<K> {  public Iterator<K> iterator() {  return newKeyIterator();  }  public int size() {  return size;  }  public boolean contains(Object o) {  return containsKey(o);  }  public boolean remove(Object o) {  return HashMap.this.removeEntryForKey(o) != null;  }  public void clear() {  HashMap.this.clear();  } } // 返回“value集合”，实际上返回的是一个Values对象 public Collection<V> values() {  Collection<V> vs = values;  return (vs != null ? vs : (values = new Values())); } // “value集合” // Values继承于AbstractCollection，不同于“KeySet继承于AbstractSet”， // Values中的元素能够重复。因为不同的key可以指向相同的value。 private final class Values extends AbstractCollection<V> {  public Iterator<V> iterator() {  return newValueIterator();  }  public int size() {  return size;  }  public boolean contains(Object o) {  return containsValue(o);  }  public void clear() {  HashMap.this.clear();  } } // 返回“HashMap的Entry集合” public Set<Map.Entry<K,V>> entrySet() {  return entrySet(); } // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象 private Set<Map.Entry<K,V>> entrySet() {  Set<Map.Entry<K,V>> es = entrySet;  return es != null ? es : (entrySet = new EntrySet()); } // EntrySet对应的集合 // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {  public Iterator<Map.Entry<K,V>> iterator() {  return newEntryIterator();  }  public boolean contains(Object o) {  if (!(o instanceof Map.Entry))   return false;  Map.Entry<K,V> e = (Map.Entry<K,V>) o;  Entry<K,V> candidate = getEntry(e.getKey());  return candidate != null && candidate.equals(e);  }  public boolean remove(Object o) {  return removeMapping(o) != null;  }  public int size() {  return size;  }  public void clear() {  HashMap.this.clear();  } } // java.io.Serializable的写入函数 // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中 private void writeObject(java.io.ObjectOutputStream s)  throws IOException {  Iterator<Map.Entry<K,V>> i =  (size > 0) ? entrySet0().iterator() : null;   // Write out the threshold, loadfactor, and any hidden stuff  s.defaultWriteObject();  // Write out number of buckets  s.writeInt(table.length);  // Write out size (number of Mappings)  s.writeInt(size);  // Write out keys and values (alternating)  if (i != null) {  while (i.hasNext()) {  Map.Entry<K,V> e = i.next();  s.writeObject(e.getKey());  s.writeObject(e.getValue());  }  } } private static final long serialVersionUID = L; // java.io.Serializable的读取函数：根据写入方式读出 // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出 private void readObject(java.io.ObjectInputStream s)  throws IOException, ClassNotFoundException {  // Read in the threshold, loadfactor, and any hidden stuff  s.defaultReadObject();  // Read in number of buckets and allocate the bucket array;  int numBuckets = s.readInt();  table = new Entry[numBuckets];  init(); // Give subclass a chance to do its thing.  // Read in size (number of Mappings)  int size = s.readInt();  // Read the keys and values, and put the mappings in the HashMap  for (int i=; i<size; i++) {  K key = (K) s.readObject();  V value = (V) s.readObject();  putForCreate(key, value);  } } // 返回“HashMap总的容量” int capacity() { return table.length; } // 返回“HashMap的加载因子” float loadFactor() { return loadFactor; } }

transient Entry[] table;

 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; // 指向下一个节点 Entry<K,V> next; final int hash; // 构造函数。 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" Entry(int h, K k, V v, Entry<K,V> n) {  value = v;  next = n;  key = k;  hash = h; } public final K getKey() {  return key; } public final V getValue() {  return value; } public final V setValue(V newValue) {  V oldValue = value;  value = newValue;  return oldValue; } // 判断两个Entry是否相等 // 若两个Entry的“key”和“value”都相等，则返回true。 // 否则，返回false public final boolean equals(Object o) {  if (!(o instanceof Map.Entry))  return false;  Map.Entry e = (Map.Entry)o; Object k1 = getKey();  Object k2 = e.getKey();  if (k1 == k2 || (k1 != null && k1.equals(k2))) {  Object v1 = getValue();  Object v2 = e.getValue();  if (v1 == v2 || (v1 != null && v1.equals(v2)))   return true;  }  return false; } // 实现hashCode() public final int hashCode() {  return (key==null ? 0 : key.hashCode()) ^  (value==null ? 0 : value.hashCode()); } public final String toString() {  return getKey() + "=" + getValue(); } // 当向HashMap中添加元素时，绘调用recordAccess()。 // 这里不做任何处理 void recordAccess(HashMap<K,V> m) { } // 当从HashMap中删除元素时，绘调用recordRemoval()。 // 这里不做任何处理 void recordRemoval(HashMap<K,V> m) { } }

// 默认构造函数。 public HashMap() { // 设置“加载因子” this.loadFactor = DEFAULT_LOAD_FACTOR; // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // 创建Entry数组，用来保存数据 table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } // 指定“容量大小”和“加载因子”的构造函数 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)  throw new IllegalArgumentException("Illegal initial capacity: " +      initialCapacity); // HashMap的最大容量只能是MAXIMUM_CAPACITY if (initialCapacity > MAXIMUM_CAPACITY)  initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor))  throw new IllegalArgumentException("Illegal load factor: " +      loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; // 设置“加载因子” this.loadFactor = loadFactor; // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 threshold = (int)(capacity * loadFactor); // 创建Entry数组，用来保存数据 table = new Entry[capacity]; init(); } // 指定“容量大小”的构造函数 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 包含“子Map”的构造函数 public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + ,   DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // 将m中的全部元素逐个添加到HashMap中 putAllForCreate(m); }

public void clear() { modCount++; Entry[] tab = table; for (int i = 0; i < tab.length; i++)  tab[i] = null; size = 0; } 

public boolean containsKey(Object key) { return getEntry(key) != null;}

final Entry<K,V> getEntry(Object key) { // 获取哈希值 // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值 int hash = (key == null) ? 0 : hash(key.hashCode()); // 在“该hash值对应的链表”上查找“键值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  Object k;  if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k))))  return e; } return null; }

 public boolean containsValue(Object value) { // 若“value为null”，则调用containsNullValue()查找 if (value == null)  return containsNullValue(); // 若“value不为null”，则查找HashMap中是否有值为value的节点。 Entry[] tab = table; for (int i = ; i < tab.length ; i++)  for (Entry e = tab[i] ; e != null ; e = e.next)  if (value.equals(e.value))   return true; return false; }

private boolean containsNullValue() { Entry[] tab = table; for (int i = ; i < tab.length ; i++)  for (Entry e = tab[i] ; e != null ; e = e.next)  if (e.value == null)   return true; return false; }

 // 返回“HashMap的Entry集合” public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象 private Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } // EntrySet对应的集合 // EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() {  return newEntryIterator(); } public boolean contains(Object o) {  if (!(o instanceof Map.Entry))  return false;  Map.Entry<K,V> e = (Map.Entry<K,V>) o;  Entry<K,V> candidate = getEntry(e.getKey());  return candidate != null && candidate.equals(e); } public boolean remove(Object o) {  return removeMapping(o) != null; } public int size() {  return size; } public void clear() {  HashMap.this.clear(); } }

 // 返回一个“entry迭代器” Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } // Entry的迭代器 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() {  return nextEntry(); } } // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。 // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”个子类。 private abstract class HashIterator<E> implements Iterator<E> { // 下一个元素 Entry<K,V> next; // expectedModCount用于实现fast-fail机制。 int expectedModCount; // 当前索引 int index; // 当前元素 Entry<K,V> current; HashIterator() {  expectedModCount = modCount;  if (size > 0) { // advance to first entry  Entry[] t = table;  // 将next指向table中第一个不为null的元素。  // 这里利用了index的初始值为，从开始依次向后遍历，直到找到不为null的元素就退出循环。  while (index < t.length && (next = t[index++]) == null)   ;  } } public final boolean hasNext() {  return next != null; } // 获取下一个元素 final Entry<K,V> nextEntry() {  if (modCount != expectedModCount)  throw new ConcurrentModificationException();  Entry<K,V> e = next;  if (e == null)  throw new NoSuchElementException();  // 注意！！！  // 一个Entry就是一个单向链表  // 若该Entry的下一个节点不为空，就将next指向下一个节点;  // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。  if ((next = e.next) == null) {  Entry[] t = table;  while (index < t.length && (next = t[index++]) == null)   ;  }  current = e;  return e; } // 删除当前元素 public void remove() {  if (current == null)  throw new IllegalStateException();  if (modCount != expectedModCount)  throw new ConcurrentModificationException();  Object k = current.key;  current = null;  HashMap.this.removeEntryForKey(k);  expectedModCount = modCount; } }

public V get(Object key) { if (key == null)  return getForNullKey(); // 获取key的hash值 int hash = hash(key.hashCode()); // 在“该hash值对应的链表”上查找“键值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  Object k;  if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  return e.value; } return null; }

 public V put(K key, V value) { // 若“key为null”，则将该键值对添加到table[]中。 if (key == null)  return putForNullKey(value); // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) {  Object k;  // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  V oldValue = e.value;  e.value = value;  e.recordAccess(this);  return oldValue;  } } // 若“该key”对应的键值对不存在，则将“key-value”添加到table中 modCount++; addEntry(hash, key, value, i); return null; }

void addEntry(int hash, K key, V value, int bucketIndex) { // 保存“bucketIndex”位置的值到“e”中 Entry<K,V> e = table[bucketIndex]; // 设置“bucketIndex”位置的元素为“新Entry”， // 设置“e”为“新Entry的下一个节点” table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小 if (size++ >= threshold)  resize(2 * table.length); } 

 void createEntry(int hash, K key, V value, int bucketIndex) { // 保存“bucketIndex”位置的值到“e”中 Entry<K,V> e = table[bucketIndex]; // 设置“bucketIndex”位置的元素为“新Entry”， // 设置“e”为“新Entry的下一个节点” table[bucketIndex] = new Entry<K,V>(hash, key, value, e); size++; } 

if (size++ >= threshold) resize(2 * table.length);

public void putAll(Map<? extends K, ? extends V> m) { // 有效性判断 int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0)  return; // 计算容量是否足够， // 若“当前实际容量 < 需要的容量”，则将容量x。 if (numKeysToBeAdded > threshold) {  int targetCapacity = (int)(numKeysToBeAdded / loadFactor + );  if (targetCapacity > MAXIMUM_CAPACITY)  targetCapacity = MAXIMUM_CAPACITY;  int newCapacity = table.length;  while (newCapacity < targetCapacity)  newCapacity <<= 1;  if (newCapacity > table.length)  resize(newCapacity); } // 通过迭代器，将“m”中的元素逐个添加到HashMap中。 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {  Map.Entry<? extends K, ? extends V> e = i.next();  put(e.getKey(), e.getValue()); } }

 public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } // 删除“键为key”的元素 final Entry<K,V> removeEntryForKey(Object key) { // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算 int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; // 删除链表中“键为key”的元素 // 本质是“删除单向链表中的节点” while (e != null) {  Entry<K,V> next = e.next;  Object k;  if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k)))) {  modCount++;  size--;  if (prev == e)   table[i] = next;  else   prev.next = next;  e.recordRemoval(this);  return e;  }  prev = e;  e = next; } return e; }

// 克隆一个HashMap，并返回Object对象 public Object clone() { HashMap<K,V> result = null; try {  result = (HashMap<K,V>)super.clone(); } catch (CloneNotSupportedException e) {  // assert false; } result.table = new Entry[table.length]; result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); // 调用putAllForCreate()将全部元素添加到HashMap中 result.putAllForCreate(this); return result; }

 // java.io.Serializable的写入函数 // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中 private void writeObject(java.io.ObjectOutputStream s) throws IOException { Iterator<Map.Entry<K,V>> i =  (size > 0) ? entrySet0().iterator() : null; // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); // Write out number of buckets s.writeInt(table.length); // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) if (i != null) {  while (i.hasNext()) {  Map.Entry<K,V> e = i.next();  s.writeObject(e.getKey());  s.writeObject(e.getValue());  } } } // java.io.Serializable的读取函数：根据写入方式读出 // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出 private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold, loadfactor, and any hidden stuff s.defaultReadObject();  // Read in number of buckets and allocate the bucket array; int numBuckets = s.readInt(); table = new Entry[numBuckets];  init(); // Give subclass a chance to do its thing.  // Read in size (number of Mappings) int size = s.readInt();  // Read the keys and values, and put the mappings in the HashMap for (int i=; i<size; i++) {  K key = (K) s.readObject();  V value = (V) s.readObject();  putForCreate(key, value); }51 }

// 假设map是HashMap对象// map中的key是String类型，value是Integer类型Integer integ = null;Iterator iter = map.entrySet().iterator();while(iter.hasNext()) { Map.Entry entry = (Map.Entry)iter.next(); // 获取key key = (String)entry.getKey(); // 获取value integ = (Integer)entry.getValue();}

// 假设map是HashMap对象// map中的key是String类型，value是Integer类型String key = null;Integer integ = null;Iterator iter = map.keySet().iterator();while (iter.hasNext()) { // 获取key key = (String)iter.next(); // 根据key，获取value integ = (Integer)map.get(key);}

// 假设map是HashMap对象// map中的key是String类型，value是Integer类型Integer value = null;Collection c = map.values();Iterator iter= c.iterator();while (iter.hasNext()) { value = (Integer)iter.next();}

 import java.util.Map; import java.util.Random; import java.util.Iterator; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; import java.util.Collection; /* * @desc 遍历HashMap的测试程序。 * (01) 通过entrySet()去遍历key、value，参考实现函数： * iteratorHashMapByEntryset() * (02) 通过keySet()去遍历key、value，参考实现函数： * iteratorHashMapByKeyset() * (03) 通过values()去遍历value，参考实现函数： * iteratorHashMapJustValues() * *  */ public class HashMapIteratorTest { public static void main(String[] args) {  int val = ;  String key = null;  Integer value = null;  Random r = new Random();  HashMap map = new HashMap();  for (int i=0; i<12; i++) {  // 随机获取一个[0,100)之间的数字  val = r.nextInt(100);    key = String.valueOf(val);  value = r.nextInt(5);  // 添加到HashMap中  map.put(key, value);  System.out.println(" key:"+key+" value:"+value);  }  // 通过entrySet()遍历HashMap的key-value  iteratorHashMapByEntryset(map) ;  // 通过keySet()遍历HashMap的key-value  iteratorHashMapByKeyset(map) ;  // 单单遍历HashMap的value  iteratorHashMapJustValues(map);  } /* * 通过entry set遍历HashMap * 效率高! */ private static void iteratorHashMapByEntryset(HashMap map) {  if (map == null)  return ;  System.out.println("/niterator HashMap By entryset");  String key = null;  Integer integ = null;  Iterator iter = map.entrySet().iterator();  while(iter.hasNext()) {  Map.Entry entry = (Map.Entry)iter.next();  key = (String)entry.getKey();  integ = (Integer)entry.getValue();  System.out.println(key+" -- "+integ.intValue());  } } /* * 通过keyset来遍历HashMap * 效率低! */ private static void iteratorHashMapByKeyset(HashMap map) {  if (map == null)  return ;  System.out.println("/niterator HashMap By keyset");  String key = null;  Integer integ = null;  Iterator iter = map.keySet().iterator();  while (iter.hasNext()) {  key = (String)iter.next();  integ = (Integer)map.get(key);  System.out.println(key+" -- "+integ.intValue());  } } /* * 遍历HashMap的values */ private static void iteratorHashMapJustValues(HashMap map) {  if (map == null)  return ;  Collection c = map.values();  Iterator iter= c.iterator();  while (iter.hasNext()) {  System.out.println(iter.next()); } } }

 import java.util.Map; import java.util.Random; import java.util.Iterator; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; import java.util.Collection; /* * @desc HashMap测试程序 *   *  */ public class HashMapTest {  public static void main(String[] args) {   testHashMapAPIs();  }  private static void testHashMapAPIs() {   // 初始化随机种子   Random r = new Random();   // 新建HashMap   HashMap map = new HashMap();   // 添加操作   map.put("one", r.nextInt(10));   map.put("two", r.nextInt(10));   map.put("three", r.nextInt(10));   // 打印出map   System.out.println("map:"+map );   // 通过Iterator遍历key-value   Iterator iter = map.entrySet().iterator();   while(iter.hasNext()) {    Map.Entry entry = (Map.Entry)iter.next();    System.out.println("next : "+ entry.getKey() +" - "+entry.getValue());   }   // HashMap的键值对个数     System.out.println("size:"+map.size());   // containsKey(Object key) :是否包含键key   System.out.println("contains key two : "+map.containsKey("two"));   System.out.println("contains key five : "+map.containsKey("five"));   // containsValue(Object value) :是否包含值value   System.out.println("contains value : "+map.containsValue(new Integer()));   // remove(Object key) ： 删除键key对应的键值对   map.remove("three");   System.out.println("map:"+map );   // clear() ： 清空HashMap   map.clear();   // isEmpty() : HashMap是否为空   System.out.println((map.isEmpty()?"map is empty":"map is not empty") );  } }

map:{two=7, one=9, three=6}next : two - 7next : one - 9next : three - 6size:3contains key two : truecontains key five : falsecontains value 0 : falsemap:{two=7, one=9}map is empty