其他
别慌，我带你来读读HashMap源码，就明白了...
以下文章来源于Java剑主 ，作者Java剑主
1.HashMap不同步的，也就是非线程安全
多线程下进行结构修改需要在外部进行同步操作，改变已经关联的键值不是结构修改，
如果不存在此类对象，则应使用Map m = Collections.synchronizedMap
2.允许存在null键null值，只能允许一个，因为key是不能重复的
3.HashMap存入的顺序和遍历的顺序有可能是不一致的
4.影响HashMap性能的来个只要因素：初试容量、负载因数
5.返回的迭代器是fail-fast机制的
6.快速失败机制
7.不能保证迭代器的快速故障行为，迭代器的快速故障行为应该只用于检测bug
8.保存数据的时候通过计算key的hash值来去决定存储的位置。
9.hash桶结构（数组和链表（或树形结构）组成）-拉链式散列算法
10.红黑树
11.序列化机制：通过实现readObject/writeObject两个方法自定义序列化内容
12.进制转换
13.位运算
二、进一步的了解：
1.HashMap是Map接口的一个实现，属于映射型的哈希表(散列表)，存储key-value键
值对，允许存储null值的键值对，非同步的(非线程安全)。
2.HashMap是将Key做Hash算法,然后将 Hash值映射到内存地址,直接取得 Key所对应
的数据，hash算法是不可逆的，且具唯一性。
3.key不能重复，且HashMap是按照哈希值存储，HashMap的遍历输出是随机无序的
也就是数据存放进去和取出来的顺序是不一样的。
4.HashMap存值的时候会根据key的hashCode()来计算存储的位置(位置是散列的，所
以说其无序)。
5.对于存进去Map的一组数据，在没有外界影响的情况下(没有元素的取用，查找不算)，
不会调用Hash算法，所以数据的顺序也是不会变的。
6.HashMap的存储结构是由数组+链表+红黑树的形式来组成散列桶，桶的每一个节点
都为链表的头节点或者树的根节点，采用链地址法来进行对象的存储，
先根据key的hashCode()方法在散列桶(数组)中进行寻址找到具体位置(bucket)，
7.该具体位置就是一个链表结构，调用keys.equals()方法找到key对象的value节点，
如果该位置链表结构的节点超过8，就将该位置的链表转化为红黑树结构来进行存储，
时间复杂度：O(logN)。
8.HashMap根据key的hashCode值生成数组下标，通过内存地址直接查找，没有任何
的判断，时间复杂度和数组相同，都是需要更多的空间，以空间换时间。
第三步：对HashMap有了进一步的了解之后，可能会有还意犹未尽的感觉，继续
摸索：
三、再进一步的了解：
1.HashMap的底层基本性能操作：get与put。
2.哈希函数将元素适当地分散到桶中，迭代所需时间与HashMap实例(桶的数量)和本身
大小(键值映射对的数量)有关，因此，不设置初始值是非常重要的，如果迭代性能过高，
则容量过高(或负载因子过低)重要。
3.load factor(负载因子)是一个衡量哈希表允许有多满的指标，该指标在容量自动增加
之前获取
4.初试容量为创建哈希表时定义的容量，当哈希表的大小超过了当前的容量和负载因子
，就会利用rehash进行扩容操作。
5.碰撞冲突：两个相同的Key被分配到相同的桶bucket里面，哈希冲突并不会导致
HashMap覆盖一个已经存在于集合中的元素，这种情况只会在使用者试图向集合中放
入两个元素，并且它们的键对于 equal()方法是相等的时候才会发生。
6.默认的负载因子(0.75)提供了一个很好的选择，权衡时间和空间成本。值越高，空间
开销，但增加查找成本(反映在大多数HashMap类的操作，包括get， put)。
7.键不相等但又会产生哈希冲突的不同元素最终会以某种数据结构存储在 HashMap的
同一个桶中肯定会降低HashMap的性能，可以使用Comparable接口进行比较来打破
该僵局。
8.迭代器的快速故障行为应该只用于检测bug。
9.capacity： 源码中没有将它作为属性，但是为了方便，引进了这个概念，是指
HashMap中桶的数量。默认值为16。
文字有点多，划个线。。。（做完这三步，如果有哪些疑惑，我就会从源码中去分析了。。。）
好了，学习方法，就说到这里，有更好的建议欢迎和我交流！！！
/** * 阅读源码前，需要对如下有熟悉 * 关键字：static、final、transient、instanceof * 运算符：<< 、 ^ 、 >>> 、 |= * * 回顾基础： * * static： * 1.被static修饰的变量或者方法是独立于该类的任何对象，也就是说，这些变量和方法不属于任何一个实例对象，而是被类的实例对象所共享，而非静态变量是对象所拥有的。 * 2.在类被加载的时候，就会去加载被static修饰的部分。 * 3.被static修饰的变量或者方法是优先于对象存在的，也就是说当一个类加载完毕之后，即便没有创建对象，也可以去访问。 * 4.static方法就是没有this的方法 * 5.在static方法内部不能调用非静态方法 * 6.在静态方法中不能访问非静态成员方法和非静态成员变量，因为非静态成员方法/变量都是须依赖具体的对象才能够被调用。但是在非静态成员方法中是可以访问静态成员方法/变量的。 * 7.static关键字并不会改变变量和方法的访问权限，静态成员变量虽然独立于对象，但是不代表不可以通过对象去访问，所有的静态方法和静态变量都可以通过对象访问（只要访问权限足够）。 * 8.static是不允许用来修饰局部变量。 * 9.static修饰的属性和方法，使用类名.xx的形式访问。 * 10.使用的位置：那些不需要通过创建对象就可以访问方法的情况。 * * * final: * 1.修饰类当用final去修饰一个类的时候，表示这个类不能被继承。 * 2.被final修饰的类，final类中的成员变量可以根据自己的实际需要设计为fianl。 * 3.final类中的成员方法都会被隐式的指定为final方法。 * 4.被final修饰的方法不能被重写。 * 5.一个类的private方法会隐式的被指定为final方法。 * 6.如果父类中有final修饰的方法，那么子类不能去重写。 * 7.修饰成员变量必须要赋初始值，而且是只能初始化一次。 * 8.修饰成员变量必须初始化值。被fianl修饰的成员变量赋值，有两种方式：1、直接赋值 2、全部在构造方法中赋初值。 * 9.如果修饰的成员变量是基本类型，则表示这个变量的值不能改变。 * 10.如果修饰的成员变量是一个引用类型，则是说这个引用的地址的值不能修改，但是这个引用所指向的对象里面的内容还是可以改变的。 * * * transient: * 1.在已序列化的类中使变量不序列化——在已实现序列化的类中，有的变量不需要保存在磁盘中，就要transient关键字修饰. * 2.transient只能修饰成员变量，不能修饰方法。 * * instanceof： * 在运行时指出的对象是否是特定类的一个实例 * * <<（左移位运算） ：(>>：则反过来) * 1<<2 = 2 、 1 << 3 = 8 、1 << 4 = 16 ...... * 20的二进制补码：0001 0100 * 向左移动两位后：0101 0000 》》》 20 << 2 * * * ^(异或运算符)： * 5^9 = 12 》》》 5的二进制位是0000 0101 ， 9的二进制位是0000 1001，也就是0101 ^ 1001,结果为1100，00001100的十进制位是12 * * >>>（无符号右移运算符）： * 无符号右移运算符和右移运算符的主要区别在于负数的计算，因为无符号右移是高位补0，移多少位补多少个0。 * 15的二进制位是0000 1111 ， 右移2位0000 0011，结果为3 * * * |=（运算符，先计算|再=）： * n|=n>>>2 》》》 n=n|(n>>>2)=1000100|0010001=1010101 * */
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L; //版本序列号
/** * 文本翻译： * * 实现注意事项： * * 1.桶上的红黑树主要是按hashCode排序，如果来个元素相同，则通过compareTo方法进行比较排序。 * 2.当普通节点数大于TREEIFY_THRESHOLD时，就会进行大小调整成红黑树结构，树节点的大小大约是普通节点的两倍，当树节点太小的时候也会转换为普通节点大小。 * 3.默认大小调整的参数平均约为0.5，阈值为0.75忽略方差，得到期望列表大小k的出现次数为(exp(-0.5) * pow(0.5, k) / factorial (k))。第一个值是: * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million * * 4.树的根节点为第一个节点，如果该节点被删除，可以通过TreeNode.root()方法来恢复根节点。 * 5.所有适用的内部方法都接受哈希码作为参数(通常由公共方法提供)，允许在不重新计算用户哈希码的情况下相互调用。大多数内部方法也接受“tab”参数，也就是说通常是当前表，但可能是新表或旧表时调整大小或转换 * 6.当bin列表被treeified、split或untreeified时，我们保存以相同的相对存取/遍历次序(即、现场为了更好地保存局部，并稍微简化对调用的分割和遍历的处理iterator.remove。 * 7.当使用比较器插入时，要保持跨区域的总排序(或与此处所需的最接近)rebalancings，我们将类和identityhashcode进行比较参加。 * 8.在普通模式和树模式之间的使用和转换是由于LinkedHashMap子类的存在而变得复杂。看到下面是定义在插入时调用的钩子方法，删除和访问允许LinkedHashMap内部文件否则独立于这些机制。 * 9.这也要求将映射实例传递给一些实用程序方法可能会创建新节点。 * 10.基于并行编程的类似于ssa的编码风格很有帮助避免所有扭曲指针操作中的混叠错误。 * */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量—必须是2的幂。值为16。 static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量限制：2的30次方 static final float DEFAULT_LOAD_FACTOR = 0.75f; //构造函数中没有指定时，默认使用的负载因子= 0.75f
static final int TREEIFY_THRESHOLD = 8; //当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int UNTREEIFY_THRESHOLD = 6; //当桶(bucket)上的结点数小于这个值时树转链表，前提是它当前是红黑树结构。
static final int MIN_TREEIFY_CAPACITY = 64; //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
//单向链表，每个节点都存有hash值，key-value，next指针。 static class Node<K,V> implements 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; }
//重写方法，返回对该节点元素计算出来的hashCode。 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
//允许为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) { Entry<?,?> e = (Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
//计算key的hash码 /* ---------------- Static utilities -------------- */ static final int hash(Object key) { int h; //哈希码 /** * 如果key==null哈希值就返回0，否则就计算出前的key的哈希码与哈希码无符号右移16位，后移的每一个位置都补零，接着进行异或（掩码），得出该key的哈希码 * 计算key.hashCode()并传播(XORs)更高的散列位，因为表使用的是2的幂掩码，所以是只在当前掩码上方的位上变化的散列会总是发生碰撞。 * 高16位与低16位异或来减少这种碰撞影响，这样操作与table下标的计算有关：n = table.length; index = （n-1） & hash; * table的长度都是2的幂，因此index仅与hash值的低n位有关（此n非table.leng，而是2的幂指数），hash值的高位都被与操作置为0了。 * *【1】计算过程： * *16的二进制为：10000 *15的二进制为：1111 * *假如有这两个对象的hashCode: *对象A：1000010001110001000001111000000 *两个数进行与异或 *对象B：0111011100111000101000010100000 *15与对象A和对象B进行异或后的结果进行&操作后结果都是0 *解决方法： *1.将hashCode右移16位，也就是取int类型的一半，刚好将二进制数对半切开，然后使用异或。（如果两个数对应的位置相反，则结果为1，反之为0），这样就能避免上面的情况发生。 * *在一些极端情况下还是有问题，比如： *10000000000000000000000000 和 1000000000100000000000000 *这两个数，如果数组长度是16，那么即使右移16位，再异或，hash值还是会重复。但是为了性能，对这种极端情况，JDK的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash时间，性价比不高。 * */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //如果它的形式是：class C implements Comparable<C>，返回x的类，否则为空。 static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {//判断指出的对象是否是特定类的一个实例 Class<?> c; //定义实例类 Type[] ts, as; //定义数组类型 Type t; //定义原始类型 ParameterizedType p; //定义参数化类型 if ((c = x.getClass()) == String.class) //找到x的类，直接返回 return c; if ((ts = c.getGenericInterfaces()) != null) { //如果该类的类型数组参数不为空 for (int i = 0; i < ts.length; ++i) { //遍历该类的类型数组 //如果该类的类型符合一系列参数类型和类型对象条件，则返回该类 if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) return c; } } } return null; }
@SuppressWarnings({"rawtypes","unchecked"}) static int compareComparables(Class<?> kc, Object k, Object x) { //如果x匹配kc，k是可比较的，返回k.compareto(x)，否则返回0。 return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); }
//算法1：通过移位和减法来代替乘法，与2相乘等价于移位运算(低位补0)，例如：31*i == (i<<5)-1 static final int tableSizeFor(int cap) { //返回一个比给定整数大且最接近的2的幂次方整数。 //防止现在就是2的幂次，如果不减，经过下面的算法会把最高位后面的都置位1，再加1则相当于将当前的数值乘2 /** * 这个与HashMap中table下标的计算有关。 * n = table.length; * index = （n-1） & hash; * 因为，table的长度都是2的幂，因此index仅与hash值的低n位有关（此n非table.leng，而是2的幂指数），hash值的高位都被与操作置为0了。 * * 【2】为什么要n-1呢？ * * 当 n为 2 的幂次方的时候，减一之后就会得到 1111*的数字，这个数字正好可以掩码。 * 并且得到的结果取决于 hash值。因为 hash值是1，那么最终的结果也是1 ，hash值是0，最终的结果也是0。 * */ int n = cap - 1; n |= n >>> 1;//第一次右移 n |= n >>> 2;//第二次右移，这里的n是上面式子计算出来的结果，后面以此类推 n |= n >>> 4;//第三次右移 n |= n >>> 8;//第四次右移 /** * h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。 * */ n |= n >>> 16;//第五次右移、key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。 //如果n<0就返回1，否则如果n是大于等于最大容量限制就返回最大容量值，不然返回n+1。 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } /** *【3】HashMap 的容量为什么建议是 2的幂次方？ * hash 算法的目的是为了让hash值均匀的分布在桶中（数组），如果不使用 2 的幂次方作为数组的长度会怎么样？ * 假设我们的数组长度是10，还是上面的公式： * 1010 & 101010100101001001000 结果：1000 = 8 * 1010 & 101000101101001001001 结果：1000 = 8 * 1010 & 101010101101101001010 结果：1010 = 10 * 1010 & 101100100111001101100 结果：1000 = 8 * 这种散列结果，会导致这些不同的key值全部进入到相同的插槽中，形成链表，性能急剧下降。 * 所以一定要保证 &中的二进制位全为 1，才能最大限度的利用 hash 值，并更好的散列，只有全是1，才能有更多的散列结果。 * 如果是 1010，有的散列结果是永远都不会出现的，比如 0111，0101，1111，1110…，只要 &之前的数有 0， 对应的 1肯定就不会出现（因为只有都是1才会为1）。 * 大大限制了散列的范围。 * * 【4】自定义 HashMap 容量最好是多少？ * 如果Map中已有数据的容量达到了初始容量的 75%，那么散列表就会扩容，而扩容将会重新将所有的数据重新散列，性能损失严重. * 如果是2个数据的话可以将初始化容量设置为4。如果不是2的幂次方，散列结果将会大大下降。 * 如果你预计大概会插入 12 条数据的话，那么初始容量为16简直是完美，一点不浪费，而且也不会扩容。 * */ transient Node<K,V>[] table; //存储元素的数组，总是2的幂次倍
transient Set<Entry<K,V>> entrySet; // 存放具体元素的集
transient int size; // 存放元素的个数，注意这个不等于数组的长度。
transient int modCount; // 每次扩容和更改map结构的计数器
/** * threshold = capacity * loadFactor，当Size>=threshold的时候， * 那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。 * */ int threshold; // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
/** * loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1， * 那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0。 * loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。 * */ final float loadFactor; // 填充因子 //HashMap使用指定的初始容量和加载因子构造 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);//用户自定义的initialCapacity } //HashMap使用指定的初始容量和默认加载因子（0.75）构造 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //HashMap使用默认初始容量（16）和默认加载因子（0.75）构造 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } /**HashMap(Map<? extends K, ? extends V> m) -》 putMapEntries -》 resize()*/ //传入一个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) { if (table == null) { //判断table是否初始化 /** * 求出需要的容量，因为实际使用的长度=容量*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大且最接近的2的幂次方整数。 if (t > threshold) threshold = tableSizeFor(t); } //如果table已经初始化，则进行扩容操作，resize()就是扩容。 else if (s > threshold) resize(); //Map中的每一个key-value就是一个Entry实例，遍历取得key-value for (Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); //放入hashMap中 putVal(hash(key), key, value, false, evict); } } } //返回此映射中键 - 值映射的数量。 public int size() { return size; } //如果此映射不包含键-值映射关系,返回true public boolean isEmpty() { return size == 0; } /**get(Object key) -》 getNode(int hash, Object key)*/ //通过key获取value，如果是null，则返回null 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) { Node<K,V>[] tab; //hash节点数组 Node<K,V> first, e; //头结点与临时变量 int n; //长度 K k; //key //如果数组有元素且数组长度大于0且头结点下标不为空 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;//找不到该节点返回null } //如果此映射包含指定键的映射，则返回true public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } /**put(K key, V value) ——》 putVal() -》 treeifyBin*/ //向hashmap中添加key-value实例 public V put(K key, V value) { //调用putVal方法 return putVal(hash(key), key, value, false, true); } /** * onlyIfAbsent：如果该key存在值，如果为null的话，则插入新的value * evict：：如果为false，则该表处于创建模式。 * */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; //hash桶 Node<K,V> p; //桶中的头节点 int n, i; //n hashMap的长度，i 计算出的数组下标 //获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载 if ((tab = table ) == null || (n = tab.length) == 0) n = (tab = resize()).length; /**如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p**/ if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //哈希冲突的几种情况 else { Node<K,V> e; //临时节点 K k; //存放该当前节点的key //第一种，插入的key-value的hash值，key都与当前节点的相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //令其表示为头节点 else if (p instanceof TreeNode) //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点 /**为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功，如果添加成功返回null**/ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {//第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点 for (int binCount = 0; ; ++binCount) {//遍历链表 if ((e = p.next) == null) {//如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加 p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) //判断是否要转换为红黑树结构 treeifyBin(tab, hash); break; } //如果链表中有重复的key，e则为当前重复的节点，结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //有重复的key，则用待插入值进行覆盖，返回旧值。 if (e != null) { V oldValue = e.value; //如果不存在该值或者原来的值为null if (!onlyIfAbsent || oldValue == null) //为该节点设置value e.value = value; afterNodeAccess(e); return oldValue; } }
++modCount; //修改次数+1 //实际长度+1，判断是否大于临界值，大于则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null return null; } //扩容方法 final Node<K,V>[] resize() { //把没插入之前的哈希数组做为oldTal Node<K,V>[] oldTab = table; //old的长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //old的临界值 int oldThr = threshold; //初始化长度与临界值 int newCap, newThr = 0; if (oldCap > 0) {//oldCap > 0也就是说不是首次初始化，因为hashMap用的是懒加载 if (oldCap >= MAXIMUM_CAPACITY) {//大于最大值 threshold = Integer.MAX_VALUE;//临界值为整数的最大值 return oldTab; } //标记##其它情况，扩容两倍，并且扩容后的长度要小于最大值，old长度也要大于16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; //临界值也扩容为old的临界值2倍 } /** * 如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在， * 如果是首次初始化，它的临界值则为0 **/ else if (oldThr > 0) newCap = oldThr; //首次初始化，给与默认的值 else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//临界值等于容量*加载因子 } if (newThr == 0) {//此处的if为上面标记##的补充，也就是初始化时容量小于默认值16的，此时newThr没有赋值 float ft = (float)newCap * loadFactor;//new的临界值 //判断是否new容量是否大于最大值，临界值是否大于最大值 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; //赋予当前的table
//此处自然是把old中的元素，遍历到new中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //临时变量 Node<K,V> e; //当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突 if ((e = oldTab[j]) != null) { //把已经赋值之后的变量置为null，当然是为了好回收，释放内存 oldTab[j] = null; //如果下标处的节点没有下一个元素 if (e.next == null) //把该变量的值存入newCap中，e.hash & (newCap - 1)并不等于j newTab[e.hash & (newCap - 1)] = e; //该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素 else if (e instanceof TreeNode) //把此树进行转移到newCap中 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 如果这个链表不止一个元素且不是一颗树 // 则分化成两个链表插入到新的桶中去 // 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中 // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去 // 也就是分化成了两个链表 Node<K,V> loHead = null, loTail = null; //低位链表 Node<K,V> hiHead = null, hiTail = null; //高位链表 Node<K,V> next;//指针：指向下一个节点 do { next = e.next; // (e.hash & oldCap) == 0的元素放在低位链表中 // 比如，3 & 4 == 0 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; //往低位链表插入节点 else loTail.next = e; loTail = e; } // (e.hash & oldCap) != 0的元素放在高位链表中 // 比如，7 & 4 != 0 else { if (hiTail == null) hiHead = e; //往高位链表插入节点 else hiTail.next = e; hiTail = e; } } while ((e = next) != null);//遍历结束 // 遍历完成分化成两个链表了 // 低位链表在新桶中的位置与旧桶一样，即3和11还在三号桶中 if (loTail != null) { loTail.next = null; newTab[j] = loHead;// 原索引放到bucket里 } // 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了） if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; // 原索引+oldCap放到bucket里 } } } } } return newTab; }
//如果插入元素后链表的长度大于等于8则判断是否需要树化。 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; //n:数组长度，index:索引 Node<K,V> e; //e是hash值和数组长度计算后，得到链表的首节点 /** 如果数组为空或者数组长度小于树结构化的最小限制 * MIN_TREEIFY_CAPACITY 默认值64，对于这个值可以理解为：如果元素数组长度小于这个值，没有必要去进行结构转换 * 当一个数组位置上集中了多个键值对，那是因为这些key的hash值和数组长度取模之后结果相同。（并不是因为这些key的hash值相同） * 因为hash值相同的概率不高，所以可以通过扩容的方式，来使得最终这些key的hash值在和新的数组长度取模之后，拆分到多个数组位置上。 */ if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //如果桶的数量小于64，则进行扩容 resize(); // 如果元素数组长度已经大于等于了 MIN_TREEIFY_CAPACITY，那么就有必要进行结构转换了 // 根据hash值和数组长度进行取模运算后，得到链表的首节点 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //hd是树首节点，tl是树尾节点 do { TreeNode<K,V> p = replacementTreeNode(e, null);//节点转换为树节点 if (tl == null)//如果树尾节点为空说明没有根节点 hd = p;//附值给首节点，树的根节点 else {// 尾节点不为空 p.prev = tl;// 将节点p的prev指向尾结点 tl.next = p;//再将尾结点的next指向该插入的节点 } tl = p;// 把当前节点设为尾节点，值传递 } while ((e = e.next) != null); //循环遍历完所有要转化的节点 // 到目前为止 也只是把Node对象转换成了TreeNode对象，把单向链表转换成了双向链表 // 把转换后的双向链表，替换原来位置上的单向链表 // 如果进入过上面的循环，则从头节点开始树化 if ((tab[index] = hd) != null) hd.treeify(tab); //红黑树的方法：树化成红黑树结构 } }
//将指定映射中的所有映射复制到此映射。 public void putAll(Map<? extends K, ? extends V> m) { putMapEntries(m, true); }
/**remove(Object key) ——》 removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)*/ //如果存在，则从此映射中删除指定键的映射。 public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }
//方法为final，不可被覆写，子类可以通过实现afterNodeRemoval方法来增加自己的处理逻辑 /**第一参数为哈希值，第二个为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) { //node 存储要删除的节点，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; /* * 到这一步说明首节点没有匹配上，那么检查下是否有next节点 * 如果没有next节点，就说明该节点所在位置上没有发生hash碰撞, 就一个节点并且还没匹配上，也就没得删了，最终也就返回null了 * 如果存在next节点，就说明该数组位置上发生了hash碰撞，此时可能存在一个链表，也可能是一颗红黑树 */ else if ((e = p.next) != null) { if (p instanceof TreeNode)//先判断是否为红黑树的节点 //遍历红黑树，找到该节点并返回 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { //表示为链表节点，一样的遍历找到该节点 do { // 如果e节点的键是否和key相等，e节点就是要删除的节点，赋值给node变量，调出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } // 走到这里，说明e也没有匹配上 // 把当前节点p指向e，这一步是让p存储下一次循环里e的父节点，如果下一次e匹配上了，那么p就是node的父节点 /**注意，如果进入了链表中的遍历，那么此处的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);//调用afterNodeRemoval方法，该方法HashMap没有任何实现逻辑，目的是为了让子类根据需要自行覆写 //返回删除的节点 return node; } } //返回null则表示没有该节点，删除失败 return null; }获取方式：点“在看”，关注公众号并回复 面试 领取