2. 技术博客
  3. Java容器-Map

Java容器-Map

tech2023-12-24  84

Java容器-Map

Map.EntryMap的四种遍历方式 HashMapJDK 1.8 HashMap 源码分析成员变量public HashMap(int initialCapacity, float loadFactor)static final int tableSizeFor(int cap)hash()public V put(K key, V value)resize() TreeMapPair参考资料 HashMap、Hashtable、ConcurrentHashMapHashMap 的数据结构？请你解释 HashMap 的容量为什么是2的n次幂？HashMap中put()方法的过程？​HashMap的扩容操作是怎么实现的？​HashMap的扩容操作是怎么实现的？​​HashMap扩容时的重哈希过程是怎么实现的？ HashMap 中两个对象的 hashcode 相同时会发生什么？HashMap 是怎么解决哈希冲突的？ HashMap为什么不直接使用处理后的hashCode()值作为其哈希数组的下标？不直接使用 hashCode()作为哈希数组的下标，那 HashMap 是怎么处理其哈希数组的下标的呢？你知道 hash() 的实现吗？为什么要这样实现？为什么要用异或运算符？ HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？HashMap 和 HashTable 有什么区别？1. 线程安全性不同2. 效率不同3. Hash 数组初始化大小不同4. Hash 数组扩容大小不同5. 放入对象时，hashcode 的获取方式不同6. 放入对象时，键-值为空情况不同参考资料 HashMap，LinkedHashMap，TreeMap 有什么区别？HashMap & TreeMap & LinkedHashMap 使用场景？HashMap 与 ConcurrentHashMap 的区别？1. 线程安全性不同2. 放入对象时，键值对为空情况不同 Java 中另一个线程安全的、与 HashMap 极其类似的类是什么？同样是线程安全，它与 Hashtable 在线程同步上有什么不同？为什么 ConcurrentHashMap 比 Hashtable 效率要高？

Map.Entry

Map是Java中的接口，Map.Entry是Map中的一个内部接口； Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue方法。

遍历map的四种方法及Map.entry详解

Map的四种遍历方式

java中Map及Map.Entry详解

HashMap

得到HashMap的长度

HashMap 中元素索引的确定： idx = hashcode & (tab.length - 1)

JDK 1.8 HashMap 源码分析

成员变量

/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 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; /** * 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. * * 链表转换为红黑树的阈值: 8 */ 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. * * 红黑树退化为链表的阈值: 6 */ static final int UNTREEIFY_THRESHOLD = 6;

public HashMap(int initialCapacity, float loadFactor)

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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); }

static final int tableSizeFor(int cap)

/** * Returns a power of two size for the given target capacity. */ 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; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

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); }

public V put(K key, V value)

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * 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; // 初始化桶数组 tab, tab 被延迟到插入新数据时再进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法 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); // 如果链表长度大于或等于树化阈值，则进行树化操作 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 条件为 true，表示当前链表包含要插入的键值对，终止遍历 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 判断要插入的键值对是否存在 HashMap 中 if (e != null) { // existing mapping for key V oldValue = e.value; // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 键值对数量超过阈值时，则进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

resize()

