Version: Next

HashMap

https://blog.csdn.net/ljf199701/article/details/106309417/

查找速度快，理想情况下时间复杂度为O(1)
在哈希表中插入一个元素的复杂度是O(1)
在无序数组中插入一个元素的复杂度是O(1)
访问数组中的第n个元素的复杂度是O(1)
访问链表中的第n个元素的复杂度是O(n)

HashMap的所有构造方法

Constructor and Description
`HashMap()` 构造一个空的 `HashMap` ，默认初始容量（16）和默认负载系数（0.75）。
`HashMap(int initialCapacity)` 构造一个空的 `HashMap`具有指定的初始容量和默认负载因子（0.75）。
`HashMap(int initialCapacity, float loadFactor)` 构造一个空的 `HashMap`具有指定的初始容量和负载因子。
`HashMap(Map<? extends K,? extends V> m)` 构造一个新的 `HashMap`与指定的相同的映射 `Map` 。

初始容量、加载因子与HashMap底层结构

容量有什么作用，加载因子有什么作用？
什么时候创建？
数组的作用、链表的作用
Java中存储数据都需要容器
什么时候创建数组，什么时候形成链表
并不是在构造方法内创建的
实在put方法中创建的
为什么要在put中创建
数组在内存中是一段连续的内存空间，如果创建了hashmap申请了空间，但是什么都不放，那就白白浪费了空间，所以在put时才开辟空间
怎么确定键值对Entry在数组中的位置
Entry键值对在数组中的位置重复了怎么办
如果存放的键值对在数组中位置相同，称为Hash冲突
如果数组中的每一个位置上都已经有Entry了怎么办？会发生什么？
会频繁的构成链表
因此提出了对数组进行扩容
当已使用的数组容量超过 初始容量 x 加载因子 ，默认 16 x 0.75 = 12时，对数组进行扩容

HashMap的无参构造方法源代码

