文章目录：
3.5 hash方法
在get 方法和put方法中都需要先计算key映射到哪个桶上，然后才进行之后的操作，计算的主要代码如下：
(n - 1) & hash
上面代码中的 n 指的是哈希表的大小，hash 指的是 key 的哈希值，hash是通过下面这个方法计算出来的，采用了二次哈希的方式，其中 key 的 hashCode 方法是一个native 方法：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这个 hash 方法先通过 key 的hashCode 方法获取一个哈希值，再拿这个哈希值与它的高 16 位的哈希值做一个异或操作来得到最后的哈希值，计算过程可以参考下图。
为啥要这样做呢？注释中是这样解释的：如果当 n 很小，假设为 64 的话，那么 n-1 即为63（0x111111），这样的值跟 hashCode()直接做与操作，实际上只使用了哈希值的后 6 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成冲突了，所以这里把高低位都利用起来，从而解决了这个问题。
正是因为与的这个操作，决定了 HashMap 的大小只能是 2 的幂次方，想一想，如果不是2的幂次方，会发生什么事情？即使你在创建HashMap的时候指定了初始大小，HashMap 在构建的时候也会调用下面这个方法来调整大小：
这个方法的作用看起来可能不是很直观，它的实际作用就是把 cap 变成第一个大于等于 2 的幂次方的数。
例如，16 还是 16，13 就会调整为 16，17 就会调整为 32。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
3.6 resize方法
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap 什么时候进行扩容呢？
当HashMap中的元素个数超过数组大小（数组总大小length不是数组中个数size）*loadFactor 时，就会进行数组扩容，loadFactor 的默认值
(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
在这里有一个需要注意的地方，有些文章指出当哈希表的桶占用超过阈值时就进行扩容，这是不对的；
实际上是当哈希表中的键值对个数超过阈值时，才进行扩容的。
3.7 size方法
返回map集合中键值对的个数。
public int size() { return size; }
3.8 isEmpty方法
判断map集合是否为空。
public boolean isEmpty() { return size == 0; }
3.9 clear方法
清空map集合，首先判断哈希表是否为空，为空的情况下，将size置为0，遍历哈希表依次清空每隔键值对。
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; } }
3.10 containsKey方法
判断map集合中是否包含指定的key。内部实现是调用了getNode方法，这个在上面将get方法的时候已经说过了。
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }
3.11 containsValue方法
判断map集合中是否包含指定的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) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }
将map集合中指定key对应的旧值替换为一个新值。
public V replace(K key, V value) { Node<K,V> e; if ((e = getNode(hash(key), key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; }
3.13 关于遍历map集合的三个方法
这三个方法分别是 keySet、entrySet、forEach，源码我这里就不再多说了，下面给出的是测试代码。
@Test public void test1() { Map<String,Object> map = new HashMap<>(); map.put("1001","张起灵"); map.put("1002","小哥"); map.put("1003","小宋"); System.out.println("keySet方法遍历map集合: "); Set<String> stringSet = map.keySet(); Iterator<String> iterator = stringSet.iterator(); while (iterator.hasNext()) { String key = iterator.next(); Object value = map.get(key); System.out.println("键: " + key + ", 值: " + value); } System.out.println("======================================"); System.out.println("entrySet方法遍历map集合: "); Set<Map.Entry<String,Object>> entrySet = map.entrySet(); Iterator<Map.Entry<String,Object>> entryIterator = entrySet.iterator(); while (entryIterator.hasNext()) { Map.Entry<String, Object> entry = entryIterator.next(); String key = entry.getKey(); Object value = entry.getValue(); System.out.println("键: " + key + ", 值: " + value); } System.out.println("======================================"); System.out.println("forEach方法遍历map集合: "); map.forEach((key,value) -> System.out.println("键: " + key + ", 值: " + value)); }
4.传统HashMap的缺点——引入红黑树
(1)JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
(2)当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
(3)针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。
HashMap 是数组+ 链表+红黑树（JDK1.8 增加了红黑树部分）实现的。
关于红黑树的三个关键参数。
