java基础 |
您所在的位置：网站首页 › hashmap怎么排序 › java基础 |
java基础
|
一、初始化
1.1 默认初始化
//默认初始化仅指定加载因子，首次put元素时，会使用resize()开辟16（2的4次幂）个长度的空间
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
1.2 指定容量初始化
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 返回最小大于等于cap的2的n次幂
* 例如：tableSizeFor(19)返回32
*/
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;
}
1.3 HashMap为什么让容量一定是2的幂次方
（1）偶数使数据均匀分布（节约空间、减少位置冲突）：桶下标计算公式即是hash&(capacity-1),若允许capacity为奇数， 那经过capacity-1之后就变成了偶数，那经过&运算后的值也是偶数，这样任何Hash值只会散列到数组的偶数下标位置上，浪费空间并且增加冲突的可能性。如果capacity为偶数，那么经过capacity-1之后就变成奇数，再经过&运算后的值，可能是奇数也可能是偶数，这样可以保证散列比较均匀。 （2）运算速度更快：见2.3-（2） 二、定位桶位置增加、删除、查找键值对，定位到哈希桶数组的位置都是关键的第一步。 HashMap处理逻辑为：先是通过扰动函数hash(Object key)处理key的hashCode而得到其hash 值，然后通过 hash&(capacity-1)判断当前元素存放的位置。 2.1 hash(Object key) static final int hash(Object key) { int h; //^ (h >>> 16)为扰动函数，作用见见2.3分析-（3） return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 2.2 桶下标计算 hash&(capacity-1) 2.3 分析（1）key.hashCode()函数调用的是key键值类型自带的哈希函数public native int hashCode()返回的int类型。如果直接拿散列值做数组下标，那么索引范围就是‑2147483648到2147483648，前后加起来大概40亿的映射空间，但桶数组默认的初始容量最大才16，这就说明hashCode()返回的散列值是不能直接用来访问，需要映射到桶的容量空间（%、&）。 （2）桶下标计算公式是hash&(capacity-1)。之所以不使用hash % capacity方式取模，是因为HashMap中规定了哈希表长度为2 的幂，在这种情况下，位与运算更快， resize() 扩容时也可以更高效地重新计算桶下标【hash&(capacity-1)计算方式，可以使新老桶位置之间存在一定关系】。 （3）扰动函数作用 （a）桶下标计算如果直接使用key.hashCode()&(capacity-1)，因初始时capacity值较小，所以总会截取最后几位，碰撞会比较严重。比如capacity=16，capacity-1=15 0000 0000 0000 0000 0000 0000 0000 1111 & 1111 1111 1111 1111 1111 0000 1110 1010 -------------------------------------------- 0000 0000 0000 0000 0000 0000 0000 1010（b）这时候扰动函数的作用就体现出来了：右位移16位，正好是32的一半，自己的高半区与低半区做异或，就是为了混合原始哈希码的高位与低位，以此来加大低位随机性。而混合后的低位参杂了高位部分特征，高位信息也参入了寻址计算（进行扰动）。
三、扩容 3.1 桶下标计算公式是hash&(capacity-1)，扩容为2倍后，节点在新旧table中的位置存在一定联系: (1)要么下标相同; (2)要么相差一个oldCap(原table的大小) 例如，有2个元素k1、k2,对应的hash值分别为0000 0101、0001 0101, (1)原来table大小为16，k1、k2对应的位置都为5: (a) k1 0000 0101 & 0000 1111 -------------- 0000 0101 (b) k2 0001 0101 & 0000 1111 -------------- 0000 0101 (2)table大小扩容为32后: (a) k1对应位置为5 0000 0101 & 0001 1111 -------------- 0000 0101 (b) k2对应位置为21=5+16 0001 0101 & 0001 1111 -------------- 0001 0101 3.2 扩容后桶位置的快速计算因为扩容后计算存储位置就是hash&(capacity-1)），但是并不需要再如此计算一次位置，因为有快速的替代算法，即：只需要判断左边新增的那一位是否为1，便可判断此节点是留在原地lo，还是移动去高位hi【(e.hash & oldCap) == 0】。 例如，有2个元素k1、k2,对应的hash值分别为0000 0101、0001 0101, (1)原来table大小为16，对应的位置都为5: (a) k1 0000 0101 & 0000 1111 -------------- 0000 0101 (b) k2 0001 0101 & 0000 1111 -------------- 0000 0101 (2)table大小扩容为32后位置,看hash值与16(原oldCap值)位与是否为0，可以快速定位位置 (a) k1 0000 0101 & 0001 0000 -------------- 0000 0000 (b) k2 0001 0101 & 0001 0000 -------------- 0001 0000 3.3 resize源码 final HashMap.Node[] resize() { HashMap.Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; ... //newCap扩为原来的2倍：newCap = oldCap |
【本文地址】
今日新闻 |
推荐新闻 |