数据结构
数组+链表+红黑树数组：ArrayList链表：LinkedList 单向链表 Node{pred(上一个) item(元素) next(下一个)}红黑树：jdk8链表长度达到8，转为红黑树
成员变量
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//序列号，序列化的时候使用。
private static final long serialVersionUID = 362498820763181265L;
/**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，2的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子，用于扩容使用。
//为啥是0.75？提高空间利用率和减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小，
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当某个桶节点数量大于8时，会转换为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
static final int UNTREEIFY_THRESHOLD = 6;
//当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
static final int MIN_TREEIFY_CAPACITY = 64;
//存储元素的数组，transient关键字表示该属性不能被序列化
transient Node<K,V>[] table;
//将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
transient Set<Map.Entry<K,V>> entrySet;
//元素数量
transient int size;
//统计该map修改的次数
transient int modCount;
//临界值，也就是元素数量达到临界值时，会进行扩容。
int threshold;
//也是加载因子，只不过这个是变量。
final float loadFactor;
为什么默认容量大小为16，加载因子为0.75，
主要原因是这两个常量的值都是经过大量的计算和统计得出来的最优解，仅仅是这样而已。
内部类
//使用静态内部类，是为了方便调用，而不用每次调用里面的属性或者方法都需要new一个对象。红黑树的结构。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
//结点内部类，是一个单向链表。这两个内部类再加上之前的Node<K,V>[] table属性，
//组成了hashMap的结构，哈希桶。
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;
}
}
构造方法
//空参构造，使用默认的加载因子0.75。但它还是空的，put的时候才扩容到16
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)
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);
}
//传入一个Map，然后把该Map转为hashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取该map的实际长度
int s = m.size();
if (s > 0) {
//判断table是否初始化，如果没有初始化
if (table == null) { // pre-size
/**求出需要的容量，因为实际使用的长度=容量*0.75得来的，+1是因为小数相除，基本都不会是整数，容量大小不能为小数的，后面转换为int，多余的小数就要被丢掉，所以+1，例如，map实际长度22，22/0.75=29.3,所需要的容量肯定为30，有人会问如果刚刚好除得整数呢，除得整数的话，容量大小多1也没什么影响**/
float ft = ((float)s / loadFactor) + 1.0F;
//判断该容量大小是否超出上限。
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
/**对临界值进行初始化，tableSizeFor(t)这个方法会返回大于t值的，且离其最近的2次幂，例如t为29，则返回的值是32**/
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果table已经初始化，则进行扩容操作，resize()就是扩容。
else if (s > threshold)
resize();
//遍历，把map中的数据转到hashMap中。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
put(K key, V value)
public V put(K key, V value) {
//四个参数，第一个hash值，第四个参数表示如果该key存在值，如果为null的话，则插入新的value，
//最后一个参数，在hashMap中没有用，可以不用管，使用默认的即可
return putVal(hash(key), key, value, false, true);
}
//key的hashCode，^ hashCode除以2的16次方
static final int hash(Object key) {
int h;
//先获取到key的hashCode，然后进行移位再进行异或运算，
//为什么这么复杂，是为了减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//判断数组长度，初始化数组，也就是创建HashMap的时候，长度是0
//当第一次put的时候，才对它给予长度，进行resize()操作
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果数组不为空，进行运算，用于确定在数组中的位置
//n是数组大小，(16 - 1) & hash
//15的二进制是00001111，& hash
//结果必定是在0000-1111范围内,那么肯定在0-15之间
//为什么用&，不用%，因为&运算速度最快。
//如果，tab[index] == null，那么则占据这个下标位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/**
* newNode源码，就是返回一个新的Node元素
* Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
* return new Node<>(hash, key, value, next);
* }
*/
else {
//说明该位置，已有其他元素，那么则区分3中情况，正好对应下面的if和else
Node<K,V> e; K k;
//1.key相同(hash冲突)，直接覆盖
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.key不相同，红黑树结构插入
else if (p instanceof TreeNode)
//为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），
//该值很重要，用来判断put操作是否成功，如果添加成功返回null
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//3.key不相同，链表结构插入
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//如果链表中的某个元素下一个指向为null(说明它是最后一个)
if ((e = p.next) == null) {
//将其插入到尾部
p.next = newNode(hash, key, value, null);
//如果遍历的次数，大于(8-1)，那么就说明链表的长度达到了8
if (binCount >= TREEIFY_THRESHOLD - 1)
//将链表转为红黑树
treeifyBin(tab, hash);
break;
}
//和上面一样，做了一次判断，hash冲突覆盖，老值被覆盖，返回老值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//上面的e不为空，有重复的key，则用待插入值进行覆盖，返回旧值。
if (e != null) {
//将老的值获取，用于返回
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null
//操作次数
++modCount;
//size元素个数，threshold数组长度，threshold计算方式是 长度 * 负载因子(0.75) 的一个值
//也就是假设长度是16，他不会等到真正达到16才去扩容，他会用16*0.75=12，用12来作为判定扩容标准
//如果元素个数，大于数组的长度，需要扩容
if (++size > threshold)
resize();//初始化/扩容
afterNodeInsertion(evict);
return null;
}
resize()
//这里是双倍扩容，假如原来长度是16，那么一定会扩容到32
//原因是为了保证长度一定是2的N次方，减少哈希碰撞
final Node<K,V>[] resize() {
//把没插入之前的哈希数组做我诶oldTab
Node<K,V>[] oldTab = table;
//如果数组为null，返回0(初次)，否则返回数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//old的临界值
int oldThr = threshold;
//初始化new的长度和临界值
int newCap, newThr = 0;
//oldCap > 0也就是说不是首次初始化
if (oldCap > 0) {
//判断数组长度有没有超过最大限度，也就是2的30次方(1 << 30)
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
//如果超过了，那就直接返回了，不扩容了。
return oldTab;
}
//如果还可以扩容，那么使用位移运算
//运算：数组长度 << 1(数组长度 * 2)，那么长度*2 必须小于 最大限度
//并且：数组长度 >= 2的16次方(也就是默认的长度 1 << 4 = 1 * 2的4次方)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//当然这里对threshold 长度*负载因子 也是要扩容的
//假设以前是12，那么12 << 1 = 12 * 2 = 24 也是双倍扩容
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // oldCap为0，使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;//大小16赋值给newCap变量
//0.75 * 16 = 12 赋值给newThr
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//初始化时容量小于默认值16的，此时newThr没有赋值
if (newThr == 0) {
//new的临界值
float ft = (float)newCap * loadFactor;
//判断是否new容量是否大于最大值，临界值是否大于最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//把上面各种情况分析出的临界值，在此处真正进行改变，也就是容量和临界值都改变了。
threshold = newThr;
//对数组进行赋值，newCap是大小
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//这里对新建的空数组，以及将以前的未扩容的数组合并
//并且根据新长度，对以前的数据和新插入的数据，全部重新计算位置
if (oldTab != null) {//如果数组不为空，遍历
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//将该位置元素赋值给e，如果该位置上已有其他元素
//因为要进行元素搬家，如果该位置为空，没有必要对其操作
if ((e = oldTab[j]) != null) {
//将该位置置为null
oldTab[j] = null;
//如果老元素e的下一个节点为null，说明只有一个Node
if (e.next == null)
//重新进行计算，重新分配位置
//这里计算是用的newCap，也就是新的长度，比如从16扩容到32
//那就是e.hash & (32 - 1)
//计算后将e赋值进去
newTab[e.hash & (newCap - 1)] = e;
//判断是不是红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//否则就是链表
else {
//此处表示为链表结构，同样把链表转移到newCap中，
//就是把链表遍历后，把值转过去，在置位null
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//这里的运算，不是e.hash & (长度 - 1)了，而是e.hash & 长度
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;
}
}
}
}
}
//返回扩容后的hashMap
return newTab;
}
remove(Object key)
public V remove(Object key) {
//临时变量
Node<K,V> e;
//调用removeNode(hash(key), key, null, false, true)进行删除，
//第三个value为null，表示，把key的节点直接都删除了，不需要用到值，
//如果设为值，则还需要去进行查找操作
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
//第一参数为哈希值，第二个为key，第三个value，
//第四个为是为true的话，则表示删除它key对应的value，不删除key
//第四个如果为false，则表示删除后，不移动节点
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标
Node<K,V>[] tab; Node<K,V> p; int n, index;
//哈希数组不为null，且长度大于0，然后得到要删除key的节点所在是数组下标位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value
Node<K,V> node = null, e; K k; V v;
//如果数组下标的节点正好是要删除的节点，把值赋给临时变量node
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 { //表示为链表节点，一样的遍历找到该节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
/**注意，如果进入了链表中的遍历，那么此处的p不再是数组下标的节点，而是要删除结点的上一个结点**/
p = e;
} while ((e = e.next) != null);
}
}
//找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true
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 /**为链表结构，删除的节点在链表中，把要删除的下一个结点设为上一个结点的下一个节点**/
p.next = node.next;
//修改计数器
++modCount;
//长度减一
--size;
/**此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理**/
afterNodeRemoval(node);
//返回删除的节点
return node;
}
}
//返回null则表示没有该节点，删除失败
return null;
}
get(Object key)
public V get(Object key) {
Node<K,V> e;
//也是调用getNode方法来完成的
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//first 头结点，e 临时变量，n 长度,k key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//头结点也就是数组下标的节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果是头结点，则直接返回头结点
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//不是头结点
if ((e = first.next) != null) {
//判断是否是红黑树结构
if (first instanceof TreeNode)
//去红黑树中找，然后返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { //链表节点，一样遍历链表，找到该节点并返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//找不到，表示不存在该节点
return null;
}
HashMap与Hashtable的区别
1、线程安全
Hashtable 是线程安全的，HashMap 不是线程安全的。因为Hashtable的操作是synchronized修饰的。
2、性能优劣
既然 Hashtable 是线程安全的，每个方法都要阻塞其他线程，
所以 Hashtable 性能较差，HashMap 性能较好，使用更广。
3、NULL
Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
因为value为null会抛出空指针异常。
而key为null，因为它要计算数组位置，key.hashCode();相当于null.hashCode();肯定会报错的。
HashMap对null做了特殊处理，key为null，hashcode会返回0，value则没有限制。
4、实现方式
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
可以看出两者继承的类不一样，Hashtable继承了Dictionary类，而HashMa继承的是AbstractMap类。
5、容量扩容
HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
当现有容量大于总容量*负载因子时，HashMap扩容规则为当前容量翻倍，
Hashtable扩容规则为当前容量翻倍 + 1。
6、迭代器
HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
所以，当其他线程改变了HashMap 的结构，如：增加、删除元素，
将会抛出 ConcurrentModificationException 异常，而 Hashtable 则不会。
若有收获，就点个赞吧
0 人点赞