/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 如果老的容量大于0 if (oldCap > 0) { // 如果容量大于容器最大值 if (oldCap >= MAXIMUM_CAPACITY) { // 阀值设为int最大值 threshold = Integer.MAX_VALUE; // 返回老的数组，不再扩充 return oldTab; }// 如果老的容量*2 小于最大容量并且老的容量大于等于默认容量 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 新的阀值也再老的阀值基础上*2 newThr = oldThr << 1; // double threshold }// 如果老的阀值大于0 else if (oldThr > 0) // initial capacity was placed in threshold // 新容量等于老阀值 newCap = oldThr; else { // 如果容量是0，阀值也是0，认为这是一个新的数组，使用默认的容量16和默认的阀值12 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的阀值是0，重新计算阀值 if (newThr == 0) { // 使用新的容量 * 负载因子（0.75） float ft = (float)newCap * loadFactor; // 如果新的容量小于最大容量 且 阀值小于最大 则新阀值等于刚刚计算的阀值，否则新阀值为 int 最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 将新阀值赋值给当前对象的阀值。 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 创建一个Node 数组，容量是新数组的容量（新容量要么是老的容量，要么是老容量*2，要么是16） Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 将新数组赋值给当前对象的数组属性 table = newTab; // 如果老的数组不是null if (oldTab != null) { // 循环老数组 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) // 调用红黑树 的split 方法，传入当前对象，新数组，当前下标，老数组的容量，目的是将树的数据重新散列到数组中 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 如果既不是树，next 节点也不为空，则是链表，注意，这里将优化链表重新散列（java 8 的改进） // Java8 之前，这里曾是并发操作会出现环状链表的情况，但是Java8 优化了算法。此bug不再出现，但并发时仍然不建议HashMap Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 这里的判断需要引出一些东西：oldCap 假如是16，那么二进制为 10000，扩容变成 100000，也就是32. // 当旧的hash值 与运算 10000，结果是0的话，那么hash值的右起第五位肯定也是0，那么该于元素的下标位置也就不变。 if ((e.hash & oldCap) == 0) { // 第一次进来时给链头赋值 if (loTail == null) loHead = e; else // 给链尾赋值 loTail.next = e; // 重置该变量 loTail = e; } // 如果不是0，那么就是1，也就是说，如果原始容量是16，那么该元素新的下标就是：原下标 + 16（10000b） else { // 同上 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 理想情况下，可将原有的链表拆成2组，提高查询性能。 if (loTail != null) { // 销毁实例，等待GC回收 loTail.next = null; // 置入bucket中 newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

深入理解 HashMap put 方法（JDK 8逐行剖析）

TreeMap

Java集合–TreeMap完全解析 java集合系列——Map之TreeMap介绍（九）

Pair

介绍java中Pair 【小家java】Java实用数据结构Pair、MutablePair、ImmutablePair详解（推荐apache的commons组件提供） java.util.TreeMap.tailMap()方法实例

参考资料

面试28k职位，老乡面试官从HashCode到HashMap给我讲了一下午！「回家赶忙整理出1.6万字的面试材料」 Java8 HashMap源码分析 java8 HashMap源码 详细研读 Java 基础：hashCode方法 深入解析Java对象的hashCode和hashCode在HashMap的底层数据结构的应用 Java提高篇——equals()与hashCode()方法详解

全网把Map中的hash()分析的最透彻的文章，别无二家。

HashMap、Hashtable、ConcurrentHashMap

HashMap 的数据结构？

HashMap 的设计就是为了在元素的查找上获得最优的性能（get()时时间复杂度达到O(1)），因此 HashMap 主要使用了数组作为核心的数据存储结构，同时使用链地址法来解决K-V映射时产生的碰撞，同时在 Java 8 中引入红黑树来进一步优化哈希碰撞时的数据查找性能； HashMap 通过 hash() 方法确定元素在哈希数组中的下标，并将元素放入数组对应下标处指向的链表中（尾插法），当元素个数超过 8 时，会将链表转换为红黑树；当元素个数小于6时，会将红黑树转换为链表；

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

Java8 HashMap源码分析 面试：HashMap 夺命二十一问！鸡哥都扛不住~ 问题1

请你解释 HashMap 的容量为什么是2的n次幂？

请你解释HashMap的容量为什么是2的n次幂？ Java集合必会14问（精选面试题整理）面试官：为什么数组长度要保证为2的幂次方呢？

从原理上来说，HashMap 为了存取高效，要尽量减少碰撞，就是要尽量把数据均匀分配，使得每个链表上分配的数据大致相同。在 HashMap 中这个实现就是取模，即 hash % tab.length，计算机中取模效率比不上位移运算，所以在源码的实现上采用了位移运算，即 hash & (tab.length - 1)，而 hash & (tab.length - 1) == hash % tab.length 的前提就是哈希数组的长度必须是 2 的 n 次幂。

HashMap中put()方法的过程？

判断哈希数组是否为空，如果为空，则创建默认大小为 16 的哈希数组；通过 hash() 方法计算key对应的数组下标，并判断该下标处元素是否为空：如果为空，则根据 key 和 value 创建对应元素；如果下标处对应元素不为空，则说明存在哈希冲突，相应的进行如下3种判断及操作： 3.1 判断两个冲突的 key 是否相等，如果相等，说明元素已存在，将当前值赋值给变量 e，留待之后的重复值处理； 3.2 如果 key 不相等，则判断对应值是否为树类型，如果是树类型，则将该值追加至红黑树； 3.3 如果 key 不相等，并且对应值也不是树类型，那么就必然是链表类型，则遍历链表，如果链表中不存在 key 对应值，则将该值追加至链表；如果链表的长度大于8，则将链表修改为红-黑树；最后，如果这三个判断返回的 e != null，则说明 key 重复，则更新 key 对应的 value 值；对维护着迭代器的 modCount 变量自增；最后判断是否超过阈值，如果当前数组的长度超过阈值，则重新 hash；

深入理解 HashMap put 方法（JDK 8逐行剖析） 面试28k职位，老乡面试官从HashCode到HashMap给我讲了一下午！「回家赶忙整理出1.6万字的面试材料」 1.2 插入流程和源码分析 HashMap面试必问的数据结构相关知识总结 7.HashMap中put方法的过程？

​HashMap的扩容操作是怎么实现的？

​HashMap的扩容操作是怎么实现的？

深入理解 HashMap put 方法（JDK 8逐行剖析） 5. 判断是否超过阀值，如果超过，则重新散列数组。 面试28k职位，老乡面试官从HashCode到HashMap给我讲了一下午！「回家赶忙整理出1.6万字的面试材料」 1.2 插入流程和源码分析

HashMap 扩容过程主要实现为 resize() 方法，初始化一个默认大小的 HashMap 时会调用该方法；同事，当 HashMap 中链表长度超过 8 但是哈希数组的长度小于 64 的时候，也会调用该方法进行哈希数组的重新散列；HashMap 的扩容过程主要如下：

判断老的容量是否大于 0： 如果老的容量大于0，并且老的容量大于容器的最大值，则设置阈值为容器的最大值并返回老的哈希数组，哈希数组不再扩容；如果老的容量乘以2小于容器的最大容量，并且老的容量大于等于容器默认大小，则更新新的阈值为原阈值的两倍； 如果老的阈值大于 0，则新的容量等于老的阈值；注意：这里很重要！！！还记得我们之前使用new 操作符的时候，会设置阀值为 2 的幂次方，那么这里就用上了那个计算出来的数字，也就是说，就算我们设置的不是2的幂次方，HashMap 也会自动将你的容量设置为2的幂次方。如果老的阈值和容量都不大于0，则是一个新的数组，设置新的容量为默认初始容量 16，新的阈值为 16 * 0.75 = 12如果新的阈值是0，则重新计算新的阈值，使用新的容量乘以负载因子得到新的阈值，然后判断新的阈值是否合法（新的阈值和新的容量都小于容器的最大值）：如果新的阈值合法则使用该阈值；否则设置新的阈值为容器的最大值；将新阈值赋值给当前 HashMap 对象的阈值；创建新的Node数组，大小为新的容量（新的容量要么为旧的容量，要么为旧的容量*2，要么为 16），并将新的 Node 数组赋值给当前 HashMap 对象的数组；如果老的数组不为空，则将老数组中的值重新散列到新数组中；如果老的数组为空，则直接返回新的数组；

​​HashMap扩容时的重哈希过程是怎么实现的？

深入理解 HashMap put 方法（JDK 8逐行剖析） 5. 判断是否超过阀值，如果超过，则重新散列数组。 面试28k职位，老乡面试官从HashCode到HashMap给我讲了一下午！「回家赶忙整理出1.6万字的面试材料」 1.2 插入流程和源码分析

将老数组中的元素重哈希到新数组的过程如下：

循环遍历老的数组，下标从 0 开始，并判断对应下标的值是否为空：如果对应下标的值不为空，则判断对应下标处的 next 节点是否为空，也就是判断对应下标的数组元素是否为链表：如果不是链表，说明该下标处实际只有一个元素，则重新将该值散列（hash & (newTab.length - 1)）到新数组中；判断对应下标处是否为树的节点，如果该节点是树，则调用红黑树的 split() 方法，传入当前对象、新的数组、当前下标、旧的容量，split() 方法会重新计算红黑树中每个节点的 hash 值，如果重新计算后，树中元素的哈希值与原值不同，则重新散列到不同的下标中，达到拆分红黑树的目的，提高性能；如果既不是树，next 节点也不为空，则是链表，将旧链表中的元素重新计算哈希值，如果得到的哈希值和之前的不同，则将该元素从链表中拆出，重新放到对应的下标关于链表元素重哈希的过程为：如果元素哈希值 & 旧的数组容量为 0，那么该元素下标不变，直接尾插法插入新数组；如果元素哈希值 & 旧的数组容量不为 0，那么该元素下标为原下标+旧数组的长度

HashMap 中两个对象的 hashcode 相同时会发生什么？

在 HashMap 中，当两个对象的 hashcode 相同时，这两个对象在哈希数组中的下标相同，会发生"哈希碰撞"；当发生哈希碰撞时，这两个对象会被存储到数组下标对应的链表中。 HashMap面试必问的数据结构相关知识总结 3.当两个对象的 hashCode 相同会发生什么？

HashMap 是怎么解决哈希冲突的？

HashMap为什么不直接使用处理后的hashCode()值作为其哈希数组的下标？

hashCode() 方法的返回值是 int 类型，int 类型的取值范围为 -2^31 ~ 2^31 - 1，而 HashMap 的哈希数组的大小范围在 16~1^30； 很明显，hashcode() 方法生成的哈希值是大于 HashMap 的哈希数组的有效空间的，也就是说，通过 hashcode() 方法生成的哈希值可能落不到哈希数组的有效空间上，因此 HashMap 没有直接使用 hashcode() 的哈希值作为哈希数组的下标

不直接使用 hashCode()作为哈希数组的下标，那 HashMap 是怎么处理其哈希数组的下标的呢？

HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均； 在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；

你知道 hash() 的实现吗？为什么要这样实现？

JDK 1.8 中是通过 hashCode() 的高 16 位异或低 16 位实现的。

为什么要用异或运算符？

保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。

HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？

①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30； ②、loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容； ③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold） ④、如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

HashMap 和 HashTable 有什么区别？

1. 线程安全性不同

HashMap 是线程不安全的，而Hashtable 是线程安全的； HashMap 是 1.2 版本开始加入 JDK 的，是线程不安全的 Map 接口的实现类，具体体现为 HashMap 中的所有方法都没有使用 synchronized 进行修饰； Hashtable 是 1.0 版本开始加入 JDK 的，是线程安全的 Map 接口的实现类，具体体现为 Hashtable 中的所有方法都有使用 synchronized 进行修饰；

2. 效率不同

由于线程安全，所以 HashTable 的效率比不上 HashMap； 由于线程安全，Hashtable 中的所有方法都有使用 synchronized 进行修饰，而 HashMap 中的所有方法都没有使用 synchronized 进行修饰；synchronized 虽然可以保证线程的安全性，但是其性能消耗较大，因此，Hashtable 相对 HashMap 来说性能更差；

3. Hash 数组初始化大小不同

HashMap 默认初始话大小为16，而 Hashtable 默认初始化大小为 11； HashMap 默认初始化大小如下：

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

Hashtable 默认初始化大小如下：

/** * Constructs a new, empty hashtable with a default initial capacity (11) * and load factor (0.75). */ public Hashtable() { this(11, 0.75f); }

4. Hash 数组扩容大小不同

HashMap 扩容时，resize 为原大小的 2 倍；Hashtable 扩容时，rehash 为原大小的 2 倍+1； HashMap 扩若时大小如下：

/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ 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) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // HashMap 扩容时，扩容为原大小的 2 倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } 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); } // ...... // ...... // ...... return newTab; }

