Put方法hashMap常见属性源码分析HashMap是懒惰加载在创建对象时并没有初始化数组在无参的构造函数中设置了默认的加载因子是0.75添加数据流程图public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; //判断数组是否未初始化 if ((tab table) null || (n tab.length) 0) //如果未初始化调用resize方法 进行初始化 n (tab resize()).length; //通过 运算求出该数据key的数组下标并判断该下标位置是否有数据 if ((p tab[i (n - 1) hash]) null) //如果没有直接将数据放在该下标位置 tab[i] newNode(hash, key, value, null); //该数组下标有数据的情况 else { NodeK,V e; K k; //判断该位置数据的key和新来的数据是否一样 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) //如果一样证明为修改操作该节点的数据赋值给e,后边会用到 e p; //判断是不是红黑树 else if (p instanceof TreeNode) //如果是红黑树的话进行红黑树的操作 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); //新数据和当前数组既不相同也不是红黑树节点证明是链表 else { //遍历链表 for (int binCount 0; ; binCount) { //判断next节点如果为空的话证明遍历到链表尾部了 if ((e p.next) null) { //把新值放入链表尾部 p.next newNode(hash, key, value, null); //因为新插入了一条数据所以判断链表长度是不是大于等于8 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st //如果是进行转换红黑树操作 treeifyBin(tab, hash); break; } //判断链表当中有数据相同的值如果一样证明为修改操作 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; //把下一个节点赋值为当前节点 p e; } } //判断e是否为空e值为修改操作存放原数据的变量 if (e ! null) { // existing mapping for key //不为空的话证明是修改操作取出老值 V oldValue e.value; //一定会执行 onlyIfAbsent传进来的是false if (!onlyIfAbsent || oldValue null) //将新值赋值当前节点 e.value value; afterNodeAccess(e); //返回老值 return oldValue; } } //计数器计算当前节点的修改次数 modCount; //当前数组中的数据数量如果大于扩容阈值 if (size threshold) //进行扩容操作 resize(); //空方法 afterNodeInsertion(evict); //添加操作时 返回空值 return null; }判断键值对数组table是否为空或为null否则执行resize()进行扩容初始化根据键值key计算hash值得到数组索引判断table[i]null条件成立直接新建节点添加如果table[i]null ,不成立4.1 判断table[i]的首个元素是否和key一样如果相同直接覆盖value4.2 判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值对4.3 遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作遍历过程中若发现key已经存在直接覆盖value插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold数组长度*0.75如果超过进行扩容。HashMap的扩容机制扩容的流程//扩容、初始化数组 final NodeK,V[] resize() { NodeK,V[] oldTab table; //如果当前数组为null的时候把oldCap老数组容量设置为0 int oldCap (oldTab null) ? 0 : oldTab.length; //老的扩容阈值 int oldThr threshold; int newCap, newThr 0; //判断数组容量是否大于0大于0说明数组已经初始化 if (oldCap 0) { //判断当前数组长度是否大于最大数组长度 if (oldCap MAXIMUM_CAPACITY) { //如果是将扩容阈值直接设置为int类型的最大数值并直接返回 threshold Integer.MAX_VALUE; return oldTab; } //如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap2 //运算过后判断是不是最大值并且oldCap需要大于16 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) * newThr oldThr 1; // double threshold 等价于oldThr*2 } //如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0 else if (oldThr 0) // initial capacity was placed in threshold newCap oldThr; //数组未初始化的情况将阈值和扩容因子都设置为默认值 else { // zero initial threshold signifies using defaults newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //初始化容量小于16的时候扩容阈值是没有赋值的 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}) //根据上边计算得出的容量 创建新的数组 NodeK,V[] newTab (NodeK,V[])new Node[newCap]; //赋值 table newTab; //扩容操作判断不为空证明不是初始化数组 if (oldTab ! null) { //遍历数组 for (int j 0; j oldCap; j) { NodeK,V e; //判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作 if ((e oldTab[j]) ! null) { //将数组位置置空 oldTab[j] null; //判断是否有下个节点 if (e.next null) //如果没有就重新计算在新数组中的下标并放进去 newTab[e.hash (newCap - 1)] e; //有下个节点的情况并且判断是否已经树化 else if (e instanceof TreeNode) //进行红黑树的操作 ((TreeNodeK,V)e).split(this, newTab, j, oldCap); //有下个节点的情况并且没有树化链表形式 else { //比如老数组容量是16那下标就为0-15 //扩容操作*2容量就变为32下标为0-31 //低位0-15高位16-31 //定义了四个变量 // 低位头 低位尾 NodeK,V loHead null, loTail null; // 高位头 高位尾 NodeK,V hiHead null, hiTail null; //下个节点 NodeK,V next; //循环遍历 do { //取出next节点 next e.next; //通过 与操作 计算得出结果为0 if ((e.hash oldCap) 0) { //如果低位尾为null证明当前数组位置为空没有任何数据 if (loTail null) //将e值放入低位头 loHead e; //低位尾不为null证明已经有数据了 else //将数据放入next节点 loTail.next e; //记录低位尾数据 loTail e; } //通过 与操作 计算得出结果不为0 else { //如果高位尾为null证明当前数组位置为空没有任何数据 if (hiTail null) //将e值放入高位头 hiHead e; //高位尾不为null证明已经有数据了 else //将数据放入next节点 hiTail.next e; //记录高位尾数据 hiTail e; } } //如果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; }在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值数组长度 * 0.75每次扩容的时候都是扩容之前容量的2倍扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中没有hash冲突的节点则直接使用 e.hash (newCap - 1) 计算新数组的索引位置如果是红黑树走红黑树的添加如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上hashMap的寻址算法在putVal方法中有一个hash(key)方法这个方法就是来去计算key的hash值的看下面的代码首先获取key的hashCode值然后右移16位 异或运算 原来的hashCode值主要作用就是使原来的hash值更加均匀减少hash冲突有了hash值之后就很方便的去计算当前key的在数组中存储的下标看下面的代码n-1)hash : 得到数组中的索引代替取模性能更好数组长度必须是2的n次幂关于hash值的其他面试题为何HashMap的数组长度一定是2的次幂计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模扩容时重新计算索引效率更高 hash oldCap 0 的元素留在原来位置 否则新位置 旧位置 oldCap