APP手机端电子商务网站建设,万网站底部添加备案号,郑州软件培训学校哪个好,怎么做网站页面第9讲 | 对比Hashtable、HashMap、TreeMap有什么不同#xff1f; Map 是广义 Java 集合框架中的另外一部分#xff0c;HashMap 作为框架中使用频率最高的类型之一#xff0c;它本身以及相关类型自然也是面试考察的热点。
今天我要问你的问题是#xff0c;对比 Hashtable、…第9讲 | 对比Hashtable、HashMap、TreeMap有什么不同 Map 是广义 Java 集合框架中的另外一部分HashMap 作为框架中使用频率最高的类型之一它本身以及相关类型自然也是面试考察的热点。
今天我要问你的问题是对比 Hashtable、HashMap、TreeMap 有什么不同谈谈你对 HashMap 的掌握。
典型回答
Hashtable、HashMap、TreeMap 都是最常见的一些 Map 实现是以键值对的形式存储和操作数据的容器类型。
Hashtable 是早期 Java 类库提供的一个哈希表实现本身是同步的不支持 null 键和值由于同步导致的性能开销所以已经很少被推荐使用。
HashMap 是应用更加广泛的哈希表实现行为上大致上与 HashTable 一致主要区别在于 HashMap 不是同步的支持 null 键和值等。通常情况下HashMap 进行 put 或者 get 操作可以达到常数时间的性能所以它是绝大部分利用键值对存取场景的首选比如实现一个用户 ID 和用户信息对应的运行时存储结构。
TreeMap 则是基于红黑树的一种提供顺序访问的 Map和 HashMap 不同它的 get、put、remove 之类操作都是 Olog(n)的时间复杂度具体顺序可以由指定的 Comparator 来决定或者根据键的自然顺序来判断。
考点分析
上面的回答只是对一些基本特征的简单总结针对 Map 相关可以扩展的问题很多从各种数据结构、典型应用场景到程序设计实现的技术考量尤其是在 Java 8 里HashMap 本身发生了非常大的变化这些都是经常考察的方面。
很多朋友向我反馈面试官似乎钟爱考察 HashMap 的设计和实现细节所以今天我会增加相应的源码解读主要专注于下面几个方面
理解 Map 相关类似整体结构尤其是有序数据结构的一些要点。
从源码去分析 HashMap 的设计和实现要点理解容量、负载因子等为什么需要这些参数如何影响 Map 的性能实践中如何取舍等。
理解树化改造的相关原理和改进原因。
除了典型的代码分析还有一些有意思的并发相关问题也经常会被提到如 HashMap 在并发环境可能出现无限循环占用 CPU、size 不准确等诡异的问题。
我认为这是一种典型的使用错误因为 HashMap 明确声明不是线程安全的数据结构如果忽略这一点简单用在多线程场景里难免会出现问题。
理解导致这种错误的原因也是深入理解并发程序运行的好办法。对于具体发生了什么你可以参考这篇很久以前的分析里面甚至提供了示意图我就不再重复别人写好的内容了。
知识扩展
1.Map 整体结构
首先我们先对 Map 相关类型有个整体了解Map 虽然通常被包括在 Java 集合框架里但是其本身并不是狭义上的集合类型Collection具体你可以参考下面这个简单类图。
Hashtable 比较特别作为类似 Vector、Stack 的早期集合相关类型它是扩展了 Dictionary 类的类结构上与 HashMap 之类明显不同。
HashMap 等其他 Map 实现则是都扩展了 AbstractMap里面包含了通用方法抽象。不同 Map 的用途从类图结构就能体现出来设计目的已经体现在不同接口上。
大部分使用 Map 的场景通常就是放入、访问或者删除而对顺序没有特别要求HashMap 在这种情况下基本是最好的选择。HashMap 的性能表现非常依赖于哈希码的有效性请务必掌握 hashCode 和 equals 的一些基本约定比如
equals 相等hashCode 一定要相等。
重写了 hashCode 也要重写 equals。
hashCode 需要保持一致性状态改变返回的哈希值仍然要一致。
equals 的对称、反射、传递等特性。
这方面内容网上有很多资料我就不在这里详细展开了。
针对有序 Map 的分析内容比较有限我再补充一些虽然 LinkedHashMap 和 TreeMap 都可以保证某种顺序但二者还是非常不同的。
LinkedHashMap 通常提供的是遍历顺序符合插入顺序它的实现是通过为条目键值对维护一个双向链表。注意通过特定构造函数我们可以创建反映访问顺序的实例所谓的 put、get、compute 等都算作“访问”。
这种行为适用于一些特定应用场景例如我们构建一个空间占用敏感的资源池希望可以自动将最不常被访问的对象释放掉这就可以利用 LinkedHashMap 提供的机制来实现参考下面的示例 import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapSample {public static void main(String[] args) {LinkedHashMapString, String accessOrderedMap new LinkedHashMapString, String(16, 0.75F, true){Overrideprotected boolean removeEldestEntry(Map.EntryString, String eldest) { // 实现自定义删除策略否则行为就和普遍Map没有区别return size() 3;}};accessOrderedMap.put(Project1, Valhalla);accessOrderedMap.put(Project2, Panama);accessOrderedMap.put(Project3, Loom);accessOrderedMap.forEach( (k,v) - {System.out.println(k : v);});// 模拟访问accessOrderedMap.get(Project2);accessOrderedMap.get(Project2);accessOrderedMap.get(Project3);System.out.println(Iterate over should be not affected:);accessOrderedMap.forEach( (k,v) - {System.out.println(k : v);});// 触发删除accessOrderedMap.put(Project4, Mission Control);System.out.println(Oldest entry should be removed:);accessOrderedMap.forEach( (k,v) - {// 遍历顺序不变System.out.println(k : v);});}
}
对于 TreeMap它的整体顺序是由键的顺序关系决定的通过 Comparator 或 Comparable自然顺序来决定。
我在上一讲留给你的思考题提到了构建一个具有优先级的调度系统的问题其本质就是个典型的优先队列场景Java 标准库提供了基于二叉堆实现的 PriorityQueue它们都是依赖于同一种排序机制当然也包括 TreeMap 的马甲 TreeSet。
类似 hashCode 和 equals 的约定为了避免模棱两可的情况自然顺序同样需要符合一个约定就是 compareTo 的返回值需要和 equals 一致否则就会出现模棱两可情况。
我们可以分析 TreeMap 的 put 方法实现 public V put(K key, V value) {EntryK,V t …cmp k.compareTo(t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);// ...}从代码里你可以看出什么呢 当我不遵守约定时两个不符合唯一性equals要求的对象被当作是同一个因为compareTo 返回 0这会导致歧义的行为表现。
2.HashMap 源码分析
前面提到HashMap 设计与实现是个非常高频的面试题所以我会在这进行相对详细的源码解读主要围绕
HashMap 内部实现基本点分析。
容量capacity和负载系数load factor。
树化 。
首先我们来一起看看 HashMap 内部的结构它可以看作是数组Node[] table和链表结合组成的复合结构数组被分为一个个桶bucket通过哈希值决定了键值对在这个数组的寻址哈希值相同的键值对则以链表形式存储你可以参考下面的示意图。这里需要注意的是如果链表大小超过阈值TREEIFY_THRESHOLD, 8图中的链表就会被改造为树形结构。 从非拷贝构造函数的实现来看这个表格数组似乎并没有在最初就初始化好仅仅设置了一些初始值而已。 public HashMap(int initialCapacity, float loadFactor){ // ... this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);
}
所以我们深刻怀疑HashMap 也许是按照 lazy-load 原则在首次使用时被初始化拷贝构造函数除外我这里仅介绍最通用的场景。既然如此我们去看看 put 方法实现似乎只有一个 putVal 的调用 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}看来主要的秘密似乎藏在 putVal 里面到底有什么秘密呢为了节省空间我这里只截取了 putVal 比较关键的几部分。 final V putVal(int hash, K key, V value, boolean onlyIfAbent,boolean evit) {NodeK,V[] tab; NodeK,V p; int , i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) ull)tab[i] newNode(hash, key, value, nll);else {// ...if (binCount TREEIFY_THRESHOLD - 1) // -1 for first treeifyBin(tab, hash);// ... }
}
从 putVal 方法最初的几行我们就可以发现几个有意思的地方
如果表格是 nullresize 方法会负责初始化它这从 tab resize() 可以看出。
resize 方法兼顾两个职责创建初始存储表格或者在容量不满足需求的时候进行扩容resize。
在放置新的键值对的过程中如果发生下面条件就会发生扩容。
if (size threshold)resize();具体键值对在哈希表中的位置数组 index取决于下面的位运算
i (n - 1) hash仔细观察哈希值的源头我们会发现它并不是 key 本身的 hashCode而是来自于 HashMap 内部的另外一个 hash 方法。注意为什么这里需要将高位数据移位到低位进行异或运算呢这是因为有些数据计算出的哈希值差异主要在高位而 HashMap 里的哈希寻址是忽略容量以上的高位的那么这种处理就可以有效避免类似情况下的哈希碰撞。 static final int hash(Object kye) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16;
}我前面提到的链表结构这里叫 bin会在达到一定门限值时发生树化我稍后会分析为什么 HashMap 需要对 bin 进行处理。
可以看到putVal 方法本身逻辑非常集中从初始化、扩容到树化全部都和它有关推荐你阅读源码的时候可以参考上面的主要逻辑。
我进一步分析一下身兼多职的 resize 方法很多朋友都反馈经常被面试官追问它的源码设计。 final NodeK,V[] resize() {// ...else if ((newCap oldCap 1) MAXIMUM_CAPACIY oldCap DEFAULT_INITIAL_CAPAITY)newThr oldThr 1; // double there// ... else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsfultsnewCap DEFAULT_INITIAL_CAPAITY;newThr (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY}if (newThr 0) {float ft (float)newCap * loadFator;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold neThr;NodeK,V[] newTab (NodeK,V[])new Node[newap];table n// 移动到新的数组结构e数组结构 }
依据 resize 源码不考虑极端情况容量理论最大极限由 MAXIMUM_CAPACITY 指定数值为 130也就是 2 的 30 次方我们可以归纳为
门限值等于负载因子x容量如果构建 HashMap 的时候没有指定它们那么就是依据相应的默认常量值。
门限通常是以倍数进行调整 newThr oldThr 1我前面提到根据 putVal 中的逻辑当元素个数超过门限大小时则调整 Map 大小。
扩容后需要将老的数组中的元素重新放置到新的数组这是扩容的一个主要开销来源。 容量、负载因子和树化 前面我们快速梳理了一下 HashMap 从创建到放入键值对的相关逻辑现在思考一下为什么我们需要在乎容量和负载因子呢 这是因为容量和负载系数决定了可用的桶的数量空桶太多会浪费空间如果使用的太满则会严重影响操作的性能。极端情况下假设只有一个桶那么它就退化成了链表完全不能提供所谓常数时间存的性能。 既然容量和负载因子这么重要我们在实践中应该如何选择呢 如果能够知道 HashMap 要存取的键值对数量可以考虑预先设置合适的容量大小。具体数值我们可以根据扩容发生的条件来做简单预估根据前面的代码分析我们知道它需要符合计算条件 负载因子 * 容量 元素数量所以预先设置的容量需要满足大于“预估元素数量 / 负载因子”同时它是 2 的幂数结论已经非常清晰了。 而对于负载因子我建议 如果没有特别需求不要轻易进行更改因为 JDK 自身的默认负载因子是非常符合通用场景的需求的。 如果确实需要调整建议不要设置超过 0.75 的数值因为会显著增加冲突降低 HashMap 的性能。 如果使用太小的负载因子按照上面的公式预设容量值也进行调整否则可能会导致更加频繁的扩容增加无谓的开销本身访问性能也会受影响。 我们前面提到了树化改造对应逻辑主要在 putVal 和 treeifyBin 中。 final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();else if ((e tab[index (n - 1) hash]) ! null) {//树化改造逻辑}
}
上面是精简过的 treeifyBin 示意综合这两个方法树化改造的逻辑就非常清晰了可以理解为当 bin 的数量大于 TREEIFY_THRESHOLD 时
如果容量小于 MIN_TREEIFY_CAPACITY只会进行简单的扩容。
如果容量大于 MIN_TREEIFY_CAPACITY 则会进行树化改造。
那么为什么 HashMap 要树化呢
本质上这是个安全问题。因为在元素放置过程中如果一个对象哈希冲突都被放置到同一个桶里则会形成一个链表我们知道链表查询是线性的会严重影响存取的性能。
而在现实世界构造哈希冲突的数据并不是非常复杂的事情恶意代码就可以利用这些数据大量与服务器端交互导致服务器端 CPU 大量占用这就构成了哈希碰撞拒绝服务攻击国内一线互联网公司就发生过类似攻击事件。
今天我从 Map 相关的几种实现对比对各种 Map 进行了分析讲解了有序集合类型容易混淆的地方并从源码级别分析了 HashMap 的基本结构希望对你有所帮助。
一课一练
关于今天我们讨论的题目你做到心中有数了吗留一道思考题给你解决哈希冲突有哪些典型方法呢
请你在留言区写写你对这个问题的思考我会选出经过认真思考的留言送给你一份学习鼓励金欢迎你与我一起讨论。
过程中如果一个对象哈希冲突都被放置到同一个桶里则会形成一个链表我们知道链表查询是线性的会严重影响存取的性能。
而在现实世界构造哈希冲突的数据并不是非常复杂的事情恶意代码就可以利用这些数据大量与服务器端交互导致服务器端 CPU 大量占用这就构成了哈希碰撞拒绝服务攻击国内一线互联网公司就发生过类似攻击事件。
今天我从 Map 相关的几种实现对比对各种 Map 进行了分析讲解了有序集合类型容易混淆的地方并从源码级别分析了 HashMap 的基本结构希望对你有所帮助。
一课一练
关于今天我们讨论的题目你做到心中有数了吗留一道思考题给你解决哈希冲突有哪些典型方法呢
请你在留言区写写你对这个问题的思考我会选出经过认真思考的留言送给你一份学习鼓励金欢迎你与我一起讨论。
你的朋友是不是也在准备面试呢你可以“请朋友读”把今天的题目分享给好友或许你能帮到他。
