默认容量为16
/** * the default initial capacity - must be a power of two. * 建议容量为 2的n次幂 */ static final int default_initial_capacity = 1 << 4; // aka 16
默认负载因子
/** * the load factor used when none specified in constructor. */ static final float default_load_factor = 0.75f;
最大容量 2^30
/** * the maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * must be a power of two <= 1<<30. */ static final int maximum_capacity = 1 << 30;
数据bin转换成红黑树的阈值
/** * hash桶的存储方式由list转为tree的转换阈值(插入第9个元素时，list转为tree) * 该阈值必须大于2，并且至少应为8才能与树删除中的假设（收缩时转换回普通箱）相啮合 */ static final int treeify_threshold = 8; /** * 在调整hash桶大小的操作中，取消hash桶的树化存储的计数阈值 * (当一个hash桶中的元素小于该值时，转换成链表存储) * 应该小于treeify_threshold，且最大为6，用于删除操作后的收缩检查 */ static final int untreeify_threshold = 6; /** * hash桶树化存储的table的最小容量。（否则，如果hash桶中的节点过多，将调整table的大小。） * 应至少为 4 * treeify_threshold，以避免调整大小和树化阈值之间的冲突。 * 因为一个比较小，比较满的散列表的性能不如一个比较大，比较空的散列表， * 这种请款先考虑变大，而不是树化存储 */ static final int min_treeify_capacity = 64;
数据table
/** * 第一次使用时初始化，根据需要调整大小(始终为2的n次幂) * 在某些操作中，我们还允许长度为零，以允许使用当前不需要的引导机制。 */ transient node<k,v>[] table; //键值对的数量 transient int size; //结构修改的次数 transient int modcount; //下一个要调整大小的大小值 （容量*负载系数） //如果hash桶数组没有初始化，则该字段持有出事容量，或者是0(表示使用 default_initial_capacity) int threshold; //负载因子 final float loadfactor;
数据节点类型
我要评论static class node<k,v> implements map.entry<k,v> {
final int hash; //用来定位数组索引位置
final k key;
v value;
node<k,v> next; //链表的下一个node
node(int hash, k key, v value, node<k,v> next) { ... }
public final k getkey(){ ... }
public final v getvalue() { ... }
public final string tostring() { ... }
public final int hashcode() { ... }
public final v setvalue(v newvalue) { ... }
public final boolean equals(object o) { ... }
}
static final class treenode<k,v> extends linkedhashmap.entry<k,v> {
treenode<k,v> parent; // 父
treenode<k,v> left; // 左
treenode<k,v> right; // 右
treenode<k,v> prev; // needed to unlink next upon deletion
boolean red; // 判断颜色
treenode(int hash, k key, v val, node<k,v> next) {
super(hash, key, val, next);
}
// 返回根节点
final treenode<k,v> root() {
for (treenode<k,v> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}构造方法
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);
// 获得对应容量的 2的n次幂
this.loadfactor = loadfactor;
this.threshold = tablesizefor(initialcapacity);
}
// 构造新的hashmap 使用map接口的集合: 使用默认loadfactor(0.75) 足以(最小可用)将映射保存在指定map中的初始容量
public hashmap(map<? extends k, ? extends v> m) {
this.loadfactor = default_load_factor;
putmapentries(m, false);
}putall()方法
// 实现 map.putall and map constructor 这俩方法
final void putmapentries(map<? extends k, ? extends v> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判断table是否已经初始化
if (table == null) { // pre-size
// capacity * loadfactor = threshold（最小可用 入参map的size=threshold）
float ft = ((float)s / loadfactor) + 1.0f;
// 得到保存入参map(size)需要的最小 capacity
int t = ((ft < (float)maximum_capacity) ?
(int)ft : maximum_capacity);
//根据容量 刷新阈值
if (t > threshold)
threshold = tablesizefor(t);
}
// 已初始化，并且m元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
for (map.entry<? extends k, ? extends v> e : m.entryset()) {
k key = e.getkey();
v value = e.getvalue();
// constructor-evict:false
// putall-evict:true
putval(hash(key), key, value, false, evict);
}
}
}核心put方法
/**
* 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, don't 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) {
node<k,v>[] tab;
node<k,v> p;
int n, i;
// table未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newnode(hash, key, value, null);
// 桶中已经存在元素
else {
node<k,v> e; k k;
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
else if (p instanceof treenode)
e = ((treenode<k,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 1st
treeifybin(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 key
v oldvalue = e.value;
if (!onlyifabsent || oldvalue == null)
e.value = value;
afternodeaccess(e);
return oldvalue;
}
}
++modcount;
if (++size > threshold)
resize();
afternodeinsertion(evict);
return null;
}扩容方法，消耗很大
/**
* 初始化或加倍数组的大小。如果为空，则根据属性阈值中保持的初始容量目标进行分配。
* 否则，因为我们使用的是2的幂，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的幂偏移。
*
* @return the table
*/
final node<k,v>[] resize() {
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;
}
// 没超过最大值，就扩充为原来的2倍(翻倍后不能大于最大容量)
else if ((newcap = oldcap << 1) < maximum_capacity &&
oldcap >= default_initial_capacity)
newthr = oldthr << 1; // double threshold
}
// 初始化 初始化容量=阈值(2参数构造中赋值的)
else if (oldthr > 0) // initial capacity was placed in threshold
newcap = oldthr;
// 初始化方式--threshold=0（表示使用默认值 default_initial_capacity）
else { // zero initial threshold signifies using defaults
newcap = default_initial_capacity;
newthr = (int)(default_load_factor * default_initial_capacity);
}
// 计算新的resize上限
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"})
node<k,v>[] newtab = (node<k,v>[])new node[newcap];
table = newtab;
if (oldtab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldcap; ++j) {
node<k,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)
((treenode<k,v>)e).split(this, newtab, j, oldcap);
else { // preserve order
// 链表优化重hash的代码块
node<k,v> lohead = null, lotail = null;
node<k,v> hihead = null, hitail = null;
node<k,v> next;
do {
next = e.next;
// 原index
if ((e.hash & oldcap) == 0) {
if (lotail == null)
lohead = e;
else
lotail.next = e;
lotail = e;
}
// 原index + oldcap
else {
if (hitail == null)
hihead = e;
else
hitail.next = e;
hitail = e;
}
} while ((e = next) != null);
// 原index放到bucket里
if (lotail != null) {
lotail.next = null;
newtab[j] = lohead;
}
// 原index + oldcap放到bucket里
if (hitail != null) {
hitail.next = null;
newtab[j + oldcap] = hihead;
}
}
}
}
}
return newtab;
}
如对本文有疑问， 点击进行留言回复！！
android用Popup弹出窗(PopupWindow的使用方式)
ionic3 打包 Could not get resource ‘https://jcenter.bintray.com/com/google/zxing/core/3.2.1/core-3.2.1
NullPointerException: Attempt to invoke virtual method ‘android.content.res.XmlResourceParser androi
网友评论