概述
HashMap是基于哈希表结构并实现了Map接口的一种数据存储结构，实现了几乎所有的Map操作，其可以允许null的value和null的key，它不以保持元素在其中的存储顺序，
HashMap有两影响其性能的参数：初始容量和负载因子，容量就是哈希表中的桶数（如果哈希函数能够完美平均分散，则可以认为，一个桶中存储一个数据元素），初始容量是创建HashMap时设置的容量，负载因子是哈希表在何时扩容的一个试题值，当哈希表中存储的数据条目超过负载因子与总容量的乘积时，需要对哈希表进行扩容，并对存储的数据进行重新散列(内部数据存储位置的重新构建)。
HashMap的实现不是线程安全的，因此在多线程环境中需要在外部对其实现同步。
数据存储结构
在HashMap中数据的存储是用数组+链表+红黑树构成的，每个数组的索引位置在注释中被称为一个hash bin，可以翻译为哈希桶，当有新元素添加的时候先通过hash函数计算出元素在数组中的桶位置，如果桶中还没有元素，直接插入新元素，如果位置上已有元素，表示hash值出现了碰撞，此时要将新元插入到此桶中链表的链尾节点，如果当桶中的元素数超过8(也就是成员变量TREEIFY_THRESHOLD)的时候，将此位置上的链表转成红黑树进行存储。
?
成员变量
// 存储键值对的节点数组，在下提到容量时，都是指table变量的长度，即table.length
transient Node<K,V>[] table;
?
// TODO
transient Set<Map.Entry<K,V>> entrySet;
// 在哈希表中存储的键值对的个数
transient int size;
// 容量不够用时需要扩容的一个阀值，其值=容量*负载因子
int threshold;
// 负载因子
final float loadFactor;
?
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量，没有指定时使用此值
// 最大容量，这个值跟DEFAULT_INITIAL_CAPACITY值都是2的幂，凡是涉及到HashMap容量的时候，其值必为2的幂
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认负载因子值为0.75
static final int TREEIFY_THRESHOLD = 8;// 当链表的值超过8则会转红黑树
static final int UNTREEIFY_THRESHOLD = 6;// 当链表的值小于6则会从红黑树转回链表构造函数
// 默认构造，将负载因子设置为默认值
public HashMap() {
? ?this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 给定容量的初始化方法，负载因子使用默认值
public HashMap(int initialCapacity) {
? ?this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 用给定容量和负载因子进行初始化
public HashMap(int initialCapacity, float loadFactor) {
? ?if (initialCapacity < 0)// 容量不能小于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);// 计算容量阀值，并设置
}
?
// 该方法将给定的cap值，最终转成一个2的幂的值，例如3会转成4，7会转为8，10转成16
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;
? ?// 调整容量值，使其值在0到MAXIMUM_CAPACITY之间
? ?return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}?
构造函数中的默认构造函数将负载因子初始化为默认值0.75，此构造函数没有指定具体容量，将在添加元素时，将容量调整为默认大小16
也可以通过指定容量的构造函数，给HashMap指定一个容量，这时负载因子使用默认值0.75，
也可能即指定容量也指定自定义的负载因子。
添加元素
public V put(K key, V value) {
? ?return putVal(hash(key), key, value, false, true);
}
// 计算key的哈希值
static final int hash(Object key) {
? ?int h;
? ?return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
?
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
? ? ? ? ? ? ? boolean evict) {
? ?Node<K,V>[] tab; Node<K,V> p; int n, i;
? ?if ((tab = table) == null || (n = tab.length) == 0)// 如果原哈希表中没有元素
? ? ? ?n = (tab = resize()).length;// 重新调整大小，并记录调整后的大小
? ?// 如果此散列位置上的值为null，新建元素节点存储到该位置
? ?if ((p = tab[i = (n - 1) & hash]) == null)
? ? ? ?tab[i] = newNode(hash, key, value, null);
? ?else {
? ? ? ?Node<K,V> e; K k;
? ? ? ?// 如果新元素的hash值与此位置上的第一个元素的值相等，且key值也相等，说明新元素要要替换此位置上的元素，记录下此元素
? ? ? ?if (p.hash == hash &&
? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ?e = p;
? ? ? ?// 如果此位置上的元素是以红黑树形式存储的，
? ? ? ?else if (p instanceof TreeNode)
? ? ? ? ? ?// putTreeVal的功能是在红黑树中查找与新元素的key相等的节点，如果存在则返回该节点，如果不存在则直接在红黑树中插入，插入完成后，返回null值
? ? ? ? ? ?e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
? ? ? ?else {
? ? ? ? ? ?// 遍历hash位置上的链表
? ? ? ? ? ?for (int binCount = 0; ; ++binCount) {
? ? ? ? ? ? ? ?if ((e = p.next) == null) {//到达了链表尾
? ? ? ? ? ? ? ? ? ?p.next = newNode(hash, key, value, null);// 构建一个新节点，做为尾节点的后继
? ? ? ? ? ? ? ? ? ?// 如果当前hash位置上的链表中元素数大于等于了树形化阀值，对该hash位置进行红黑树转化
? ? ? ? ? ? ? ? ? ?if (binCount >= TREEIFY_THRESHOLD - 1)
? ? ? ? ? ? ? ? ? ? ? ?treeifyBin(tab, hash);
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?// 遍历的当前元素与新元素的hash和key都相等，直接退出遍历
? ? ? ? ? ? ? ?if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ?p = e;
? ? ? ? ? }
? ? ? }
? ? ? ?// e != null 表示新元素的key在哈希表中有相应的元素，用新元素的值替换掉旧元素
? ? ? ?if (e != null) {
? ? ? ? ? ?V oldValue = e.value;
? ? ? ? ? ?if (!onlyIfAbsent || oldValue == null)
? ? ? ? ? ? ? ?e.value = value;
? ? ? ? ? ?afterNodeAccess(e);
? ? ? ? ? ?return oldValue;
? ? ? }
? }
? ?++modCount;
? ?if (++size > threshold)//元素个数加1，如果大于扩容阀值，进行扩容
? ? ? ?resize();
? ?afterNodeInsertion(evict);
? ?return null;
}
?
final Node<K,V>[] resize() {
? ?Node<K,V>[] oldTab = table;
? ?int oldCap = (oldTab == null) ? 0 : oldTab.length;// 原容量
? ?int oldThr = threshold;// 原扩容阀值
? ?int newCap, newThr = 0;
? ?if (oldCap > 0) {// 如果原容量大于0
? ? ? ?if (oldCap >= MAXIMUM_CAPACITY) {// 大于最大容量阀值时
? ? ? ? ? ?threshold = Integer.MAX_VALUE;// 设置扩容阀值为整型值的最大值后，直接返回原容量值
? ? ? ? ? ?return oldTab;
? ? ? }
? ? ? ?// 新容量扩大两倍，如果仍在最大容量阀值和默认容量之间，使扩容阀值扩大两倍
? ? ? ?else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
? ? ? ? ? ? ? ? oldCap >= DEFAULT_INITIAL_CAPACITY)
? ? ? ? ? ?newThr = oldThr << 1; // double threshold
? }
? ?else if (oldThr > 0) // 如果原扩容阀值大于0，仍使用原阀值
? ? ? ?newCap = oldThr;
? ?else {// 使用默认容量，扩容阀值使用 默认容量乘以加载因子
? ? ? ?newCap = DEFAULT_INITIAL_CAPACITY;
? ? ? ?newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
? }
? ?if (newThr == 0) {
? ? ? ?float ft = (float)newCap * loadFactor;
? ? ? ?newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
? ? ? ? ? ? ? ? (int)ft : Integer.MAX_VALUE);
? }
? ?threshold = newThr;// 设置计算后新的扩容阀值
? ?@SuppressWarnings({"rawtypes","unchecked"})
? ?Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 扩容，用新的容量值重新分配数组空间
? ?table = newTab;
? ?if (oldTab != null) {// 原哈希表中有数据
? ? ? ?// 下面的代码将原hashmap中的元素重新散列到扩容后的新hashmap中
? ? ? ?for (int j = 0; j < oldCap; ++j) {
? ? ? ? ? ?Node<K,V> e;
? ? ? ? ? ?if ((e = oldTab[j]) != null) {
? ? ? ? ? ? ? ?oldTab[j] = null;
? ? ? ? ? ? ? ?if (e.next == null)
? ? ? ? ? ? ? ? ? ?newTab[e.hash & (newCap - 1)] = e;
? ? ? ? ? ? ? ?else if (e instanceof TreeNode)
? ? ? ? ? ? ? ? ? ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
? ? ? ? ? ? ? ?else {
? ? ? ? ? ? ? ? ? ?Node<K,V> loHead = null, loTail = null;
? ? ? ? ? ? ? ? ? ?Node<K,V> hiHead = null, hiTail = null;
? ? ? ? ? ? ? ? ? ?Node<K,V> next;
? ? ? ? ? ? ? ? ? ?do {
? ? ? ? ? ? ? ? ? ? ? ?next = e.next;
? ? ? ? ? ? ? ? ? ? ? ?if ((e.hash & oldCap) == 0) {
? ? ? ? ? ? ? ? ? ? ? ? ? ?if (loTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?loHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?loTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ?loTail = e;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ?else {
? ? ? ? ? ? ? ? ? ? ? ? ? ?if (hiTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?hiHead = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?hiTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ?hiTail = e;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? } while ((e = next) != null);
? ? ? ? ? ? ? ? ? ?if (loTail != null) {
? ? ? ? ? ? ? ? ? ? ? ?loTail.next = null;
? ? ? ? ? ? ? ? ? ? ? ?newTab[j] = loHead;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?if (hiTail != null) {
? ? ? ? ? ? ? ? ? ? ? ?hiTail.next = null;
? ? ? ? ? ? ? ? ? ? ? ?newTab[j + oldCap] = hiHead;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
? }
? ?return newTab;
}从上面方法调用过程中可总结出，HashMap添加新元素时的逻辑：
-
计算key的hash值，查找到新元素需要插入的桶的位置
-
如果table的数据为0或者table为null时，先将HashMap扩容，然后直接将新元素插入到对应的桶位置
-
如果hash值对应的桶中没有元素，抖将新元素插入到桶的第一个位置
-
如果hash位置上的桶有元素，遍历桶上的元素，如果有与新元素的key相等的，说明是相更新数据，直接替换新元素的value，如果没有元素与新元素的key值相等，则插入新元素，并将元素数量加1
删除元素
public V remove(Object key) {
? ?Node<K,V> e;
? ?return (e = removeNode(hash(key), key, null, false, true)) == null ?
? ? ? ?null : e.value;
}
?
final Node<K,V> removeNode(int hash, Object key, Object value,
? ? ? ? ? ? ? ? ? ? ? ? ? boolean matchValue, boolean movable) {
? ?Node<K,V>[] tab; Node<K,V> p; int n, index;
? ?// 如果当前hash位置p上的桶中有节点
? ?if ((tab = table) != null && (n = tab.length) > 0 &&
? ? ? (p = tab[index = (n - 1) & hash]) != null) {
? ? ? ?Node<K,V> node = null, e; K k; V v;
? ? ? ?// 如果桶中的第一个节点的key与要删除的key相等，则它就是要删除的节点
? ? ? ?if (p.hash == hash &&
? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ?node = p;
? ? ? ?else if ((e = p.next) != null) {// 如果桶中还有其它节点
? ? ? ? ? ?if (p instanceof TreeNode)// 桶中是以红黑树形式存储
? ? ? ? ? ? ? ?node = ((TreeNode<K,V>)p).getTreeNode(hash, key);// 从红黑树中找到节点
? ? ? ? ? ?else { // 否则则是以链表存储，对链表进行遍历，找到与要删除key相等的节点
? ? ? ? ? ? ? ?do {
? ? ? ? ? ? ? ? ? ?if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ? ((k = e.key) == key ||
? ? ? ? ? ? ? ? ? ? ? ? (key != null && key.equals(k)))) {
? ? ? ? ? ? ? ? ? ? ? ?node = e;
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?p = e;
? ? ? ? ? ? ? } while ((e = e.next) != null);
? ? ? ? ? }
? ? ? }
? ? ? ?// 如果找到节点node，并且不要求删除value值也相等的节点
? ? ? ?if (node != null && (!matchValue || (v = node.value) == value ||
? ? ? ? ? ? ? ? ? ? ? ? ? ? (value != null && value.equals(v)))) {
? ? ? ? ? ?if (node instanceof TreeNode)// 如果节点在红黑树上，从树上删除节点
? ? ? ? ? ? ? ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
? ? ? ? ? ?else if (node == p)// 如果节点是根节点，将根节点的后继设置为当前桶的新根节点
? ? ? ? ? ? ? ?tab[index] = node.next;
? ? ? ? ? ?else// 不是根节点，将node节点的后继设置为p的后继
? ? ? ? ? ? ? ?p.next = node.next;
? ? ? ? ? ?++modCount;
? ? ? ? ? ?--size;// 元素个数减1
? ? ? ? ? ?afterNodeRemoval(node);
? ? ? ? ? ?return node;// 返回删除的节点
? ? ? }
? }
? ?return null;
}删除的过程就比较简单了，
-
通过key的hash值定位到要删除的元素所在桶的位置
-
根据桶中数据存储的形式，对红黑树或者链表进行遍历，找到与要删除的key相等的元素
-
判断删除时是否也要求value值相匹配，如是要求匹配，则还要判断value值是否相等，然后再决定是否删除找到元素
-
根据找到的节点的数据存储形式，在红黑树中或者链表中删除节点
-
最后返回要删除的节点，如果不有找到匹配的节点则返回null