这一章，我们对HashMap进行学习。
HashMap介绍
HashMap是一个散列表，它存储的内容是键值对（key-value）映射。
HashMap继承于AbstractMap,实现了Map,Cloneable,java.io.Serializable接口
HashMap的实现不是同步的，这意味着它是线程不安全的。它的key、value都可以为null,此外，HashMap中的映射不是有序的。
HashMap的实例有两个参数影响其性能：“初始容量”和“加载因子”。容量是哈希表中桶的数量，初始容量知识哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种度量。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子是0.75，这是在时间和空间成本上寻求一种折中，加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数HashMap类的操作中，包括get和put操作，都反映了这一点）。在设置初始容量是应该考虑到映射所需要的条目数及其加载因子，以便最大限度地减少rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生rehash操作。
HashMap的构造函数
HashMap共有4个构造函数,如下：
// 默认构造函数。 HashMap() // 指定“容量大小”的构造函数 HashMap(int capacity) 例如：当传入capacity为8，默认加载因子为0.75时，当超过 最大值*加载因子时会扩容。即在第7个元素时会扩容 // 指定“容量大小”和“加载因子”的构造函数 HashMap(int capacity, float loadFactor) // 包含“子Map”的构造函数 HashMap(Map<? extends K, ? extends V> map)
HashMap的API
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()
HashMap数据结构
HashMap的继承关系
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 { }
HashMap与Map关系如下图：
从图中可以看出：
1. HashMap继承于AbstractMap类，实现了Map接口。Map是“key-value 键值对”接口。AbstractMap实现了“键值对”的通用函数接口。
2. HashMap是通过“拉链法”实现的哈希表。它包含几个重要的成员变量：table,size,threshold,loadFactor,modCount。
table 是一个Entry[] 数组类型，而Entry实际上就是一个单向链表。哈希表的“key-value 键值对”都是存储在Entry数组中的。
size是HashMap的大小，它是HashMap保存的键值对的数量。默认大小为16
threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=“容量*加载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
loadFactor就是加载因子。默认大小为0.75
modCount是用来实现fail-fast机制的。
HashMap源码分析（基于JDK1.8_131）
说明：
在详细介绍HashMap的代码之前，我们需要了解：HashMap就是一个散列表，它是通过“拉链法”解决哈希冲突的。
还需要再补充说明的一点是影响HashMap性能的有两个参数：初始容量（initialCapacity）和加载因子（loadFactor）。 容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash 操作。从而哈希表将具有大约两倍的桶数。
HashMap的“拉链法”相关内容
HashMap数据存储数组
transient Node<K,V>[] table;（ps:被transient修饰之后则不能被序列化）
HashMap中的key-value都是存储在Entry数组中的
数据节点Entry的数据结构
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; //指向下一个节点 Node<K,V> next; //构造函数 //输入参数包括“哈希值（h）”,"键（K）","值（V）","下一节点（n）" Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } /** * 判断两个Node是否相等 * 若两个Node的“key”和“value”都相等，则返回true * 否则返回false */ public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
从中，我们可以看出Entry实际上就是一个单向链表。这也是为什么我们说HashMap是通过拉链法来解决哈希冲突的。
Entry实现了Map.Entry接口，即实现getKey()，getValue(),setValue(V value),equals(Object o),hashCode(),这些函数。这些都是基本的读取/修改key、value值得函数。
HashMap的构造函数
HashMap共包含4个构造函数
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive * 指定“容量大小”和“加载因子”的构造函数 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //设置“加载因子” this.loadFactor = loadFactor; //设置"HashMap阈值"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 this.threshold = tableSizeFor(initialCapacity); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. * 指定"容量大小"的构造函数 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). * 创建一个空的HashMap，它的初始容量是16，加载因子是0.75 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null * 包含“子Map”的构造函数 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; //将m中的全部元素逐个添加到HashMap中 putMapEntries(m, false); }
HashMap的主要对外接口
clear()
clear()的作用是清空HashMap。它是通过将所有的元素设为null来实现的。
public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } }
containsKey()
containsKey()的作用是判断HashMap是否包含key.
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }
containsKey()首先通过getNode(hash(key), key) 来获取key 对应的Entry,然后判断该Entry是否为null。
getNode() 的源码如下：
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //总是检查第一个元素，当满足条件则直接返回第一个元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //如果第一个元素不满足，则循环检查其他元素 if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
getNode()的作用就是返回”键为key”的键值对。
containsValue()
containsValue()的作用是判断HashMap是否包含“值为value”的元素。
public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { //若“value不为null”,则查找HashMap中是否有值为value //的节点。 if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }
entrySet()、values()、keySet()
它们3个的原理类似，这里以entrySet()为例来说明。
entrySet()的作用是返回“HashMap中的所有Entry的集合”，它是一个集合。实现代码如下：
//返回“HashMap的Entry集合”，它实际上是返回一个EntrySet对象 public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } //EntrySet 对应的集合 //EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。 final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super Map.Entry<K,V>> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } } }
HashMap是通过拉链法实现的散列表，表现在HashMap包含许多的Entry,而每一个Entry本质上又是一个单向链表。那么HashMap遍历key-value键值对的时候，是如何逐个去遍历的呢？
下面我们就看看HashMap是如何通过entrySet()遍历的。
//Entry的迭代器 final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } // abstract class HashIterator { Node<K,V> next; // next entry to return，下一个元素 Node<K,V> current; // current entry 当前元素 int expectedModCount; // for fast-fail 用于实现 fast-fail 机制 int index; // current slot 当前索引 HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; //将next指向table中第一个不为null的元素 //这里利用了index的初始值为0，从0开始依次向后遍历，知道找到不为null的元素就退出循环 if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } // 获取下一个元素 final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); //一个Entry就是一个单向链表 //若该Entry的下一个节点不为空，就将next指向下一个节点； //否则，将next指向下一个链表（也是下一个Entry）的不为null的节点。 if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }
当我们通过entrySet()获取到Iterator的next()方法去遍历HashMap时，实际上调用的是nextNode()。而nextEntry()的实现方式，先遍历Node(根据Node在table中的序号，从小到大的遍历)；然后对每个Node(即单向链表)，逐个遍历。
get()
get()的作用是获取key对应的value,它的实现代码如下：
public V get(Object key) { Node<K,V> e; //hash(key) 获取key的hash值 return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //在"该hash值对应的链表"上查找"键值等于key"的元素 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
put()
put()的作用是对外提供接口，让HashMap对象可以通过put()将"key-value" 添加到HashMap中。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //若“该key”对应的键值对已经存在，则用新的value取代旧的value, //然后退出。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //若“该key对应的键值对不存在，则将“key-value”添加到table中” ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
若要添加到HashMap中的键值对对应的key已经存在HashMap中，则找到该键值对；然后新的value取代旧的value,并退出。
如要添加到HashMap中的键值对对应的key不在HashMap中，则将其添加到该哈希值对应的链表中。
putAll()
putAll()的作用是将”m”的全部元素都添加到HashMap中，它的代码如下：
public void putAll(Map<? extends K, ? extends V> m) { putMapEntries(m, true); } final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-size float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
remove()
remove()的作用是删除”键为key”元素
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
HashMap实现的Cloneable接口
HashMap实现了Cloneable接口，即实现了clone()方法
clone() 方法的作用很简单，就是克隆一个HashMap对象并返回。
public Object clone() { HashMap<K,V> result; try { result = (HashMap<K,V>)super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } result.reinitialize(); result.putMapEntries(this, false); return result; }
HashMap实现的Serializable接口
HashMap实现了Serializable,分别实现了串行读取、写入功能。
串行写入函数是writeObject()，它的作用是将HashMap的”总的容量，实际容量，所有的Node”都写入到输出流中。
而串行读取函数是readObject()，它的作用是将HashMap的”总的容量，实际容量，所有的Node”依次读出
// java.io.Serializable的写入函数 // 将HashMap的“总的容量，实际容量，所有的Node”都写入到输出流中 private void writeObject(java.io.ObjectOutputStream s) throws IOException { int buckets = capacity(); // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); s.writeInt(buckets); s.writeInt(size); internalWriteEntries(s); } // java.io.Serializable的读取函数：根据写入方式读出 // 将HashMap的“总的容量，实际容量，所有的Node”依次读出 private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); reinitialize(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new InvalidObjectException("Illegal load factor: " + loadFactor); s.readInt(); // Read and ignore number of buckets int mappings = s.readInt(); // Read number of mappings (size) if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); else if (mappings > 0) { // (if zero, use defaults) // Size the table using given load factor only if within // range of 0.25...4.0 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f); float fc = (float)mappings / lf + 1.0f; int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? DEFAULT_INITIAL_CAPACITY : (fc >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)fc)); float ft = (float)cap * lf; threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE); @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] tab = (Node<K,V>[])new Node[cap]; table = tab; // Read the keys and values, and put the mappings in the HashMap for (int i = 0; i < mappings; i++) { @SuppressWarnings("unchecked") K key = (K) s.readObject(); @SuppressWarnings("unchecked") V value = (V) s.readObject(); putVal(hash(key), key, value, false, false); } } }
HashMap遍历方式
遍历HashMap的键值对
第一步：根据entrySet()获取HashMap的“键值对”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
// 假设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(); }
遍历HashMap的键
第一步：根据keySet()获取HashMap的“键”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
// 假设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); }
遍历HashMap的值
第一步：根据value()获取HashMap的“值”的集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
// 假设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(); }
http://www.cnblogs.com/skywang12345/p/3310835.html#a21
