jdk1.7:数组 + 链表
jdk1.8:数组 + 链表 + 红黑树
(1).HashMap的无参构造方法采用延迟加载的方式来进行数组初始化的,默认长度是16,扩容因子为12
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** * Constructs an empty <tt>HashMap</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
}
这里并没有初始化数组,而是在put()方法的时候来完成数组的初始化的
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
transient Node<K,V>[] table;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义一个数组,Node<K,V>[] tab;
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断当前数组是null,或者长度等于0
if ((tab = table) == null || (n = tab.length) == 0){
//resize()就是初始化方法
tab = resize()
n=tab.length;
}
}
在这一行,Node<K,V>[] tab开始初始化。resize()中的部分代码
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
newCap = DEFAULT_INITIAL_CAPACITY;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
(2).初始化方法:resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //transient Node<K,V>[] table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap:0
int oldThr = threshold; //oldThr:0
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 threshold
newCap = oldThr;
else { // zero initial threshold signifies(表示,意思是) using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //newCap:16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //newThr:12
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //threshold:12
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //初始化一个容量为16的Node<K,V>的数组
table = newTab;
if (oldTab != null) {
......
}
return newTab;
}
(3).threshold
threshold:扩容因子
Node<K,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
}
总结:
//扩容因子第一次
threshold = (newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY));//0.75 * 16 = 12
//数组容量第一次
newCap = DEFAULT_INITIAL_CAPACITY;//16
//扩容因子第二次
threshold = (newThr = oldThr << 1); //12 * 2 = 24
//数组容量第一次
newCap = oldCap << 1; //16 * 2 = 32
作用:数组是否扩容是通过threshold扩容因子来进行判断,但是是按照数组容量的两倍来进行扩容的!
this.threshold = tableSizeFor(initialCapacity); //扩容因子 = 扩容后的容量
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
有参构造器
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity); //非法数据异常
//如果初始化容量大于最大容量,则改变为最大容量2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果装载因子小于等于0 或 装载因子为NaN ,则报错
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//通过这个方法可以实现提前设置一个较为稳定的容量,从而避免频繁扩容导致的性能下降
this.threshold = tableSizeFor(initialCapacity);
}
–>关于Float.isNaN(flaoat v)
public static boolean isNaN(float v) {
return (v != v);
}
/* 每个NaN都会分配一个单独的地址来放, 所以导致NaN==NaN的时候比较内存地址一定会返回false,也就是当且仅当v是NaN时NaN!=NaN一定是true 虽然Float.NaN==Float.NaN 结果为false,但Float.NaN与Float.NaN的equal()结果相等的 虽然0.0f==-0.0f结果为true,但0.0f 与 -0.0f的equals()结果是不等的;*/
扩容方法:tablesizefor()
当初始化HashMap时,如果指定了初始化容量initialCapacity,由于哈希桶的数量必须时2的n次幂,因此要把initialCapacity转化为
比它大的最小2的n次幂。
如传入的initialCapacity=3,数组实际容量为4;传入的initialCapacity=5,数组实际容量为8;传入的initialCapacity=15,数组实际容量为16;
/** * 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;
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_44928370/article/details/120207276
内容来源于网络,如有侵权,请联系作者删除!