Hashtable 扩若时大小如下：

/** * Increases the capacity of and internally reorganizes this * hashtable, in order to accommodate and access its entries more * efficiently. This method is called automatically when the * number of keys in the hashtable exceeds this hashtable's capacity * and load factor. */ @SuppressWarnings("unchecked") protected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; // Hashtable 扩容时扩容为原大小的 2倍+1 // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; // ...... // ...... // ...... }

5. 放入对象时，hashcode 的获取方式不同

在放入对象时，HashMap 会重新计算 hash 值，而 Hashtable 直接使用对象的 hashcode 作为 hash 值； HashMap 放入对象时 hashcode 的获取方式如下：

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { // 在放入对象时，HashMap 会重新计算 hash 值 return putVal(hash(key), key, value, false, true); }

Hashtable 放入对象时 hashcode 的获取方式如下：

private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); // 在放入对象时，Hashtable 直接使用对象的 hashcode 作为 hash 值 tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; }

6. 放入对象时，键-值为空情况不同

HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 Hashtable不允许键-值为空； 放入对象时，HashMap 的键-值要求如下：

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * 放入对象时，HashMap 的键-值都可为空 * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

放入对象时，Hashtable 的键-值要求如下：

/** * Maps the specified <code>key</code> to the specified * <code>value</code> in this hashtable. Neither the key nor the * value can be <code>null</code>. <p> * * 放入对象时，Hashtable 的键-值都不能为空 * * The value can be retrieved by calling the <code>get</code> method * with a key that is equal to the original key. * * @param key the hashtable key * @param value the value * @return the previous value of the specified key in this hashtable, * or <code>null</code> if it did not have one * @exception NullPointerException if the key or value is * <code>null</code> * @see Object#equals(Object) * @see #get(Object) */ public synchronized V put(K key, V value) {}

