为什么HashMap中在链表与数组的选择时选择了数组？
因为使用链表的话访问查询会比较低（get方法），在ArrayList中可以直接使用下表来获取数据，但是链表需要一个位置一个位置遍历来查询。
在HashMap中get和put使用的频率都是非常的高的，所以我们也需要同时去保证他们的效率。
JDK 1.8 前 ： 数组 + 链表
put方法：
● 通过 key 的 hashCode 经过 扰动函数(hash()) 处理过后得到 hash 值
● 通过 (n - 1) & hash （高效的求余数的办法，相当于）判断当前元素存放的位置（n 指的是数组的长度）
● 如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同
● 如果相同的话，直接覆盖，不相同就通过 拉链法 解决冲突
源码：
* Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous（以前的） value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { // 如果table={} if (table == EMPTY_TABLE) { //初始化 inflateTable(threshold); } //查看key是否位null if (key == null) return putForNullKey(value); //对key求hash int hash = hash(key); //Returns index for hash code h. int i = indexFor(hash, table.length); //从第i个位置的table开始 该节点是否位null(是否是最后一个节点，是退出循环) for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //hash值是否相等，key是否相等。如果不相等先取到旧值，再覆盖，最后将久值返回 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; }
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); }
createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; //新建一个节点，并把它放到table的前面 //创建新节点 Entry(int h, K k, V v, Entry<K,V> n)//Creates new entry. table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } // indexFor 根据hash值计算table中的i的大小 static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }
在put开头会先判断table={}是否成立，是则对hashmap进行初始化
The next size value at which to resize (capacity * load factor). int threshold; • 1 • 2
inflateTable方法
/** * Inflates the table. */ private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }
roundUpToPowerOf2 方法
//找到一个大于或等于number的2的幂 private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; // number <= 1 , number = 1 // number > 1 时 ：number是否是大于MAXIMUM_CAPACITY，如果大于MAXIMUM_CAPACITY那么容量就等于MAXIMUM_CAPACITY。如果小于那么就先number减1，然后翻倍在求翻倍后的小于等于参数的最大2的幂的值 return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; }
highestOneBit方法 （图解）
//获取小于等于参数的最大2的幂的值 public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); }
扩容：
addEntry方法
/** * 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;//要调整大小的下一个大小值(容量负载因子) 16 * 0.75 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); }
resize方法
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //new一个新对象 容量为newCapacity Entry[] newTable = new Entry[newCapacity]; // transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
transfer方法
//Transfers all entries from current table to newTable. void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length;//新数组的容量 // 遍历桶（table） for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; //rehash if (rehash) { //key 是否为空， 是 e.hash = 0 否 再hash e.hash = null == e.key ? 0 : hash(e.key); } //算出新的数组下标 int i = indexFor(e.hash, newCapacity); //将当前的旧数组的下一个元素 指向 新数组中计算出来的对应元素中 e.next = newTable[i]; // newTable[i] = e; //将next作为数组的头部 e = next; } } }
上面的扩容时，在单线程的时候是不会出问题的，但是在多线程的情况下，会出现死锁。
hash函数
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
使用的是头插法：因为如果是尾插法需要从头部依次遍历找打最后一个元素进行插入（最后一个节点next==null），这样就需要花费时间遍历。所以1.7使用的是头插法。
get方法：
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }
getForNullKey方法
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; }
getEntry方法
//获取节点 final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } // key ==null 返回0，否则返回key的hash值 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相等 那么e就是想找的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
注意： (n - 1) & hash 相当于 hash % n， (n - 1) & hash 是一种高效的求余数的办法。在默认容量16时，&操作只需要留下最后的4位，前面的都可以舍去。 因为比8更高位的都来自于8的2次幂，所以高位的1都是可以整除8，可以直接舍弃。(只有除数是2n才可以这样的操作)
0 0 0 0 0 0 0 0 0
256 128 64 32 16 8 4 2 1
直接&8的话是不行的，假设最后四位是1XXX，那么1XXX&1000=1000，很明显对8取余得到的结果不可能是8，余数应在0到除数减一之间，所以我们需要对&7，让取余结果最大在0-7之间。这就是为什么要&(2n-1)。
