HsahMap继承了AbstractMap，实现了三个接口：Map、Clonealbe、Serializable
一、成员变量：
1、
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
初始化的容量，默认为16，值得注意的是注释中的后一句：必须为2的倍数---为什么必须是2的倍数呢，这个和HashMap的哈希算法有关，详见四、重要方法
2、/**
* 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.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
最大的容量，hashmap中的值必须小于2^30，且必须为2的倍数
3、/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
载入因子，默认为0.75，这个和扩容相关
4、/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
链表转树的值，必须是大于2且小于8
5、/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表
6、/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
在转变成树之前，还会有一次判断，只有键值对数量大于64才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
7、/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
存储元素的数组，总是2的倍数，Node是内部类
8、/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
9、
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
存放元素的个数
10、/**
* 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;
每次扩容和更改map结构的计数器
11、/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
12、/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
加载因子
二、HashMap的构造方法
1、int + float双参数构造方法
/**
* 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;
this.threshold = tableSizeFor(initialCapacity);
}
参数是初始容量以及加载因子
这个构造方法里面有个tableSizeFor(initialCapacity)方法，返回的是最接近且大于等于initialCapacity的2次幂的值，大道至简的算法，膜拜。。贴下代码
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
主要是利用了右移和或操作，刚开始的cap-1是为了将2、4、8这种二次幂考虑进去，如果不减一的话，8这种2次幂算出来的值为16，不符合我们的要求。
2、单int构造方法
/**
* 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);
}
默认加载因子是0.75
3、无参构造方法
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
4、带有初始化集合的构造方法
/**
* 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
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
三、静态内部类
1、Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
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;
}
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;
}
}
比较简单，单向链表
2、TreeNode
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode extends LinkedHashMap.Entry
一个TreeNode代表红黑树的一个节点
五个成员变量
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; //用来删除下一个节点用的，因此prev也就是上一个节点
boolean red;
四、重要方法
1、/**
* 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) {
return putVal(hash(key), key, value, false, true);
}
比较重要的是putVal
hash(key)这个方法主要是两步，首先调用native的hashcode方法，得到结果h,之后将h右移16位，再与h进行与运算，得到hash值
putVal里面有一个比较重要的条件判断if ((p = tab[i = (n - 1) & hash]) == null)意思是判断节点是否存在：
(1) 不存在就新建一个节点，那么如何判断这个节点是否存在的呢？这里使用的是(n - 1) & hash，其中n是整个HashMap的大小，hash值是上一步hash(key)得到的值，看了几篇博客，都将说是二次幂-1之后低位都是1，然后与之后高位为0，低位为1，然后举例子，巴拉巴拉。。。其实简单理解这就是将hash对二次幂取余的过程，且只有当n为二次幂时(n - 1) & hash才是hash对n取余，为了保证算法的高效性，将HashMap的容量都设为二次幂。
(2) 如果存在的话，首先判断下面两个条件是否成立
a、当前节点的hash值与入参的hash值是否相等
b、当前节点的Key与入参的key相同 或者 入参key不为null而且key.equals（当前节点的k）
如果两个都成立的话，替换当前的节点
如果有一个条件不成立，判断当前节点是否为树形节点，如果是树形节点，执行树形节点的方法
如果不为树形节点，判断当前节点是否大于等于7，大于等于7 调用treeifyBin()方法
2、/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node[] tab, int hash)
判断当前tab的大小是否小于MIN_TREEIFY_CAPACITY，最小树化的临界值，小于的话就执行resize方法
大于的话执行树形化