参考资料

面试：HashMap 夺命二十一问！鸡哥都扛不住~ 问题14

HashMap，LinkedHashMap，TreeMap 有什么区别？

HashMap面试必问的数据结构相关知识总结 问题16

HashMap 参考其他问题； LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢； TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器） HashMap面试必问的数据结构相关知识总结 问题12

HashMap & TreeMap & LinkedHashMap 使用场景？

一般情况下，使用最多的是 HashMap。 HashMap：在 Map 中插入、删除和定位元素时； TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下； LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。 HashMap面试必问的数据结构相关知识总结 问题13

HashMap 与 ConcurrentHashMap 的区别？

1. 线程安全性不同

HashMap 是线程不安全的，而 ConcurrentHashMap 是线程安全的； HashMap 中没有使用任何加锁手段保证线程安全性，而 ConcurrentHashMap 在 JDK1.7 中主要使用分段锁进行加锁，在 JDK1.8 中主要使用 CAS(比较交换) + synchronized 进行加锁； ConcurrentHashMap 在 JDK1.8 中使用 CAS + synchronized 加锁的源码如下：

/** * Maps the specified key to the specified value in this table. * Neither the key nor the value can be null. * * <p>The value can be retrieved by calling the {@code get} method * with a key that is equal to the original key. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with {@code key}, or * {@code null} if there was no mapping for {@code key} * @throws NullPointerException if the specified key or value is null */ 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) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // ConcurrentHashMap 中使用 CAS 保证线程安全性的场景 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; // ConcurrentHashMap 中使用 synchronized 关键字进行加锁的场景 synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; 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; } } } 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) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }

