做网站建设业务,扬中网站建设流程,dw怎么做鲜花网站,wordpress 主题 函数目录一. #x1f981; HashMap介绍1.1 特点1.2 底层实现二. #x1f981; 结构以及对应方法分析2.1 结构组成2.1.1 成员变量2.1.2 存储元素的节点类型2.1.2.1 链表Node类2.1.2.2 树节点类2.1.2.3 继承关系2.2 方法实现2.2.1 HashMap的数组初始化2.2.2 计算hash值2.2.3 添加元…
目录一. HashMap介绍1.1 特点1.2 底层实现二. 结构以及对应方法分析2.1 结构组成2.1.1 成员变量2.1.2 存储元素的节点类型2.1.2.1 链表Node类2.1.2.2 树节点类2.1.2.3 继承关系2.2 方法实现2.2.1 HashMap的数组初始化2.2.2 计算hash值2.2.3 添加元素putK keyV value方法2.2.4 数组扩容三. 总结一. HashMap介绍
1.1 特点
HashMap 是 Map 接口的接口实现类它采用哈希算法实现是 Map 接口最常用的实现类。 由于底层采用了哈希表存储数据所以要求键不能重复如果发生重复新的值会替换旧的值。 HashMap 在查找、删除、修改方面都有非常高的效率。
1.2 底层实现
HashMap 底层实现采用了哈希表既集合了数组占用空间连续。 寻址容易查询速度快的优点又集合了链表增加和删除效率非常高的优点。其实哈希表的本质就是”数组链表“。
二. 结构以及对应方法分析
在HashMap中当维互链表节点个数的过程中链表节点数大于8时则会转化成红黑树来存储从而提高查询效率。
2.1 结构组成
2.1.1 成员变量 DEFAULT_INITIAL_CAPACITY 1 4 默认的初始容量为16而且注解有说明这个默认初始化容量必须是2的倍数。 MAXIMUM_CAPACITY 1 30:最大初始化容量为2^30。 DEFAULT_LOAD_FACTOR 0.75f负载因子用来决定数组什么时候开始扩容即当数组长度达到75%时会进行扩容。 TREEIFY_THRESHOLD 8阈值当前数组长度64,会将节点个数大于8的链表做红黑树转换。 UNTREEIFY_THRESHOLD 6同理当红黑树节点数小于6时将这个红黑树转换成链表。 MIN_TREEIFY_CAPACITY 64设置当数组长度超过多少时才会对链表节点个数大于8的做红黑树转换。 transient NodeK,V[] table就是前面说的神秘的数组。为啥是NodeK,Vl类型 /*** 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 130.*/static final int MAXIMUM_CAPACITY 1 30;/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR 0.75f;/*** 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;/*** 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 NodeK,V[] table;2.1.2 存储元素的节点类型
既然说了哈希表是由数组链表组成而且到后面还会转为红黑树那么他肯定会有对应的节点类。其源码类型如下
2.1.2.1 链表Node类 /*** Basic hash bin node, used for most entries. (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue value;value newValue;return oldValue;}public final boolean equals(Object o) {if (o this)return true;if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?)o;if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true;}return false;}}由源码可知链表的Node节点类型实现了Map接口的内部接口类EntryKV这个接口定义的就是能操作HashMap的一个key——value存储结构的一些行为例如 获取键值对的key。 成员遍历 hash记录存储key的hash值不可改变final修饰 key记录key不可改变final修饰所以hashmap的key是唯一的不能重复。 value记录value可改变。 next当前节点记录下一个节点的地址由此可知该链表是单向链表 2.1.2.2 树节点类
/*** Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn* extends Node) so can be used as extension of either regular or* linked node.*/
static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent; // red-black tree linksTreeNodeK,V left;TreeNodeK,V right;TreeNodeK,V prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}/*** Returns root of tree containing this node.*/final TreeNodeK,V root() {for (TreeNodeK,V r this, p;;) {if ((p r.parent) null)return r;r p;}} 成员变量 parent记录父节点 left 左子树 right右子树 prev前节点 red记录红黑树的状态true是红树反之。 2.1.2.3 继承关系 HashMap的数组既有链表又有红黑树为什么这个神秘的数组是Node类型我觉得到这里就可以讲的通了 链表节点类Node实现了Entry接口而LinkedHashMap的内部类Entry又继承了Node类而TreeNode又继承了Entry所以红黑树的节点类是和链表的Node是有继承关系的可以统一当成一个类型来看待所以NodeK,V类型的数组既可以存放链表又可以存放红黑树。 2.2 方法实现
2.2.1 HashMap的数组初始化 在 JDK11 的 HashMap 中对于数组的初始化采用的是延迟初始化方式。通过 resize 方法 实现初始化处理。resize 方法既实现数组初始化也实现数组扩容处理。 tips啥叫延迟初始化 向数组添加第一个元素的时候才开始对数组做初始化处理。 /*** 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 NodeK,V[] resize() {NodeK,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;}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 thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}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;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;}首先回到刚刚的HashMap的成员变量时成员变量table只是作了一个声明如图 所以table为null所以在执行int oldCap (oldTab null) ? 0 : oldTab.length时oldCap0而此时 threshold也为0所以在执行第一个if的时候两个变量都为0所以直接执行else里面的语句。 newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 即将将初始化数组长度的成员变量16赋值给newCap而下一句则是将下一次扩容的长度给newThr此时为12然后跳过if语句给成员变量threshold重新赋值。再执行 NodeK,V[] newTab (NodeK,V[])new Node[newCap],将newTab赋值给成员变量table然后返回newTab这样一次初始化完成。
2.2.2 计算hash值
在map的存储中我们是根据key的hash值来存放元素的。所以需要对key的hash值进行一系列的运算 1.获取key的hashCode。 2.根据hashCode计算出hash值。但是由于要求要转换成table数组的长度-1的范围内所以还需要一系列的运算。 3.转化算法hash hashcoden-1得到数组中的存放位置。 /*** 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 ttkey/tt, or* ttnull/tt if there was no mapping for ttkey/tt.* (A ttnull/tt return can also indicate that the map* previously associated ttnull/tt with ttkey/tt.)*/
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);
} 这里是计算key的hash值的方法。先将key的hashcode值赋给h然后与h的高16位进行异或运算也就是h的低16位和高16位进行异或运算。 下面来演示一下运算过程 假定key 123456使用计算器计算得到其二进制为 然后进行异或运算相同为0相异为1 计算得到10进制为 到这一步返回123457下面回到putVal()方法 /*** 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, dont 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) {NodeK,V[] tab; NodeK,V p; int n, i;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 {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,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 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;
}putVal方法拿到key的hashCode后和15进行运算(相同为1相异为0) 最终得到存入数组位置为1。 2.2.3 添加元素putK keyV value方法 调用了putVal()方法源码在上面 putVal()主要是计算hash值从而获取元素在数组中的位置前面已经分析过了、如果该位置数组没有元素则将新节点放入我们都知道hashMap对于key相同的值是将其value值覆盖key不变以下则是实现方法 如果p节点与TreeNode节点是同类红黑树则将其挂到红黑树上 前面都不执行的话最后就是挂载到数组所在位置的链表了末尾了 我们再来看看链表——红黑树的方法 treeifyBin(NodeK,V[] tab, int hash) /*** Replaces all linked nodes in bin at index for given hash unless* table is too small, in which case resizes instead.*/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) {TreeNodeK,V hd null, tl null;do {TreeNodeK,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);}}在这里我们看到链表并不是马上做红黑树转换而是先判断数组的长度是否大于MIN_TREEIFY_CAPACITY这个前面有解释小于MIN_TREEIFY_CAPACITY则会调用 resize()方法对数组进行扩容处理。
2.2.4 数组扩容
三. 总结
HashMap的底层是由哈希算法来实现的即数组链表的形式数组长度大于64并且链表的节点个数大于8时会将链表转变为红黑树这样就大大减少了遍历的时间提高效率之所以一个数组能存储两种数据结构就是因为数组的数据类型为链表的节点NodeK,V而红黑树节点TreeNodeK,V跟Node有继承关系的。此外HashMap是采用延时初始化的方式来初始化数组的即用户添加第一个元素的时候才会调用resize() 初始化数组长度16以及预定数组下一次扩容长度12。还有就是hash值的计算以及添加元素等方法的原理等待小伙伴们的探索哦 学习源码知识有助于帮助我们扎实内功,提升程序员的涵养如果您不想直接在idea查看源码也想了解他可以关注博主都给您整理好啦好了文章到这里就结束啦咱们下期见喜欢可以一键三连哦
