网站制作需要的软件,注册企业邮箱需要什么,网站建设毕业设计报告书,莱芜网站建设sikesoft来源 | Java 建设者责编 | Carol封图 | CSDN 下载自视觉中国#xff08;如果你没有时间细抠本文#xff0c;可以直接看 HashMap 概述#xff0c;能让你对 HashMap 有个大致的了解#xff09;HashMap 是 Map 接口的实现#xff0c;HashMap 允许空的 key-value 键值对#… 来源 | Java 建设者责编 | Carol封图 | CSDN 下载自视觉中国如果你没有时间细抠本文可以直接看 HashMap 概述能让你对 HashMap 有个大致的了解HashMap 是 Map 接口的实现HashMap 允许空的 key-value 键值对HashMap 被认为是 Hashtable 的增强版HashMap 是一个非线程安全的容器如果想构造线程安全的 Map 考虑使用 ConcurrentHashMap。HashMap 是无序的因为 HashMap 无法保证内部存储的键值对的有序性。HashMap 的底层数据结构是数组 链表的集合体数组在 HashMap 中又被称为桶(bucket)。遍历 HashMap 需要的时间损耗为 HashMap 实例桶的数量 (key - value 映射) 的数量。因此如果遍历元素很重要的话不要把初始容量设置的太高或者负载因子设置的太低。HashMap 实例有两个很重要的因素初始容量和负载因子初始容量指的就是 hash 表桶的数量负载因子是一种衡量哈希表填充程度的标准当哈希表中存在足够数量的 entry以至于超过了负载因子和当前容量这个哈希表会进行 rehash 操作内部的数据结构重新 rebuilt。注意 HashMap 不是线程安全的如果多个线程同时影响了 HashMap 并且至少一个线程修改了 HashMap 的结构那么必须对 HashMap 进行同步操作。可以使用 Collections.synchronizedMap(new HashMap) 来创建一个线程安全的 Map。HashMap 会导致除了迭代器本身的 remove 外外部 remove 方法都可能会导致 fail-fast 机制因此尽量要用迭代器自己的 remove 方法。如果在迭代器创建的过程中修改了 map 的结构就会抛出 ConcurrentModificationException 异常。下面就来聊一聊 HashMap 的细节问题。我们还是从面试题入手来分析 HashMap 。HashMap 和 HashTable 的区别我们上面介绍了一下 HashMap 现在来介绍一下 HashTable。相同点HashMap 和 HashTable 都是基于哈希表实现的其内部每个元素都是 key-value 键值对HashMap 和 HashTable 都实现了 Map、Cloneable、Serializable 接口。不同点父类不同HashMap 继承了 AbstractMap 类而 HashTable 继承了 Dictionary 类空值不同HashMap 允许空的 key 和 value 值HashTable 不允许空的 key 和 value 值。HashMap 会把 Null key 当做普通的 key 对待。不允许 null key 重复。线程安全性HashMap 不是线程安全的如果多个外部操作同时修改 HashMap 的数据结构比如 add 或者是 delete必须进行同步操作仅仅对 key 或者 value 的修改不是改变数据结构的操作。可以选择构造线程安全的 Map 比如 Collections.synchronizedMap 或者是 ConcurrentHashMap。而 HashTable 本身就是线程安全的容器。性能方面虽然 HashMap 和 HashTable 都是基于单链表的但是 HashMap 进行 put 或者 get???? 操作可以达到常数时间的性能而 HashTable 的 put 和 get 操作都是加了 synchronized 锁的所以效率很差。初始容量不同HashTable 的初始长度是11之后每次扩充容量变为之前的 2n1n为上一次的长度而 HashMap 的初始长度为16之后每次扩充变为原来的两倍。创建时如果给定了容量初始值那么HashTable 会直接使用你给定的大小而 HashMap 会将其扩充为2的幂次方大小。HashMap 和 HashSet 的区别也经常会问到 HashMap 和 HashSet 的区别HashSet 继承于 AbstractSet 接口实现了 Set、Cloneable,、java.io.Serializable 接口。HashSet 不允许集合中出现重复的值。HashSet 底层其实就是 HashMap所有对 HashSet 的操作其实就是对 HashMap 的操作。所以 HashSet 也不保证集合的顺序。HashMap 底层结构要了解一个类先要了解这个类的结构先来看一下 HashMap 的结构最主要的三个类(接口)就是 HashMap,AbstractMap和 Map 了HashMap 我们上面已经在概述中简单介绍了一下下面来介绍一下 AbstractMap。AbstractMap 类这个抽象类是 Map 接口的骨干实现以求最大化的减少实现类的工作量。为了实现不可修改的 map程序员仅需要继承这个类并且提供 entrySet 方法的实现即可。它将会返回一组 map 映射的某一段。通常返回的集合将在AbstractSet 之上实现。这个set不应该支持 add 或者 remove 方法并且它的迭代器也不支持 remove 方法。为了实现可修改的 map程序员必须额外重写这个类的 put 方法(否则就会抛出UnsupportedOperationException)并且 entrySet.iterator() 返回的 iterator 必须实现 remove() 方法。Map 接口Map 接口定义了 key-value 键值对的标准。一个对象支持 key-value 存储。Map不能包含重复的 key每个键最多映射一个值。这个接口代替了Dictionary 类Dictionary是一个抽象类而不是接口。Map 接口提供了三个集合的构造器它允许将 map 的内容视为一组键值集合或一组键值映射。map的顺序定义为map映射集合上的迭代器返回其元素的顺序。一些map实现像是TreeMap类保证了map的有序性其他的实现像是HashMap则没有保证。重要内部类和接口Node 接口Node节点是用来存储HashMap的一个个实例它实现了 Map.Entry接口我们先来看一下 Map中的内部接口 Entry 接口的定义Map.Entry// 一个map 的entry 链这个Map.entrySet()方法返回一个集合的视图包含类中的元素
// 这个唯一的方式是从集合的视图进行迭代获取一个map的entry链。这些Map.Entry链只在
// 迭代期间有效。
interface EntryK,V {K getKey();V getValue();V setValue(V value);boolean equals(Object o);int hashCode();
}Node 节点会存储四个属性hash值keyvalue指向下一个Node节点的引用 // hash值
final int hash;
// 键
final K key;
// 值
V value;
// 指向下一个Node节点的Node类型
NodeK,V next;因为Map.Entry 是一条条entry 链连接在一起的所以Node节点也是一条条entry链。构造一个新的HashMap实例的时候会把这四个属性值分为传入Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;
}实现了 Map.Entry 接口所以必须实现其中的方法所以 Node 节点中也包括上面的五个方法KeySet 内部类keySet 类继承于 AbstractSet 抽象类它是由 HashMap 中的 keyset() 方法来创建 KeySet 实例的旨在对HashMap 中的key键进行操作看一个代码示例图中把「1, 2, 3」这三个key 放在了HashMap中然后使用 lambda 表达式循环遍历 key 值可以看到map.keySet() 其实是返回了一个 Set 接口KeySet() 是在 Map 接口中进行定义的不过是被HashMap 进行了实现操作来看一下源码就明白了// 返回一个set视图这个视图中包含了map中的key。
public SetK keySet() {// // keySet 指向的是 AbstractMap 中的 keysetSetK ks keySet;if (ks null) {// 如果 ks 为空就创建一个 KeySet 对象// 并对 ks 赋值。ks new KeySet();keySet ks;}return ks;
}所以 KeySet 类中都是对 Map中的 Key 进行操作的Values 内部类Values 类的创建其实是和 KeySet 类很相似不过 KeySet 旨在对 Map中的键进行操作Values 旨在对key-value 键值对中的 value 值进行使用看一下代码示例循环遍历 Map中的 values值看一下 values() 方法最终创建的是什么public CollectionV values() {// values 其实是 AbstractMap 中的 valuesCollectionV vs values;if (vs null) {vs new Values();values vs;}return vs;
}所有的 values 其实都存储在 AbstractMap 中而 Values 类其实也是实现了 Map 中的 Values 接口看一下对 values 的操作都有哪些方法其实是和 key 的操作差不多EntrySet 内部类上面提到了HashMap中分别有对 key、value 进行操作的其实还有对 key-value 键值对进行操作的内部类它就是 EntrySet来看一下EntrySet 的创建过程点进去 entrySet() 会发现这个方法也是在 Map 接口中定义的HashMap对它进行了重写// 返回一个 set 视图此视图包含了 map 中的key-value 键值对
public SetMap.EntryK,V entrySet() {SetMap.EntryK,V es;return (es entrySet) null ? (entrySet new EntrySet()) : es;
}如果 es 为空创建一个新的 EntrySet 实例EntrySet 主要包括了对key-value 键值对映射的方法如下HashMap 1.7 的底层结构JDK1.7 中HashMap 采用位桶 链表的实现即使用链表来处理冲突同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多即 hash 值相等的元素较多时通过 key 值依次查找的效率较低。它的数据结构如下HashMap 大致结构HashMap 底层数据结构就是一个 Entry 数组Entry 是 HashMap 的基本组成单元每个 Entry 中包含一个 key-value 键值对。transient EntryK,V[] table (EntryK,V[]) EMPTY_TABLE;而每个 Entry 中包含 「hash, key ,value」 属性它是 HashMap 的一个内部类static class EntryK,V implements Map.EntryK,V {final K key;V value;EntryK,V next;int hash;Entry(int h, K k, V v, EntryK,V n) {value v;next n;key k;hash h;}...
}所以HashMap 的整体结构就像下面这样HashMap 1.8 的底层结构与 JDK 1.7 相比1.8 在底层结构方面做了一些改变当每个桶中元素大于 8 的时候会转变为红黑树目的就是优化查询效率JDK 1.8 重写了 resize() 方法。HashMap 重要属性「初始容量」HashMap 的默认初始容量是由 DEFAULT_INITIAL_CAPACITY 属性管理的。static final int DEFAULT_INITIAL_CAPACITY 1 4;HashMap 的默认初始容量是 1 4 16 是一个左移操作它相当于是「最大容量」HashMap 的最大容量是static final int MAXIMUM_CAPACITY 1 30;这里是不是有个疑问int 占用四个字节按说最大容量应该是左移 31 位为什么 HashMap 最大容量是左移 30 位呢因为在数值计算中最高位也就是最左位的位 是代表着符号为0 - 正数1 - 负数容量不可能是负数所以 HashMap 最高位只能移位到 2 ^ 30 次幂。「默认负载因子」HashMap 的默认负载因子是static final float DEFAULT_LOAD_FACTOR 0.75f;float 类型所以用 .f 为单位负载因子是和扩容机制有关这里大致提一下后面会细说。扩容机制的原则是当 HashMap 中存储的数量 HashMap 容量 * 负载因子时就会把 HashMap 的容量扩大为原来的二倍。HashMap 的第一次扩容就在 DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR 12 时进行。「树化阈值」HashMap 的树化阈值是static final int TREEIFY_THRESHOLD 8;在进行添加元素时当一个桶中存储元素的数量 8 时会自动转换为红黑树JDK1.8 特性。「链表阈值」HashMap 的链表阈值是static final int UNTREEIFY_THRESHOLD 6;在进行删除元素时如果一个桶中存储元素数量 6 后会自动转换为链表「扩容临界值」static final int MIN_TREEIFY_CAPACITY 64;这个值表示的是当桶数组容量小于该值时优先进行扩容而不是树化「节点数组」HashMap 中的节点数组就是 Entry 数组它代表的就是 HashMap 中 「数组 链表」 数据结构中的数组。transient NodeK,V[] table;Node 数组在第一次使用的时候进行初始化操作在必要的时候进行 resizeresize 后数组的长度扩容为原来的二倍。「键值对数量」在 HashMap 中使用 size 来表示 HashMap 中键值对的数量。「修改次数」在 HashMap 中使用 modCount 来表示修改次数主要用于做并发修改 HashMap 时的快速失败 - fail-fast 机制。「扩容阈值」在 HashMap 中使用 threshold 表示扩容的阈值也就是 初始容量 * 负载因子的值。threshold 涉及到一个扩容的阈值问题这个问题是由 tableSizeFor 源码解决的。我们先看一下它的源码再来解释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;
}代码中涉及一个运算符 | 它表示的是按位或啥意思呢你一定知道 「ab 的意思是 aab」那么同理a | b 就是 a a | b也就是双方都转换为二进制来进行与操作。如下图所示我们上面采用了一个比较大的数字进行扩容由上图可知 2^29 次方的数组经过一系列的或操作后会算出来结果是 2^30 次方。所以扩容后的数组长度是原来的 2 倍。「负载因子」loadFactor 表示负载因子它表示的是 HashMap 中的密集程度。HashMap 构造函数在 HashMap 源码中有四种构造函数分别来介绍一下带有初始容量 initialCapacity 和 负载因子 loadFactor 的构造函数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);
}初始容量不能为负所以当传递初始容量 0 的时候会直接抛出 IllegalArgumentException 异常。如果传递进来的初始容量 最大容量时初始容量 最大容量。负载因子也不能小于 0 。然后进行数组的扩容这个扩容机制也非常重要我们后面进行探讨只带有 initialCapacity 的构造函数public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}最终也会调用到上面的构造函数不过这个默认的负载因子就是 HashMap 的默认负载因子也就是 0.75f无参数的构造函数public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR;
}默认的负载因子也就是 0.75f带有 map 的构造函数public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}带有 Map 的构造函数会直接把外部元素批量放入 HashMap 中。讲一讲 HashMap put 的全过程我记得刚毕业一年去北京面试一家公司问我 HashMap put 过程的时候我支支吾吾答不上来后面痛下决心好好整。以 JDK 1.8 为基准进行分析后面也是。先贴出整段代码后面会逐行进行分析。final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;// 如果table 为null 或者没有为 table 分配内存就resize一次if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// 指定hash值节点为空则直接插入这个(n - 1) hash才是表中真正的哈希if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);// 如果不为空else {NodeK,V e; K k;// 计算表中的这个真正的哈希值与要插入的key.hash相比if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;// 若不同的话并且当前节点已经在 TreeNode 上了else if (p instanceof TreeNode)// 采用红黑树存储方式e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);// key.hash 不同并且也不再 TreeNode 上在链表上找到 p.nextnullelse {for (int binCount 0; ; binCount) {if ((e p.next) null) {// 在表尾插入p.next newNode(hash, key, value, null);// 新增节点后如果节点个数到达阈值则进入 treeifyBin() 进行再次判断if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果找到了同 hash、key 的节点那么直接退出循环if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;// 更新 p 指向下一节点p e;}}// map中含有旧值返回旧值if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}// map调整次数 1modCount;// 键值对的数量达到阈值需要扩容if (size threshold)resize();afterNodeInsertion(evict);return null;
}首先看一下 putVal 方法这个方法是 final 的如果你自已定义 HashMap 继承的话是不允许你自己重写 put 方法的然后这个方法涉及五个参数hash - put 放在桶中的位置在 put 之前会进行 hash 函数的计算。key - 参数的 key 值value - 参数的 value 值onlyIfAbsent - 是否改变已经存在的值也就是是否进行 value 值的替换标志evict - 是否是刚创建 HashMap 的标志在调用到 putVal 方法时首先会进行 hash 函数计算应该插入的位置public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}哈希函数的源码如下static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}首先先来理解一下 hash 函数的计算规则Hash 函数hash 函数会根据你传递的 key 值进行计算首先计算 key 的 hashCode 值然后再对 hashcode 进行无符号右移操作最后再和 hashCode 进行异或 ^ 操作。❝: 无符号右移操作它指的是 「无符号右移也叫逻辑右移即若该数为正则高位补0而若该数为负数则右移后高位同样补0」 也就是不管是正数还是负数右移都会在空缺位补 0 。❞在得到 hash 值后就会进行 put 过程。首先会判断 HashMap 中的 Node 数组是否为 null如果第一次创建 HashMap 并进行第一次插入元素首先会进行数组的 resize也就是重新分配这里还涉及到一个 resize() 扩容机制源码分析我们后面会介绍。扩容完毕后会计算出 HashMap 的存放位置通过使用 「( n - 1 ) hash」 进行计算得出。然后会把这个位置作为数组的下标作为存放元素的位置。如果不为空那么计算表中的这个真正的哈希值与要插入的 key.hash 相比。如果哈希值相同key-value 不一样再判断是否是树的实例如果是的话那么就把它插入到树上。如果不是就执行尾插法在 entry 链尾进行插入。会根据桶中元素的数量判断是链表还是红黑树。然后判断键值对数量是否大于阈值大于的话则进行扩容。扩容机制在 Java 中数组的长度是固定的这意味着数组只能存储固定量的数据。但在开发的过程中很多时候我们无法知道该建多大的数组合适。好在 HashMap 是一种自动扩容的数据结构在这种基于变长的数据结构中扩容机制是非常重要的。在 HashMap 中阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时进行扩容。HashMap 中的扩容机制是由 resize() 方法来实现的下面我们就来一次认识下。贴出中文注释便于复制final NodeK,V[] resize() {NodeK,V[] oldTab table;// 存储old table 的大小int oldCap (oldTab null) ? 0 : oldTab.length;// 存储扩容阈值int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {// 如果old table数据已达最大那么threshold也被设置成最大if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}// 左移扩大二倍,else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 扩容成原来二倍newThr oldThr 1; // double threshold}// 如果oldThr ! 0else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;// 如果old table 0 并且 存储的阈值 0else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果扩充阈值为0if (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;// 如果第一次进行table 初始化不会走下面的代码// 扩容之后需要重新把节点放在新扩容的数组中if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,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)// 重新映射时需要对红黑树进行拆分((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;// 遍历链表并将链表节点按原顺序进行分组do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail 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;
}扩容机制源码比较长我们耐心点进行拆分我们以 if...else if...else 逻辑进行拆分上面代码主要做了这几个事情判断 HashMap 中的数组的长度也就是 (NodeK,V[])oldTab.length() 再判断数组的长度是否比最大的的长度也就是 2^30 次幂要大大的话直接取最大长度否则利用位运算 扩容为原来的两倍如果数组长度不大于0 再判断扩容阈值 threshold 是否大于 0 也就是看有无外部指定的扩容阈值若有则使用这里需要说明一下 threshold 何时是 oldThr 0因为 oldThr threshold 这里其实比较的就是 threshold因为 HashMap 中的每个构造方法都会调用 HashMap(initCapacity,loadFactor) 这个构造方法所以如果没有外部指定 initialCapacity初始容量使用的就是 16然后根据 this.threshold tableSizeFor(initialCapacity); 求得 threshold 的值。否则直接使用默认的初始容量和扩容阈值走 else 的逻辑是在 table 刚刚初始化的时候。然后会判断 newThr 是否为 0 笔者在刚开始研究时发现 newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 一直以为这是常量做乘法怎么会为 0 其实不是这部分的问题在于上面逻辑判断中的扩容操作可能会导致位溢出。导致位溢出的示例oldCap 2^28 次幂threshold 2 的三次方整数次幂。在进入到 float ft (float)newCap * loadFactor; 这个方法是 2^28 * 2^(3n) 会直接 2^31 次幂导致全部归零。「在扩容后需要把节点放在新扩容的数组中这里也涉及到三个步骤」循环桶中的每个 Node 节点判断 Node[i] 是否为空为空直接返回不为空则遍历桶数组并将键值对映射到新的桶数组中。如果不为空再判断是否是树形结构如果是树形结构则按照树形结构进行拆分拆分方法在 split 方法中。如果不是树形结构则遍历链表并将链表节点按原顺序进行分组。讲一讲 get 方法全过程我们上面讲了 HashMap 中的 put 方法全过程下面我们来看一下 get 方法的过程public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;// 找到真实的元素位置if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {// 总是会check 一下第一个元素if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;// 如果不是第一个元素并且下一个元素不是空的if ((e first.next) ! null) {// 判断是否属于 TreeNode如果是 TreeNode 实例直接从 TreeNode.getTreeNode 取if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);// 如果还不是 TreeNode 实例就直接循环数组元素直到找到指定元素位置do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
}来简单介绍下吧首先会检查 table 中的元素是否为空然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空如果不为空是否匹配如果匹配直接返回这条记录如果匹配再判断下一个元素的值是否为 null为空直接返回如果不为空再判断是否是 TreeNode 实例如果是 TreeNode 实例则直接使用 TreeNode.getTreeNode 取出元素否则执行循环直到下一个元素为 null 位置。getNode 方法有一个比较重要的过程就是 「(n - 1) hash」这段代码是确定需要查找的桶的位置的那么为什么要 (n - 1) hash 呢n 就是 HashMap 中桶的数量这句话的意思也就是说 (n - 1) hash 就是 (桶的容量 - 1) hash// 为什么 HashMap 的检索位置是 (table.size - 1) hash
public static void main(String[] args) {MapString,Object map new HashMap();// debug 得知 1 的 hash 值算出来是 49map.put(1,cxuan);// debug 得知 1 的 hash 值算出来是 50map.put(2,cxuan);// debug 得知 1 的 hash 值算出来是 51map.put(3,cxuan);}那么每次算完之后的 (n - 1) hash 依次为也就是 「tab[(n - 1) hash]」 算出的具体位置。HashMap 的遍历方式HashMap 的遍历也是一个使用频次特别高的操作HashMap 遍历的基类是 HashIterator它是一个 Hash 迭代器它是一个 HashMap 内部的抽象类它的构造比较简单只有三种方法「hasNext 、 remove 和 nextNode」 方法其中 nextNode 方法是由三种迭代器实现的这三种迭代器就就是KeyIterator 对 key 进行遍历ValueIterator对 value 进行遍历EntryIterator 对 Entry 链进行遍历虽然说看着迭代器比较多但其实他们的遍历顺序都是一样的构造也非常简单都是使用 HashIterator 中的 nextNode 方法进行遍历final class KeyIterator extends HashIteratorimplements IteratorK {public final K next() { return nextNode().key; }}final class ValueIterator extends HashIteratorimplements IteratorV {public final V next() { return nextNode().value; }
}final class EntryIterator extends HashIteratorimplements IteratorMap.EntryK,V {public final Map.EntryK,V next() { return nextNode(); }
}HashIterator 中的遍历方式abstract class HashIterator {NodeK,V next; // 下一个 entry 节点NodeK,V current; // 当前 entry 节点int expectedModCount; // fail-fast 的判断标识int index; // 当前槽HashIterator() {expectedModCount modCount;NodeK,V[] t table;current next null;index 0;if (t ! null size 0) { // advance to first entrydo {} while (index t.length (next t[index]) null);}}public final boolean hasNext() {return next ! null;}final NodeK,V nextNode() {NodeK,V[] t;NodeK,V e next;if (modCount ! expectedModCount)throw new ConcurrentModificationException();if (e null)throw new NoSuchElementException();if ((next (current e).next) null (t table) ! null) {do {} while (index t.length (next t[index]) null);}return e;}public final void remove() {...}
}next 和 current 分别表示下一个 Node 节点和当前的 Node 节点HashIterator 在初始化时会遍历所有的节点。下面我们用图来表示一下他们的遍历顺序你会发现 nextNode() 方法的遍历方式和 HashIterator 的遍历方式一样只不过判断条件不一样构造 HashIterator 的时候判断条件是有没有链表桶是否为 null而遍历 nextNode 的判断条件变为下一个 node 节点是不是 null 并且桶是不是为 null。HashMap 中的移除方法HashMap 中的移除方法也比较简单了源码如下public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ?null : e.value;
}final NodeK,V removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))node p;else if ((e p.next) ! null) {if (p instanceof TreeNode)node ((TreeNodeK,V)p).getTreeNode(hash, key);else {do {if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}if (node ! null (!matchValue || (v node.value) value ||(value ! null value.equals(v)))) {if (node instanceof TreeNode)((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)tab[index] node.next;elsep.next node.next;modCount;--size;afterNodeRemoval(node);return node;}}return null;
}remove 方法有很多最终都会调用到 removeNode 方法只不过传递的参数值不同我们拿 remove(object) 来演示一下。首先会通过 hash 来找到对应的 bucket然后通过遍历链表找到键值相等的节点然后把对应的节点进行删除。关于 HashMap 的面试题HashMap 的数据结构JDK1.7 中HashMap 采用位桶 链表的实现即使用链表来处理冲突同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多即 hash 值相等的元素较多时通过 key 值依次查找的效率较低。所以与 JDK 1.7 相比JDK 1.8 在底层结构方面做了一些改变当每个桶中元素大于 8 的时候会转变为红黑树目的就是优化查询效率。HashMap 的 put 过程大致过程如下首先会使用 hash 方法计算对象的哈希码根据哈希码来确定在 bucket 中存放的位置如果 bucket 中没有 Node 节点则直接进行 put如果对应 bucket 已经有 Node 节点会对链表长度进行分析判断长度是否大于 8如果链表长度小于 8 在 JDK1.7 前会使用头插法在 JDK1.8 之后更改为尾插法。如果链表长度大于 8 会进行树化操作把链表转换为红黑树在红黑树上进行存储。HashMap 为啥线程不安全HashMap 不是一个线程安全的容器不安全性体现在多线程并发对 HashMap 进行 put 操作上。如果有两个线程 A 和 B 首先 A 希望插入一个键值对到 HashMap 中在决定好桶的位置进行 put 时此时 A 的时间片正好用完了轮到 B 运行B 运行后执行和 A 一样的操作只不过 B 成功把键值对插入进去了。如果 A 和 B 插入的位置桶是一样的那么线程 A 继续执行后就会覆盖 B 的记录造成了数据不一致问题。还有一点在于 HashMap 在扩容时因 resize 方法会形成环造成死循环导致 CPU 飙高。HashMap 是如何处理哈希碰撞的HashMap 底层是使用位桶 链表实现的位桶决定元素的插入位置位桶是由 hash 方法决定的当多个元素的 hash 计算得到相同的哈希值后HashMap 会把多个 Node 元素都放在对应的位桶中形成链表这种处理哈希碰撞的方式被称为链地址法。其他处理 hash 碰撞的方式还有 「开放地址法、rehash 方法、建立一个公共溢出区」这几种方法。HashMap 是如何 get 元素的首先会检查 table 中的元素是否为空然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空如果不为空是否匹配如果匹配直接返回这条记录如果匹配再判断下一个元素的值是否为 null为空直接返回如果不为空再判断是否是 TreeNode 实例如果是 TreeNode 实例则直接使用 TreeNode.getTreeNode 取出元素否则执行循环直到下一个元素为 null 位置。HashMap 和 HashTable 有什么区别见上HashMap 和 HashSet 的区别见上HashMap 是如何扩容的HashMap 中有两个非常重要的变量一个是 loadFactor 一个是 threshold loadFactor 表示的就是负载因子threshold 表示的是下一次要扩容的阈值当 threshold loadFactor * 数组长度时数组长度扩大位原来的两倍来重新调整 map 的大小并将原来的对象放入新的 bucket 数组中。HashMap 的长度为什么是 2 的幂次方这道题我想了几天之前和群里小伙伴们探讨每日一题的时候问他们为什么 length%hash (n - 1) hash它们说相等的前提是 length 的长度 2 的幂次方然后我回了一句难道 length 还能不是 2 的幂次方吗其实是我没有搞懂因果关系因为 HashMap 的长度是 2 的幂次方所以使用余数来判断在桶中的下标。如果 length 的长度不是 2 的幂次方小伙伴们可以举个例子来试试。例如长度为 9 时候3 (9-1) 02 (9-1) 0 都在 0 上碰撞了这样会增大 HashMap 碰撞的几率。HashMap 线程安全的实现有哪些因为 HashMap 不是一个线程安全的容器所以并发场景下推荐使用 ConcurrentHashMap 或者使用线程安全的 HashMap使用 Collections 包下的线程安全的容器比如说Collections.synchronizedMap(new HashMap());还可以使用 HashTable 它也是线程安全的容器基于 key-value 存储经常用 HashMap 和 HashTable 做比较就是因为 HashTable 的数据结构和 HashMap 相同。上面效率最高的就是 ConcurrentHashMap。文章并没有叙述太多关于红黑树的构造、包含添加、删除、树化等过程一方面是自己能力还达不到一方面是关于红黑树的描述太过于占据篇幅红黑树又是很大的一部分内容所以会考虑放在后续的红黑树进行讲解。推荐阅读
浅谈分布式存储中的网络通信138 张图带你 MySQL 入门如何在 Kubernetes 上配置 Jenkins突发印度封禁抖音、微信、快手等 59 款中国 App厉害国内大学生计算机编程第一人一人挑战一个队百度最年轻 T10现创业自动驾驶Balancer因通缩代币STA遭遇闪电贷攻击价值50万美元资产被黑浅谈分布式存储中的网络通信真香朕在看了