/**
     * 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
}

可以看到将负载因子设置为了默认负载因子值，并没有创建任何数组或链表

Hash冲突

如果存放的键值对在数组中位置相同，称为Hash冲突
则，在对应数组位置上，将重复Entry对象封装为一个链表
如果这个链表太长了，搜索效率就会因为链表这种结构而下降
默认，链表长达大于8，且数组长度大于64，转红黑树

put方法的源代码

向HashMap中存放数据，需要计算Hash值，计算键值对在数组中的位置，决定是否要进行扩容，并且HashMap的数组实际上是在put方法阶段被创建的

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

调用了putVal()
putVal()调用了hash()哈希方法 [用于确定Entry在数组中的位置，具体请看《怎么确定Entry在数组中定位置》]，哈希方法返回了一个int值
判断数组是否存在or数组长度为0，如果不存在或长度为0就调用resize()根据初始容量得到一个数组对象，并将其长度赋给n
使用数组最大下标(n-1)作为低位掩码取hash低位作为数组下标
判断数组对应下标位置上有没有Entry元素，可能出现三种情况
1. 位置上啥也没有，是个null，直接newNode，创建一个Entry节点放进去
2. 位置上有个Entry，要涉及链表操作
3. 位置上是个红黑树，涉及到平衡二叉树操作

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  //定义一个节点数组，一个节点
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  //将当前数组赋给局部数组，判断有没有创建过数组 or 数组的长度为0
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;        // resize()方法返回一个数组对象，将数组长度赋给n，默认16
  //准备将Entry对象放入数组
  //n默认16，-1二进制位1111,做与位运算，取hash低四位。正好在n表示的长度范围内，即作为下标
  //判断计算出来的下标位置上是否已存在Entry，把下标上的东西取出来赋给p节点
  if ((p = tab[i = (n - 1) & hash]) == null) // 如果位置上没东西，直接新建一个Entry节点存进去
    tab[i] = newNode(hash, key, value, null);
  else { //位置上有东西，接下来看是走链表还是走红黑树
    Node<K,V> e; K k;
    if (p.hash == hash && // ==比较的是地址值是否相等；equals方法比较可以自定义，比如按值比较
        ((k = p.key) == key || (key != null && key.equals(k)))) //如果key完全相同
      e = p; //将当前下标上的节点赋给e 因为HashMap key唯一
    else if (p instanceof TreeNode) //判断当前下标上的东西是不是树节点，即判断是链表还是红黑树
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //将节点放到红黑树上
    else { //当前下标上的东西是个链表
      for (int binCount = 0; ; ++binCount) { //遍历链表
        if ((e = p.next) == null) { //找到链表尾
          p.next = newNode(hash, key, value, null); //尾插新节点 
          // 如果链表长度大于树阈值-1，转红黑树
          // 转红黑树的treeifyBin方()法，要判断数组长度是否小于 MIN_TREEIFY_CAPACITY，如果比最小树容量小，就调用resize()，不转红黑树;
          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; //如果key和链表上某个节点的key一模一样则啥也不做直接跳出链表遍历
        p = e;  //迭代链表的下一个节点
      }
    }
    if (e != null) { // existing mapping for key
      V oldValue = e.value;  // 取出e的value，即旧值
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;  // 直接覆盖旧值，把新值存到当前key里
      afterNodeAccess(e);  // 访问后回调
      return oldValue;  // HashMap.put()方法返回被覆盖掉的旧值
    }
  }
  ++modCount; //很多集合类都有这个属性，记录结构化修改次数，主要是关于线程安全的。
  //具体看 https://blog.csdn.net/u012926924/article/details/50452411
  if (++size > threshold) // 判断是否需要扩容
    resize();
  afterNodeInsertion(evict); 
  return null;
}

tab节点数组
- transient表示临时，主要涉及到Java序列化和安全性，使用后变量不会被持久化，关于它的具体内容请看transient关键字详解

/**
     * 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;

用于转红黑树的treeifyBin()方法

/**
     * 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<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //判断数组长度是否小于最小树容量64
    resize(); //小于64则不转红黑树，而是用resize()扩容
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    TreeNode<K,V> hd = null, tl = null;
    do {
      TreeNode<K,V> p = replacementTreeNode(e, null);
      if (tl == null)
        hd = p;
      else {
        p.prev = tl;
        tl.next = p;
      }
      tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
      hd.treeify(tab);
  }
}

如果key冲突，put方法返回被覆盖的旧值

public static void main(String[] args) {
    HashMap<Object, Object> map = new HashMap<>();
    map.put(1, "1");
    Object put = map.put(1, "2");
    System.out.println(put);
}

初始容量

源代码

/**
  * The default initial capacity - MUST be a power of two.
  */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

使用位操作定义，二进制0001 左移4下，变为二进制0001 0000 等于十进制16
注释中写到，初始容量必须为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;

最大容量为2的30次幂
必须为小于2的30次幂的一个2的次幂

加载因子——控制扩容阈值

/**
     * The load factor used when none specified in constructor.
     */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

怎么确定Entry在数组中的位置——hash()

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如果key为null，则直接将hash值设定为0
否则计算hash code，调用的是Object的hashCode方法，计算完后想有无符号移动16位，并且取高位 -> 再和原始hash进行异或运算，返回一个int值
这段计算Hash code的代码为的是实现 扰动函数，降低碰撞几率。具体请看[JDK1.8中HashMap中的hash方法的底层原理是什么]
返回的并不是entry在数组中的下标，因为这个方法并不知道数组的具体长度
最终确定位置要看put()方法，具体请看put方法，结论为： 使用数组的总长度n，减去1，即n-1即数组的最大下标，与hash值做按位与运算得到下标 (n-1) & hash
这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。
- 2的次幂用二进制书写的话，形式为 0000 0001、0000 0010、0000 0100这样的one-hot编码，即总是只有一位为1，剩下全为0
- 2的次幂的二进制表示，只要-1，就会变为0000 0000、0000 0001、0000 0011，这样的编码，从高位全为0，从某一位开始全变成1
- 当一个值用二进制表示时，值的变化更多的会反映在二进制低位上的变化，高位变化比较少，因为高位代表的值很大，低四位则是1、2、4、8这样的小值，经常出现变动以达到凑成某个数的效果。这样的值和1111 1111这种全1的二进制做与运算（用在putVal中的计算数组下标的代码中），运算结果能最大程度反映hash值的变化，降低碰撞概率。
- 这段hash方法的return语句中，Object方法返回的原始hash int值高位通常都是1，因此右移16位后，变成一个低位全是1的二进制数，同原始hash做异或运算，也能最大程度上反映hash值的变化，降低碰撞概率

