本文基于版本 JDK 1.7，即 Java 7。
HashMap用法 常用API V get (Object key) ; V put (K key, V value) ; void putAll (Map<? extends K, ? extends V> m) V remove (Object key) ; boolean containsKey (Object key) boolean containsValue (Object value) Set<K> keySet () ; Collection<V> values () ; void clear () int size () boolean isEmpty ()
import java.util.*;import java.util.concurrent.*;public class test static Map<String, Integer> map = new HashMap<>(); public static void main (String[] args) map.put("Java" , 1 ); map.put("hadoop" , 2 ); map.put("产品经理" , 3 ); System.out.println("key = 产品经理时的值为：" + map.get("产品经理" )); System.out.println(); System.out.println("------------------下面是遍历-------------------" ); test(); } public static void test () System.out.println("------------方法1------------" ); Set<Map.Entry<String, Integer>> entrySet = map.entrySet(); for (Map.Entry<String, Integer> entry : entrySet) { System.out.print(entry.getKey()); System.out.println(entry.getValue()); } System.out.println("----------" ); Iterator iter1 = entrySet.iterator(); while (iter1.hasNext()) { Map.Entry entry = (Map.Entry) iter1.next(); System.out.print((String) entry.getKey()); System.out.println((Integer) entry.getValue()); } System.out.println("------------方法2------------" ); Set<String> keySet = map.keySet(); for (String key : keySet) { System.out.print(key); System.out.println(map.get(key)); } System.out.println("----------" ); Iterator iter2 = keySet.iterator(); String key = null ; while (iter2.hasNext()) { key = (String) iter2.next(); System.out.print(key); System.out.println(map.get(key)); } System.out.println("------------方法3------------" ); Collection valueSet = map.values(); Iterator iter3 = valueSet.iterator(); while (iter3.hasNext()) { System.out.println(iter3.next()); } } }
结果
key = 产品经理时的值为：3 ------------------下面是遍历------------------- ------------方法1------------ Java1 hadoop2 产品经理3 ---------- Java1 hadoop2 产品经理3 ------------方法2------------ Java1 hadoop2 产品经理3 ---------- Java1 hadoop2 产品经理3 ------------方法3------------ 1 2 3
数据结构 简介 1、HashMap是散列表的一种，HashMap本身采用数组来进行储存。同时HashMap采用拉链法来解决hash冲突，拉链法就是通过链表来解决hash冲突。所以说整体上来看，HashMap采用的数据结构 = 数组（主） + 单链表（副）
大致是这样的一个结构
每个链表就算哈希表的桶（bucket）
链表的节点值就算一个键值对
重要参数介绍 构造函数源码
先贴一下，后面参数介绍会使用到。
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; threshold = initialCapacity; init(); } public HashMap (int initialCapacity) this (initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap () this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashMap (Map<? extends K, ? extends V> m) this (Math.max((int ) (m.size() / DEFAULT_LOAD_FACTOR) + 1 , DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }
下面的代码有些顺序和源码可能不太一样，仅仅是顺序，笔者是为了更好的阅读体验
public class HashMap <K ,V > extends AbstractMap <K ,V > implements Map <K ,V >, Cloneable , Serializable static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ; static final int MAXIMUM_CAPACITY = 1 << 30 ; final float loadFactor; static final float DEFAULT_LOAD_FACTOR = 0.75f ; transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; static final Entry<?,?>[] EMPTY_TABLE = {}; transient int size; int threshold;
数组-Entry static class Entry <K ,V > implements Map .Entry <K ,V > final K key; V value; Entry<K,V> next; int hash; 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; } 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 ; } public final int hashCode () return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString () return getKey() + "=" + getValue(); } void recordAccess (HashMap<K,V> m) } void recordRemoval (HashMap<K,V> m) } }
HashMap中的数组元素 & 链表节点 采用 Entry类实现
1、一个正方形代表一个Entry对象，同时也代表一个键值对。
2、即 HashMap的本质 = 1个存储Entry类对象的数组 + 多个单链表
3、Entry对象本质 = 1个映射（键 - 值对），属性包括：键（key）、值（value）、 下个节点( next) = 单链表的指针 = 也是一个Entry对象，用于解决hash冲突
构造函数源码 public class HashMap <K ,V > extends AbstractMap <K ,V > implements Map <K ,V >, Cloneable , Serializable { public HashMap () this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashMap (int initialCapacity) this (initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap (int initialCapacity, float loadFactor) if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; this .loadFactor = loadFactor; threshold = initialCapacity; init(); } public HashMap (Map<? extends K, ? extends V> m) this (Math.max((int ) (m.size() / DEFAULT_LOAD_FACTOR) + 1 , DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); } }
put()源码 put() public V put (K key, V value) if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null ) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null ; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this ); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null ; }
inflateTable() private void inflateTable (int toSize) int capacity = roundUpToPowerOf2(toSize); threshold = (int ) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1 ); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }
roundUpToPowerOf2() private static int roundUpToPowerOf2 (int number) return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1 ) ? Integer.highestOneBit((number - 1 ) << 1 ) : 1 ; }
putForNullKey() 当 key ==null时，将该 key-value 的存储位置规定为数组table 中的第1个位置，即table [0]
private V putForNullKey (V value) for (Entry<K,V> e = table[0 ]; 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的键key 可为null（区别于 HashTable的key 不可为null）HashMap的键key 可为null且只能为1个，但值value可为null且为多个
hash()
这个方法比较重要，1.7和1.8改动的比较大
final int hash (Object k) int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20 ) ^ (h >>> 12 ); return h ^ (h >>> 7 ) ^ (h >>> 4 ); }
indexFor() static int indexFor (int h, int length) return h & (length-1 ); }
addEntry() void addEntry (int hash, K key, V value, int bucketIndex) if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0 ; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
扩容源码 下面的也是JDK7扩容的步骤，接着上面的addEntry()
resize() void resize (int newCapacity) Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return ; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int )Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1 ); }
transfer() void transfer (Entry[] newTable, boolean rehash) int newCapacity = newTable.length; for (Entry<K,V> e : table) { while (null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
大概画了一下图：
1、在扩容resize（）过程中，在将旧数组上的数据转移到新数组上时，转移操作就是按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况。
2、设重新计算存储位置后不变，即扩容前 1->2->3，扩容后 = 3->2->1
3、此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现环形链表 ，从而在获取数据、遍历链表时形成死循环（Infinite Loop），即线程不安全 。
createEntry() void createEntry (int hash, K key, V value, int bucketIndex) Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }
举个例子说明流程：
1、假设hashmap中容量为16，加载因为为0.75 = 12。
2、此时hashmap中有11个元素，也就是size == 11，在你添加第12个元素时。看代码，此时size还是11，所以并不会扩容。只有在你调用完createEntry(),size++执行完毕后，size变成12。
3、在添加第13个元素时，才会进入if逻辑里进行先扩容。
void addEntry (int hash, K key, V value, int bucketIndex) if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0 ; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
扩容出现的死循环链表 void transfer (Entry[] newTable, boolean rehash) int newCapacity = newTable.length; for (Entry<K,V> e : table) { while (null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
前置条件 1、为了演示方便，初始状态时，hashmap容量为2，加载因子为默认的0.75.
步骤1 hashmap初始状态
1、此时只有一个元素，扩容阈值为2*0.75 = 1.5。
2、此时假设有两个线程，线程a和线程b同时put，并且都没有进入到addEntry()方法里的if逻辑【因为此时size都没有++，size == 1 1 < 1.5 所以if判断不成立。】。两个线程都准备同时调用createEntry()方法。
void addEntry (int hash, K key, V value, int bucketIndex) if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0 ; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
3、线程a put的是 e3 = <k3,v3>。线程b put的是e2 = <k2,v2>。两个都调用了createEntry()方法。
步骤2 两个线程调用完毕之后，hashmap目前是这样的。
此时size==3。下次再进行put的时候，addEntry()方法里的if判断就会成立 。
步骤3 1、接着，又来了两个线程，线程1和线程2。【假设线程1put的是e1，线程2put的是e0。其实也不用管它们两put的是谁】
2、两个线程都同时调用resize()方法，新数组已经扩容完毕，准备转移旧数组上的数据到新数组里。也就是准备调用resize()里的下面这个方法。
//5、将旧数组上的数据（键值对）转移到新table中，从而完成扩容 transfer(newTable, initHashSeedAsNeeded(newCapacity));
3、来看下此时内存里的状态
步骤4 来看下源码【上面源码里有注释，这里把注释去掉】
void transfer (Entry[] newTable, boolean rehash) int newCapacity = newTable.length; for (Entry<K,V> e : table) { while (null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
1、假设线程1执行完 代码pos_1位置后，暂时挂起。此时e == e2 e.next == e3
2、线程2直接扩容完毕 ，那么完成后的状态是这样【假设e2和e3还是hash到同一个位置】
3、线程1还是原来的状态
强调一点：线程2已经扩容完毕
步骤5 目前两个线程里的新数组是这样的
为了方便后面观看，我画成这样。
步骤6 void transfer (Entry[] newTable, boolean rehash) int newCapacity = newTable.length; for (Entry<K,V> e : table) { while (null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
之前说过：假设线程1执行完 代码pos_1位置后，暂时挂起。此时e == e2 e.next == e3【也就是next == e3】
1、线程1唤醒后，继续执行pos_2，pos_3，pos_4
2、执行pos_2：意思是e2的next指针指向了线程1的新hash表【也就是newTable1】，因为newTable1是新的所以为null，
所以e2.next = null。
3、执行pos_3：newTable1[3] = e2;
4、执行pos_4： e = e3;
也就变成了下面这个样子。
步骤7 1、线程1继续执行循环
注意之前强调过线程2已经扩容完毕，那么table就已经被指向了newTable2，也就是说第二次循环时，线程1所循环的table变量就是newTable2
2、
void transfer (Entry[] newTable, boolean rehash) int newCapacity = newTable.length; for (Entry<K,V> e : table) { while (null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
1、执行pos_1：此时e == e3，那么next就是 e3.next，此时next == e2；
2、执行pos_2：经过第一轮循环，newTable1[3] == e2。那么执行完这行代码后，e3.next还是等于e2【相当于没执行】
3、执行pos_3：newTable1[3] == e3。
4、执行pos_4：e = e2
执行完，变成这样。
步骤8 线程1执行第三次循环
1、执行pos_1：next = e2.next得到 next == null。
2、执行pos_2： e.next = newTable[i] e2.next == newTable1[3]。也就是相当于 e2.next == e3
3、执行pos_3： newTable[i] = e得到 newTable1[3] == e2
这样就形成了循环链表，再get()数据就会陷入死循环。
get()源码 public V get (Object key) if (key == null ) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } private V getForNullKey () if (size == 0 ) { return null ; } for (Entry<K,V> e = table[0 ]; e != null ; e = e.next) { if (e.key == null ) return e.value; } return null ; } final Entry<K,V> getEntry (Object key) if (size == 0 ) { return null ; } int hash = (key == null ) ? 0 : 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 ; }
微信
