文章目录
- 1. hashmap 存储结构
-
-
- 1.1 hashmap底层结构
- 1.2 hashmap 为什么采用数组 链表
-
-
- reference: 解决hash冲突的四种方法：
-
- 1.2 hashmap 数组结构可否被替代
- 1.3 hashmap 为何不直接使用红黑树
- 1.4 hashmap 红黑树什么时候退化为链表
-
- 2. hashmap 存取过程
-
-
- 2.1 hashmap put()方法
- 2.2 hashmap get()方法
-
- 3. hashmap 容量相关
-
-
- 3.1 hashmap 初始化容量
- 3.2 hashmap 扩容为什么是2的次幂
- 3.3 hashmap 扩容机制
-
- 4. hashmap 使用指南
-
-
- 4.1 使用不可变类作为hashmap的key
- 4.2 实现自定义类作为hashmap的key
-
- 4.2.1 重写 hashcode 和 equals 方法
- 4.2.2 如何设计一个不变类
-
1.1 hashmap底层结构
jdk 1.8 的 hashmap 底层数据结构与 jdk1.7 时大致相同，主要为 数组 链表。它采用entry数组来存储key-value对，每一个键值对组成了一个entry实体，entry类实际上是一个单向的链表结构，它具有next指针，可以连接下一个entry实体。但在1.8 版本中如果链表元素数量达到 8 ， 就会尝试进行树化操作（如果数组长度小于 64， 则进行扩容操作，而不是树化操作），将链表转化为 红黑树结构。故 hashmap 数据结构可作如下总结：
- jdk 1.7： 数组 链表
- jdk 1.8： 数组 链表 红黑树
static final int min_treeify_capacity = 64;
final void treeifybin(node[] tab, int hash) {
int n, index; node e;
if (tab == null || (n = tab.length) < min_treeify_capacity)
resize(); // 如果数组长度小于 64， 则进行扩容操作，而不是树化操作
else if ((e = tab[index = (n - 1) & hash]) != null) {
treenode hd = null, tl = null;
do {
treenode p = replacementtreenode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
1.2 hashmap 为什么采用数组 链表
- 数组结构简单，利用元素 key的hash值对数组长度取模可以快速定位到数组下标 index，效率极高
- 链表是用来解决hash冲突问题，当出现 hashcode 值一样的情形，就在数组相应下标位置形成一条链表。这是解决hash冲突的链地址法
reference: 解决hash冲突的四种方法：
- 链地址法
基本思想是将所有哈希地址为 i 的元素构成一个单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在链表中进行。链地址法适用于经常进行插入和删除情况。 - 开放定址法
也称再散列法，基本思想是当关键字key的哈希地址p=h（key）出现冲突时，以p为基础产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。 - 再哈希法
同时构造多个不同的哈希函数，当哈希地址hi=rh1（key）发生冲突时，再计算hi=rh2（key），直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。 - 公共溢出区域法
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
1.2 hashmap 数组结构可否被替代
能否用linkedlist 代替
- 答案是可以，但是用数组效率最高。 在hashmap中定位数组下标利用元素的key的哈希值对数组长度取模就可以，显然数组的查找效率比linkedlist高。
arraylist底层是数组查找也快，能否用arraylist
- 采用基本数组结构扩容机制可以自己定义，hashmap中数组扩容刚好是2的次幂，在做取模运算的效率高。而arraylist的扩容机制是1.5倍扩容，默认容量为10，不利于高效定位。
private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; int newcapacity = oldcapacity (oldcapacity >> 1); // 1.5 倍扩容，默认为10 ...... }
1.3 hashmap 为何不直接使用红黑树
- 当元素小于8个时，做查询操作链表结构已经能保证查询性能。
- 当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，这些都是性能损耗。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑是浪费性能。
1.4 hashmap 红黑树什么时候退化为链表
从源码看，节点数量为6的时候退转为链表,中间有个差值7可以防止链表和树之间频繁的转换。如果设计成链表个数超过8则链表转换成树结构，小于8则树结构转换成链表，如果一个hashmap不停插入删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率很低。
static final int treeify_threshold = 8;
static final int untreeify_threshold = 6;
final void split(hashmap map, node[] tab, int index, int bit) {
......
if (lohead != null) {
if (lc <= untreeify_threshold)
tab[index] = lohead.untreeify(map); // 解除树化
......
}
2.1 hashmap put()方法
存储元素的过程如下：
- 对key 做hash() 运算，获取其hashcode 值, 可看到有对 key==null 返回 0 的处理，这就是hashmap允许 null 键的原因。 另外
hash()中 将 hashcode 与 hashcode 无符号右移16位的值进行异或处理，是出于减少哈希冲突的目的，因为这个操作把原 hashcode 中没有使用到的高位数据也利用起来参与到运算中了。
hash函数是指把一个大范围映射到一个小范围，目的是节省空间，使得数据容易保存。比较出名的有murmurhash、md4、md5等等。
static final int hash(object key) {
int h;
// 此处 h与其低16位 异或 操作，目的是减少index定位时的 hash碰撞
return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}
-
懒加载策略，如果当前 entry[] 数组尚未初始化，则调用 resize（）方法初始化。
-
使用 hash（）运算后的值与【数组长度-1】与运算 后定位到数组 index，如果该位置上没有元素则插入。
-
如果碰撞了，【1】首先通过 equals（）比较 key，如相同则使用新的 value 覆盖旧 value，从此可知hashmap 只允许一个key为null的键值对；【2】不符合前一条则首先判断碰撞的元素是否是 树节点，即该位置链表是否已经转化成红黑树，如是则将新元素转化为 树节点插入；【3】不符合前两条，遍历该数组位置链表，判断链表长度是否大于8，大于8则将链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作，遍历过程中若发现key已经存在直接覆盖value即可。
-
插入成功后，判断数组实际存在的键值对数量size是否超过了最大容量threshold，如果超过则进行扩容。
public v put(k key, v value) {
return putval(hash(key), key, value, false, true); //
}
final v putval(int hash, k key, v value, boolean onlyifabsent,
boolean evict) {
node[] tab; node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newnode(hash, key, value, null);
else {
node e; k k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof treenode)
e = ((treenode)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.2 hashmap get()方法
获取value的过程也很简单：
-
对key 做hash() 运算,获取用于定位数组下标的值。
-
使用 hash（）运算后的值与【数组长度-1】与运算 后定位到数组下标index，取该位置上第一个节点 first，如其直接命中则直接返回。
-
如果有冲突，则通过key.equals(k)去查找对应的entry：若为树，则在树中通过key.equals(k)查找，o(logn)；如果是链表，则在链表中通过key.equals(k)查找，o(n)。
public v get(object key) {
node e;
return (e = getnode(hash(key), key)) == null ? null : e.value;
}
final node getnode(int hash, object key) {
node[] tab; node 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 ((treenode)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;
}
3.1 hashmap 初始化容量
hashmap默认容量为 16，最大容量为 1<<30 。扩容负载因子为 0.75，也就是默认容量下数组中实际存储的元素数量达到 16 * 0.75 = 12，就会触发扩容。
static final int default_initial_capacity = 1 << 4; // aka 16
static final int maximum_capacity = 1 << 30;
static final float default_load_factor = 0.75f;
一般建议使用 hashmap 的时候指定初始容量大小，因为随着元素的不断增加，如果实际容量与初始容量相差太大，hashmap会发生多次扩容，而其扩容机制决定了每次扩容都需要重建hash表，非常影响性能。
另外即便通过 hashmap(int initialcapacity) 设置初始容量的时候，hashmap也不一定会直接采用传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。 从以下代码看，经过无符号右移和按位或运算, hashmap的容量最终会被设置成 大于传入参数的最小的2的次幂（7–>8, 10–>16）。
static final int tablesizefor(int cap) {
int n = cap - 1; // 参数值 -1 是为了处理传入参数值恰好是 2 的次幂的情况
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;
}
3.2 hashmap 扩容为什么是2的次幂
hashmap为了存取高效就要尽量减少碰撞，也就是尽量把数据分配均匀，每个index下标上的链表(也可能是红黑树)长度需要大致相同, 这个算法实际就是取模，hash%length。
但是取模运算不如位移运算快。因此源码中优化为 hash()&(length-1),也就是hash%length 等价于 hash()&(length-1).
public v get(object key) {
node e;
return (e = getnode(hash(key), key)) == null ? null : e.value;
}
final node getnode(int hash, object key) {
node[] tab; node first, e; int n; k k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 注意，此处即为取模定位 index
......
}
之所以取数组长度为 2 的n 次方,是因为2的n次方用二进制表示实际就是1后面n个0，而2的n次方-1，实际就是n个1。
- 例如长度为8时候，3&(8-1)–>(11 & 111)=3, 2&(8-1)–>(10 & 111)=2 ，下标不同，不碰撞。
- 而长度为5的时候，3&(5-1)=0, 2&(5-1)=0，都在0上，出现碰撞了。
所以，保证容积是2的n次方，是为了保证在做 hash&(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算, 尽量减少哈希冲突.
3.3 hashmap 扩容机制
hashmap 扩容为原来2倍，所以链表中节点的位置要么是在数组原位置，要么是在数组原位置再移动2次幂的数组位置，且链表元素的顺序不变。
- jdk1.7中 hashmap旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置。1.8的优化解决了 1.7 版本 hashmap多线程扩容出现链表中两个节点 next 指针互相指向对方的 死循环（hashmap infinite loop）问题。
以下代码中已经添加了注释，jdk1.8中hashmap 不需要像jdk1.7的实现那样重新计算hash值，而是复用原 hash 值，将其与原容量进行与操作，进而确定其数组下标是否需要改变。
- 例如原容量 oldcap = 16，二进制表示为： 00001 0000
则 key1=0001 1001, key2 = 0000 1001, 扩容前两个 key&(oldcap-1) 都在下标 9 位置
扩容时 key1&oldcap = 0001 0000=16 下标变化, key2&oldcap=0 下标不变
final node[] resize() {
node[] 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
}
......
threshold = newthr;
@suppresswarnings({
"rawtypes"，"unchecked"})
node[] newtab = (node[])new node[newcap];
table = newtab;
if (oldtab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldcap; j) {
node e;
if ((e = oldtab[j]) != null) {
......
else {
// 重点，重新处理链表节点位置代码块
node lohead = null, lotail = null;
node hihead = null, hitail = null;
node next;
do {
next = e.next;
// 复用原 hash 值与 原容量与操作，若原容量为oldcap = 16 = 00001 0000
// 则 key1=0001 1001, key2 = 0000 1001, 扩容前两个[key&(oldcap-1)]都
// 在下标 9 位置
// 扩容时 key1&oldcap = 0001 0000=16 下标变化, key2&oldcap=0 下标不变
if ((e.hash & oldcap) == 0) {
if (lotail == null)
lohead = e;
else
lotail.next = e;
lotail = e;
}
// 其他则需移动位置
else {
if (hitail == null)
hihead = e;
else
hitail.next = e;
hitail = e;
}
} while ((e = next) != null);
// 放到new bucket里 位置与原索引相同
if (lotail != null) {
lotail.next = null;
newtab[j] = lohead;
}
// 放到new bucket里，下标位置为 原索引 oldcap
if (hitail != null) {
hitail.next = null;
newtab[j oldcap] = hihead;
}
}
}
}
}
return newtab;
}
4.1 使用不可变类作为hashmap的key
一般用integer、string这种不可变类当hashmap当key，最常用string。
- 因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为map中的键，字符串的处理速度要快过其它的键对象。
- hashmap 存取值的时候要用到 equals()和 hashcode()方法，键对象正确地重写这两个方法是非常重要的，通常不可变类已经很规范的覆写了hashcode()以及equals()方法。
使用可变类（如list）作为 hashmap 的key 的问题
- 例如把list 作为键，那么当这个 list 对象添加删除元素的时候 hashcode可能发生改变， 这样可能会导致其在hashmap中数组 index下标定位不准，也就无法取出存储的value。
4.2 实现自定义类作为hashmap的key
主要涉及两个关键点：
- 重写 hashcode 和 equals 方法
- 设计一个不变类
4.2.1 重写 hashcode 和 equals 方法
需要遵守以下四个原则：
-
两个对象相等，hashcode一定相等
-
两个对象不等，hashcode不一定不等
-
hashcode相等，两个对象不一定相等
-
hashcode不等，两个对象一定不等
4.2.2 如何设计一个不变类
-
类添加final修饰符，保证类不被继承
如果类可被继承就会破坏类的不可变性机制，只要子类覆盖父类的方法（如equals 和 hashcode）并且子类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。 -
所有成员变量必须私有，并且加上final修饰
通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为对象成员变量有可能在外部改变其值，所以第5点弥补这个不足。 -
不提供改变成员变量的方法，包括setter
避免通过其他接口改变成员变量的值，破坏不可变特性。 -
在getter方法中，不要直接返回对象本身，而是克隆对象并返回对象的拷贝
这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。 -
通过构造器初始化所有成员，进行深拷贝(deep copy)
如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改达到改变内部变量的效果。例如：
public final class table {
private final int[] myarray;
public table (int[] array) {
this.myarray = array; // myarray和array指向同一块内存地址
//修改传入的array对象的值可改变myarray内部的值
}
}
为了保证内部的值不被修改，可采用深度copy来创建一个新内存保存传入的值。正确做法：
public final class table {
private final int[] myarray;
public table (int[] array) {
this.myarray = array.clone();
}
}