2. 放入对象时，键值对为空情况不同

放入对象时，HashMap 中键-值都可为空，而 ConcurrentHashMap 中键-值都不能为空； 放入对象时，HashMap 中键-值都可为空的源码如下：

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * HashMap 中的键-值都可为空 * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

放入对象时，ConcurrentHashMap 中键-值都不可为空的源码如下：

/** * Maps the specified key to the specified value in this table. * Neither the key nor the value can be null. * * ConcurrentHashMap 中键-值都不能为空 * * <p>The value can be retrieved by calling the {@code get} method * with a key that is equal to the original key. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with {@code key}, or * {@code null} if there was no mapping for {@code key} * @throws NullPointerException if the specified key or value is null */ public V put(K key, V value) { return putVal(key, value, false); }

Java 中另一个线程安全的、与 HashMap 极其类似的类是什么？同样是线程安全，它与 Hashtable 在线程同步上有什么不同？

HashMap面试必问的数据结构相关知识总结 问题15 Java 中另一个与 HashMap 极其相似并且线程安全的类是 ConcurrentHashMap 类。 ConcurrentHashMap 与 Hashtable 的不同主要体现在加锁的方式上： Hashtable 是使用 synchronized 关键字进行加锁，性能较差； 而 ConcurrentHashMap 在 JDK 1.7 中采用的是分段锁，在 JDK 1.8 中采用的是CAS（比较交换）+ synchronized。

为什么 ConcurrentHashMap 比 Hashtable 效率要高？

HashMap面试必问的数据结构相关知识总结 问题15 HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞； ConcurrentHashMap JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

最新回复(0)