HashMap，非线程安全，允许使用null键和null值，这是它与HashTable的区别。
一 源码分析（基于JDK1.7）
1.属性
/** * The default initial capacity - MUST be a power of two. */
//默认的初始容量的大小为16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
//HashMap的最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */
//默认的加载因子0.75,当元素个数 >= 容量*加载因子时，就要进行扩容操作 static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * An empty table instance to share when the table is not inflated. */
//Entry类型的空数组 static final Entry<?,?>[] EMPTY_TABLE = {}; /** * The table, resized as necessary. Length MUST Always be a power of two. */
//HashMap的底层结构是数组+链表：Entry<K,V>[] transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; /** * The number of key-value mappings contained in this map. */
//元素个数 transient int size; /** * The next size value at which to resize (capacity * load factor). * @serial */ // If table == EMPTY_TABLE then this is the initial capacity at which the // table will be created when inflated.
//元素个数达到的这个值时就会进行扩容操作（扩容的临界值） int threshold; /** * The load factor for the hash table. * * @serial */
//加载因子 final float loadFactor; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
//修改次数 transient int modCount;
我们知道HashMap的底层结构是数组+链表Entry，也就是说table数组中存放的是Entry，而我们put(key,value)中的key和value存放在了Entry中，那么我们看下Entry的结构
static class Entry<K,V> implements Map.Entry<K,V> { //Entry总共有四个属性
final K key; //key V value; //value Entry<K,V> next; //指向下一个Entry的引用,所以说它是链表结构，不过是单向的 int hash; //key的hash值 /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } }
可以通过一张图来理解HashMap的结构
2.构造器
/** * 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); //给loadFactor和threshold赋值 this.loadFactor = loadFactor; threshold = initialCapacity; init(); }
3.方法
3.1 put(K key,V value):在此映射中关联指定值与指定键
对于put操作的逻辑是这样的：首先在put操作前先进行判断是否需要进行扩容操作，如果需要，扩容后同时需要重新rehash；然后根据key的hash值来获取元素在数组中的下标位置，如果该位置已经有元素OldEntry，那么新的元素newEntry顶替oldEntry的位置，然后newEntry.next = oldEntry,这时这个位置上就有了两个元素oldEntry和newEntry；如果没有，那么直接把newEntry放到数组中就行了，table[i] = newEntry。看下图：
public V put(K key, V value) {
//如果是空数组，那么给数组扩容 if (table == EMPTY_TABLE) {
//进入该方法 inflateTable(threshold); } if (key == null)
//如果key==null,则单独用这个方法处理，进入该方法 return putForNullKey(value);
//根据key获取hash值 int hash = hash(key);
//根据hash值和数组的长度获取元素将要插入数组的下标，注意：数组的长度一定是2的N次幂，这是为了减少冲突，尽可能的避免把不同的元素放到同一个数组下标里 int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k;
//如果key的hash值相等，同时key值也相等，那么直接把该key对应的value替换掉 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++;
//否则，创建一个新的Entry添加到数组中 进入该方法 addEntry(hash, key, value, i); return null; }
进入inflateTable方法
/** * Inflates the table. */ private void inflateTable(int toSize) { // Find a power of 2 >= toSize
//容量capaticy是一个大于等于toSize的最小数值，并且要满足该数值是2的N次幂这个条件 int capacity = roundUpToPowerOf2(toSize); //获取触发扩容操作的阀门值 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //创建一个长度为capacity的数组
table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative";
//Integer.highestOneNit(number) 如果number是正数，该方法返回的则是跟它最靠近的比它小的2的N次方 return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; }
进入putForNullKey方法
/** * Offloaded version of put for null keys */ private V putForNullKey(V value) {
//先查找是否存在key==null的Entry，如果存在，则直接把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++;
//如果不存在，则添加一个新的Entry，这个新Entry在table数组中的下标为0 addEntry(0, null, value, 0); return null; }
进入addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果数组中元素的个数 >= 阀门值，并且下标为bucketIndex的值不为null，那么进行扩容操作 if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容操作，将原来所有的Entry重新分配到新的数组中，需要进行rehash操作 进入该方法 resize(2 * table.length); hash = (null != key) ? hash(key) : 0;
//获取新的下标 bucketIndex = indexFor(hash, table.length); } //进入该方法 createEntry(hash, key, value, bucketIndex); }
进入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];
//将原来数组中的元素全部拷贝到新数组中，重新进行rehash transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
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); }
//根据hash值和新的数组长度重新分配Entry在数组中的位置，获取新的下标 int i = indexFor(e.hash, newCapacity);
//同一个下标位置，最新插入的元素newEntry顶替原先的oldEntry元素，table[i]指向了newEntry,newEntry.next = oldEntry,由上面那张图也可以理解 e.next = newTable[i]; newTable[i] = e; e = next; } } }
进入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++; }
3.2 remove(Object key):从此映射中移除指定键的映射关系
public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); }
final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) { return null; }
//根据key定位到该元素的下标 int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; //对于该下标下的所有元素Entry进行遍历，查找出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; }
3.3 V get(Object key):返回指定键所映射的值
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //根据key定位到下标index，然后遍历该下标下的所有Entry元素，找到键为key的Entry int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k;
//需要满足：hash值相等同时key相同，这样才能证明是同一个entry if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }