网站建议公司,平阳网站建设公司,已有网站开发app客户端,成立广告公司需要什么条件jdk1.7和jdk1.8的HashMap的原理有一点出入我们就分开讲解#xff1a;
1、JDK1.7中的HashMap
JDK1.7中的HashMap是通过数组加链表的方式存储数据。他的底层维护了一个Entry数组#xff0c;通过哈希函数的计算出来哈希值#xff0c;将待填数据根据计算出来的哈希值填入到对应…jdk1.7和jdk1.8的HashMap的原理有一点出入我们就分开讲解
1、JDK1.7中的HashMap
JDK1.7中的HashMap是通过数组加链表的方式存储数据。他的底层维护了一个Entry数组通过哈希函数的计算出来哈希值将待填数据根据计算出来的哈希值填入到对应位置。如果发生哈希冲突就以链表的方式存储在对应位置。形成链式结构。
2、JDK1.8中的HashMap
JDK1.8中的HashMap是数组链表红黑树的方式实现底层维护了一个Node数组当我们哈希冲突比较严重的时候并且数组长度大于64如果不足64优先扩容数组链表长度大于等于8的时候HashMap会将该链表转化为红黑树。值得注意的是如果此时我们减少红黑树中的节点当节点数量小于等于6的时候HashMap才会将红黑树转化位链表。
红黑树的好处
当哈希冲突比较严重的时候也就是链表过长的时候我们查找元素的时间复杂度就变成了On也就是链表查找元素的时间复杂度到那时我们哈希表就体现不出优势了。此时我们将链表转化位红黑树而红黑树的查找时间复杂度是OlogN就优化了HashMap的查找效率/
转化位红黑树的阈值为什么是6和8
因为如果我们频繁添加删除元素使得链表的长度恰好是7左右如果转化阈值是7则会频繁的转化位链表和红黑树从而占用大量的CPU资源设置为6和8就可以很好的避免此类情况。
哈希负载因子
默认的哈希负载因子是0.75也就是如果当前元素/数组大小0.75数组就必须要进行扩容。这个负载因子可以在构造函数中传入进行自定义。
3、HashMap的构造函数 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);}/*** Constructs an empty ttHashMap/tt with the specified initial* capacity and the default load factor (0.75).** param initialCapacity the initial capacity.* throws IllegalArgumentException if the initial capacity is negative.*/public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}/*** Constructs an empty ttHashMap/tt with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}/*** Constructs a new ttHashMap/tt with the same mappings as the* specified ttMap/tt. The ttHashMap/tt is created with* default load factor (0.75) and an initial capacity sufficient to* hold the mappings in the specified ttMap/tt.** param m the map whose mappings are to be placed in this map* throws NullPointerException if the specified map is null*/public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
HashMap有如上四个构造函数参数分别是空initialCapacityinitialCapacity和loadFactorMap? extends K, ? extends V m
initialCapacity指定HashMap的大小。loadFactor哈希负载因子。Map? extends K, ? extends V mMap集合。
值得注意的是如果我们不指定数组大小那么HashMap的默认大小就是16。如果我们指定大小例如33那么会调用如下函数 /*** 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进制值例如传入33返回的就是64.
也就是无论我们指定的数是几HashMap都会以2进制的大小进行初始化。这个跟HashMap的扩容机制有关HashMap是以2倍的方式进行扩容
4、HashMap的put的过程
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// 第四个参数 onlyIfAbsent 如果是 true那么只有在不存在该 key 时才会进行 put 操作
// 第五个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;// 第一次 put 值的时候会触发下面的 resize()类似 java7 的第一次 put 也要初始化数组长度// 第一次 resize 和后续的扩容有些不一样因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// 找到具体的数组下标如果此位置没有值那么直接初始化一下 Node 并放置在这个位置就可以了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;// 如果该节点是代表红黑树的节点调用红黑树的插值方法本文不展开说红黑树else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {// 到这里说明数组该位置上是一个链表for (int binCount 0; ; binCount) {// 插入到链表的最后面(Java7 是插入到链表的最前面)if ((e p.next) null) {p.next newNode(hash, key, value, null);// TREEIFY_THRESHOLD 为 8所以如果新插入的值是链表中的第 8 个// 会触发下面的 treeifyBin也就是将链表转换为红黑树if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果在该链表中找到了相等的 key( 或 equals)if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))// 此时 break那么 e 为链表中[与要插入的新值的 key 相等]的 nodebreak;p e;}}// e!null 说明存在旧值的key与要插入的key相等// 对于我们分析的put操作下面这个 if 其实就是进行 值覆盖然后返回旧值if (e ! null) {V oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;// 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值需要进行扩容if (size threshold)resize();afterNodeInsertion(evict);return null;
}当我们调用Put方法的时候会先检查数组是否为空如果为空则初始化数组。判断key是否为null如果是null则会把对应的value值放到数组下标为0位置。根据key算出来hash值找到对应位置查找如果有该key则覆盖原来的value值如果没有该key新值则把key和value以Node的形式存放到当前位置jdk1.7采用头插法jdk1.8采用尾插法。判断是否需要转化为红黑树也就是链表长度是否到达8.判断是否扩容。
值得注意的是JDK1.7是先扩容再插入1.8是先插入再扩容。
5、HashMap的扩容原理
HashMap是默认以两倍的大小进行扩容。
例如我们的HashMap的数组从16扩容到32如图所示 链表中的节点值会有序的分布在新链表的 i 位置和 i16 的位置。省去了重新计算hash值的过程而且分布的更加均匀。
6、HashMap线程安全吗
HashMap是一个线程不安全的集合如果两个线程同时操作Map扩容就会产生循环链表的现象。
如何得到一个线程安全的Map
使用Collections工具类将线程不安全的Map包装成线程安全的Map使用java.util.concurrent包下的Map如ConcurrentHashMap不建议使用Hashtable虽然Hashtable是线程安全的但是性能较差。