hashmap能不能存 key=null, value=null

能

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如果key为null，HashMap的hash方法直接将其hash值设置为0

扩容

如果数组中的每一个位置上都已经有Entry了怎么办？会发生什么？

会频繁的构成链表
因此提出了对数组进行扩容
当已使用的数组容量超过 初始容量 x 加载因子 ，默认 16 x 0.75 = 12时，对数组进行扩容，总是扩容为原来的2倍，除非达到最大数组容量
扩容的目的：减少Hash冲突，提高查询效率

resize()方法源码

/**
 * 扩容后，红黑树的hash分布，只可能存在于两个位置：原索引位置、原索引位置+oldCap
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this; // 拿到调用此方法的节点
    TreeNode<K,V> loHead = null, loTail = null; // 存储索引位置为:“原索引位置”的节点
    TreeNode<K,V> hiHead = null, hiTail = null; // 存储索引位置为:“原索引+oldCap”的节点
    int lc = 0, hc = 0;
    // 1.以调用此方法的节点开始，遍历整个红黑树节点
    for (TreeNode<K,V> e = b, next; e != null; e = next) {  // 从b节点开始遍历
        next = (TreeNode<K,V>)e.next;   // next赋值为e的下个节点
        e.next = null;  // 同时将老表的节点设置为空，以便垃圾收集器回收
        // 2.如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)  // 如果loTail为空, 代表该节点为第一个节点
                loHead = e; // 则将loHead赋值为第一个节点
            else
                loTail.next = e;    // 否则将节点添加在loTail后面
            loTail = e; // 并将loTail赋值为新增的节点
            ++lc;   // 统计原索引位置的节点个数
        }
        // 3.如果e的hash值与老表的容量进行与运算为1,则扩容后的索引位置为:老表的索引位置＋oldCap
        else {
            if ((e.prev = hiTail) == null)  // 如果hiHead为空, 代表该节点为第一个节点
                hiHead = e; // 则将hiHead赋值为第一个节点
            else
                hiTail.next = e;    // 否则将节点添加在hiTail后面
            hiTail = e; // 并将hiTail赋值为新增的节点
            ++hc;   // 统计索引位置为原索引+oldCap的节点个数
        }
    }
    // 4.如果原索引位置的节点不为空
    if (loHead != null) {   // 原索引位置的节点不为空
        // 4.1 如果节点个数<=6个则将红黑树转为链表结构
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            // 4.2 将原索引位置的节点设置为对应的头节点
            tab[index] = loHead;
            // 4.3 如果hiHead不为空，则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)
            // 已经被改变, 需要重新构建新的红黑树
            if (hiHead != null)
                // 4.4 以loHead为根节点, 构建新的红黑树
                loHead.treeify(tab);
        }
    }
    // 5.如果索引位置为原索引+oldCap的节点不为空
    if (hiHead != null) {   // 索引位置为原索引+oldCap的节点不为空
        // 5.1 如果节点个数<=6个则将红黑树转为链表结构
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            // 5.2 将索引位置为原索引+oldCap的节点设置为对应的头节点
            tab[index + bit] = hiHead;
            // 5.3 loHead不为空则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)
            // 已经被改变, 需要重新构建新的红黑树
            if (loHead != null)
                // 5.4 以hiHead为根节点, 构建新的红黑树
                hiHead.treeify(tab);
        }
    }
}

JDK1.7链表头插法改为JDK1.8链表尾插法

1.7新元素在链表头部插入，在HashMap扩容时，如果是并发环境，可能会在链表元素逆序时，产生循环引用，即前一个指向后一个，后一个又指向前一个，形成环链，导致并发环境下出现死锁

JDK1.8引入红黑树

因为链表太长时，时间复杂度从常数阶O(1)增长到线性阶O(n)
引入红黑树复杂度控制在O(logn)
当数组长度大于64，且链表长度大于8，将链表转为红黑树
当链表长度小于6时，转回链表
最小树容量为64

/**
     * 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;

/**
     * 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;

/**
     * 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;

HashMap 和 Hashtable 的区别

HashMap 允许 key 和 value 为 null，Hashtable 不允许。
HashMap 的默认初始容量为 16，Hashtable 为 11。
HashMap 的扩容为原来的 2 倍，Hashtable 的扩容为原来的 2 倍加 1。
HashMap 是非线程安全的，Hashtable是线程安全的。
HashMap 的 hash 值重新计算过，Hashtable 直接使用 hashCode。
HashMap 去掉了 Hashtable 中的 contains 方法。
HashMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类。

ConcurrentHashMap

分段锁实现线程安全——ConcurrentHashMap原理解析
ConcurrentHashMap不允许null作为key或者value，会抛出空指针异常

HashTable是线程安全的，为什么不直接使用HashTable？

HashTable基于synchronized进行方法同步，读、写都是用了synchronized，插入时不能读，读取时不能写，因为HashTable锁的是整个集合，全表锁，多线程情况下效率极低
于是，ConcurrentHashMap使用了分段锁技术，采用细粒度锁，只锁集合的一部分

JDK1.5 —— Segment级可重入锁

由一个segments数组构成，里面存放着segment，每个segment里面是一个数组，数组上的每个元素是Entry对象构成的链表
每个segment具有一把锁，当一个线程占用一个segment，只会锁当前的segment，其他的segment依然可以被访问
默认16个segment

JDK1.8——链表头CAS+synchronized细粒度锁

取消了Segments，结构与JDK1.8 HashMap相同
采用CAS+synchronized，锁链表头结点或红黑树根结点
只要hash不冲突，就不会产生并发
相比1.5的实现，锁粒度更细，效率更高

put方法

分析如何利用CAS和synchronized进行高效同步数据更新

public V put(K key, V value) {
    return putVal(key, value, false);
}

    /** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    //ConcurrentHashMap 不允许插入null键，HashMap允许插入一个null键
    if (key == null || value == null) throw new NullPointerException();
    //计算key的hash值
    int hash = spread(key.hashCode());
    int binCount = 0;
    //for循环的作用：因为更新元素是使用CAS机制更新，需要不断的失败重试，直到成功为止。
    for (Node<K,V>[] tab = table;;) {
        // f：链表或红黑二叉树头结点，向链表中添加元素时，需要synchronized获取f的锁。
        Node<K,V> f; int n, i, fh;
        //判断Node[]数组是否初始化，没有则进行初始化操作
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        //通过hash定位Node[]数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头结点），添加失败则进入下次循环。
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //检查到内部正在移动元素（Node[] 数组扩容）
        else if ((fh = f.hash) == MOVED)
            //帮助它扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //锁住链表或红黑二叉树的头结点
            synchronized (f) {
                //判断f是否是链表的头结点
                if (tabAt(tab, i) == f) {
                    //如果fh>=0 是链表节点
                    if (fh >= 0) {
                        binCount = 1;
                        //遍历链表所有节点
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //如果节点存在，则更新value
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            //不存在则在链表尾部添加新节点。
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    //TreeBin是红黑二叉树节点
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        //添加树节点
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                      value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            
            if (binCount != 0) {
                //如果链表长度已经达到临界值8 就需要把链表转换为树结构
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //将当前ConcurrentHashMap的size数量+1
    addCount(1L, binCount);
    return null;
}

判断Node[]数组是否初始化，没有则进行初始化操作
通过hash定位Node[]数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头结点），添加失败则进入下次循环。
检查到内部正在扩容，如果正在扩容，就帮助它一块扩容。
如果f!=null，则使用synchronized锁住f元素（链表/红黑二叉树的头元素） 4.1 如果是Node(链表结构)则执行链表的添加操作。 4.2 如果是TreeNode(树型结果)则执行树添加操作。
判断链表长度已经达到临界值8 就需要把链表转换为树结构。

总结：

JDK8中的实现也是锁分离的思想，它把锁分的比segment（JDK1.5）更细一些，只要hash不冲突，就不会出现并发获得锁的情况。
它首先使用无锁操作CAS插入头结点，如果插入失败，说明已经有别的线程插入头结点了，再次循环进行操作。
如果头结点已经存在，则通过synchronized获得头结点锁，进行后续的操作。性能比segment分段锁又再次提升

面试题

HashMap线程安全问题发生在哪个阶段？设计一个方案验证HashMap的线程安全问题
- 准备多个线程
- 同时访问同一个HashMap

public static void main(String[] args) throws InterruptedException {
    Map<Object, Object> map = new HashMap<>();
  
    new Thread(() -> {
      for (int i = 0; i < 2500; i++) {
        map.put(i, i);
      }
    }).start();
  
    new Thread(() -> {
      for (int i = 2500; i < 5000; i++) {
        map.put(i, i);
      }
    }).start();
  
    //为了结果完整，最好主线程睡一会儿再打印
    Thread.currentThread().sleep(1000);
    System.out.println(map.size());
}

4862

HashMap能不能存null,null
HashMap扩容大小为什么总是2的次幂
HashMap底层为什么要使用异或运算
HashMap如何确定键值对位置，如何解决Hash冲突
HashMap加载因子为什么为0.75，如果改为1呢
HashMap与ConcurrentHashMap的区别
ConcurrentHashMap是如何实现线程安全的
- 分段锁
HashMap会缩容吗
- 不会，反复横跳反而是一种浪费资源的操作
- 曾经扩容上去了，就说明这个场景确实会用到很大的容量
- 可以手动缩(略)
扩容后，节点重 hash 为什么只可能分布在 “原索引位置” 与 “原索引 + oldCap 位置”?
- 史上最详细JDK1.8 HashMap源码分析

HashMap#

HashMap的所有构造方法#

初始容量、加载因子与HashMap底层结构#

Hash冲突#

put方法的源代码#

初始容量#

最大容量#

加载因子——控制扩容阈值#

怎么确定Entry在数组中的位置——hash()#

hashmap能不能存 key=null, value=null#

扩容#

resize()方法源码#

JDK1.7链表头插法改为JDK1.8链表尾插法#

JDK1.8引入红黑树#

HashMap 和 Hashtable 的区别#

ConcurrentHashMap#

JDK1.5 —— Segment级可重入锁#

JDK1.8——链表头CAS+synchronized细粒度锁#

面试题#

HashMap

HashMap的所有构造方法

初始容量、加载因子与HashMap底层结构

Hash冲突

put方法的源代码

初始容量

最大容量

加载因子——控制扩容阈值

怎么确定Entry在数组中的位置——hash()

hashmap能不能存 key=null, value=null

扩容

resize()方法源码

JDK1.7链表头插法改为JDK1.8链表尾插法

JDK1.8引入红黑树

HashMap 和 Hashtable 的区别

ConcurrentHashMap

JDK1.5 —— Segment级可重入锁

JDK1.8——链表头CAS+synchronized细粒度锁

面试题