唐山网站建设|唐山网站制作|公司建站666起|唐山红城网络,有哪些做统计销量的网站,设计个网站多少钱,国家电网交流建设分公司网站HashMap作为我们最常用的数据类型#xff0c;当然有必要了解一下他内部是实现细节。相比于 JDK7 在JDK8 中引入了红黑树以及hash计算等方面的优化#xff0c;使得 JDK8 中的HashMap效率要高于以往的所有版本#xff0c;本文会详细介绍相关的优化#xff0c;但是主要还是写 …HashMap作为我们最常用的数据类型当然有必要了解一下他内部是实现细节。相比于 JDK7 在JDK8 中引入了红黑树以及hash计算等方面的优化使得 JDK8 中的HashMap效率要高于以往的所有版本本文会详细介绍相关的优化但是主要还是写 JDK8 的源码。 一、整体结构 1. 类定义 public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable {} 可以看到HashMap是完全基于Map接口实现的其中AbstractMap是Map接口的骨架实现提供了Map接口的最小实现。HashMap看名字也能猜到他是基于哈希表实现的数组链表红黑树 2. 构造函数和成员变量 public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map? extends K, ? extends V m)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);
} HashMap一共有四个构造函数其主要作用就是初始化loadFactor和threshold两个参数 threshold扩容的阈值当放入的键值对大于这个阈值的时候就会发生扩容loadFactor负载系数用于控制阈值的大小即threshold table.length * loadFactor默认情况下负载系数等于0.75当它值越大时哈希桶空余的位置越少空间利用率越高同时哈希冲突也就越严重效率也就越低相反它值越小时空间利用率越低效率越高而0.75是对于空间和效率的一个平衡通常情况下不建议修改但是对于上面构造函数当中this.threshold tableSizeFor(initialCapacity);这里的阈值并没有乘以负载系数是因为在构造函数当中哈希桶table[]还没有初始化在往里put数据的时候才会初始化而tableSizeFor是为了得到大于等于initialCapacity的最小的2的幂 transient NodeK,V[] table; // 哈希桶
transient SetMap.EntryK,V entrySet; // 映射关系Set视图
transient int size; // 键值对的数量
transient int modCount; // 结构修改次数用于实现fail-fast机制 哈希桶的结构如下 static class NodeK,V implements Map.EntryK,V {final int hash; // 用于寻址避免重复计算final K key;V value;NodeK,V next;...public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}
} 其中NodeK,V next还有一个TreeNode子类用于实现红黑树需要注意的是这里的hashCode()所计算的hash值只用于在遍历的时候获取hash值并非寻址所用hash 二、Hash表 既然是Hash表那么最重要的肯定是寻址了在HashMap中采用的是除留余数法即table[hash % length]但是在现代CPU中求余是最慢的操作所以人们想到一种巧妙的方法来优化它即length为2的指数幂时hash % length hash (length-1)所以在构造函数中需要使用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;
} 首先这里要明确 2的幂的二进制是1后面全是0有效位都是1的二进制加1就可以得到2的幂以33为例如图 因为int是4个字节32位所以最多只需要将高位的16位与低位的16位做或运算就可以得到2的幂而int n cap - 1;是为了避免cap本身就是2的幂的情况这个算是真是厉害看了很久才看明白实在汗颜。 计算 hash static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 这里重新计算hash是因为在hash (length-1)计算下标的时候实际只有hash的低位参与的运算容易产生hash冲突所以用异或是高位的16位也参与运算以减小hash冲突要理解这里首先要明白 操作之后只会保留下都是1的有效位length-12的n次方-1实际上就是n和1 操作之后hash所保留下来的也只有低位的n个有效位所以实际只有hash的低位参与了运算具体如图所示 三、重要方法讲解 对于Map而言最重要的当然是Get和Put等操作了所以下面将介绍与之相关的操作 1. put方法 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, 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;// 如果没有初始化哈希桶就使用resize初始化if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// 如果hash对应的哈希槽是空的就直接放入if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;// 如果已经存在key就替换旧值if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;// 如果已经是树节点就用putTreeVal遍历树赋值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);// 如果链表长度大于8则转换为红黑树if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 找到key对应的节点则跳出遍历if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}// e是最后指向的节点如果不为空说明已经存在key则替换旧的valueif (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}// 新增节点时结构改变modCount加1modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;
} 具体过程如图所示 2. resize方法 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) {// 如果hash桶已经完成初始化并且已达最大容量则直接返回if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}// 如果扩大2倍没有超过最大容量则扩大两倍else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}// 如果threshold已经初始化则初始化容量为thresholdelse if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;// 如果threshold和哈希桶都没有初始化则使用默认值else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 重新计算thresholdif (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;}// 节点重新放置后位置oldCapelse {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
} 上面的扩容过程需要注意的是因为哈希桶长度总是2的幂所以在扩大两倍之后原来的节点只可能在原位置或者原位置oldCap具体判断是通过(e.hash oldCap) 0实现的 之前将了 操作只保留了都是1的有效位oldCap 是2的n次方实际也就是在n1的位置为1其余地方为0因为扩容是扩大2倍实际上也就是在hash上取了 n1位那么就只需要判断多取的第n1位是否为0如图所示 3. 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) {if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;if ((e first.next) ! null) {if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
} 相较于其他方法get方法就要简单很多了只是用hash取到对应的hash槽在依次遍历即可。 4. clone方法 public Object clone() {HashMapK,V result;try {result (HashMapK,V)super.clone();} catch (CloneNotSupportedException e) {// this shouldnt happen, since we are Cloneablethrow new InternalError(e);}result.reinitialize();result.putMapEntries(this, false);return result;
} 对于clone方法这里有一个需要注意的地方result.putMapEntries(this, false)这里在put节点的时候是用的this所以这只是浅复制会影响原map所以在使用的时候需要注意一下 至于其他方法还有很多但大致思路都是一致的大家可以在看一下源码。 四、HashMap不同版本对比 1. hash均匀的时候使用get Number Of RecordsJava 5Java 6Java 7Java 810,0004 ms3 ms4 ms2 ms100,0007 ms6 ms8 ms4 ms1,000,00099 ms15 ms14 ms13 ms2. hash不均匀的时候使用get Number Of RecordsJava 5Java 6Java 7Java 810,000197 ms154 ms132 ms15 ms100,00030346 ms18967 ms19131 ms177 ms1,000,0003716886 ms2518356 ms2902987 ms1226 ms10,000,000OOMOOMOOM5775 ms3. hash均匀的时候使用put Number Of RecordsJava 5Java 6Java 7Java 810,00017 ms12 ms13 ms10 ms100,00045 ms31 ms34 ms46 ms1,000,000384 ms72 ms66 ms82 ms10,000,0004731 ms944 ms1024 ms99 ms4. hash不均匀的时候使用put Number Of RecordsJava 5Java 6Java 7Java 810,000211 ms153 ms162 ms10 ms100,00029759 ms17981 ms17653 ms93 ms1,000,0003527633 ms2509506 ms2902987 ms333 ms10,000,000OOMOOMOOM3970 ms从以上对比可以看到 JDK8 的 HashMap 无论 hash 是否均匀效率都要好得多这里面hash算法的改良功不可没并且因为红黑树的引入使得它在hash不均匀甚至在所有key的hash都相同的情况任然表现良好 另外这里我数据我是摘至 Performance Improvement for HashMap in Java 8里面还有更详细的图表大家有兴趣可以看一下 总结 扩容需要重排所有节点特别损耗性能所以估算map大小并给定一个合理的负载系数就显得尤为重要了。HashMap 是线程不安全的。虽然 JDK8 中引入了红黑树将极端hash的情况影响降到了最小但是从上面的对比还是可以看到一个好的hash对性能的影响仍然十分重大所以写一个好的hashCode()也非常重要。参考 https://tech.meituan.com/java_hashmap.htmlhttps://blog.csdn.net/fan2012huan/article/details/51097331https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 转载于:https://www.cnblogs.com/sanzao/p/10245212.html
