我们知道,HashMap的容量要求为2的指数(16、32、256等),默认为16。此外,HashMap也支持在构造器中指定初始容量initialCapacity,并会将容量设置为大于等于initialCapacity的最小的2的指数。HashMap会基于这个容量创建table数组:
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
那么,为什么HashMap一定要将容量设置为2的指数呢?原因如下:
对于一个整数n,如果它为2的指数,那么对于任意正整数h,都有 h % n = h & (n - 1)
写个程序验证一下:
public class TestHash {
public static void main(String[] args) {
//创建一个2的指数n
int n = (int) Math.pow(2, ThreadLocalRandom.current().nextInt(1, 10));
//创建一个随机正整数h
int h = ThreadLocalRandom.current().nextInt(1, Integer.MAX_VALUE);
//判断结果
System.err.println("取模运算与位运算的结果是否相等: " + ((h % n) == (h & (n - 1))));
}
}
可以看到,结果始终是相等的。
基于这个性质,就可以使用位运算代替取模运算,在很大程度上提升性能。
HashMap在定位table中的桶时,就利用了table长度为2的指数这个性质,通过位运算迅速地找到key所在的桶,代码如下:
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
//通过(n - 1) & hash找到桶,代替(hash % n)
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)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;
}
可以看到,上面代码中,首先计算出key的哈希值hash,然后通过tab[(n - 1) & hash]迅速定位到了key所在的桶,十分高效。
注:该性质对ConcurrentHashMap同样适用。
在JDK底层代码中,很多地方都用到了位运算,主要原因就是位运算效率很高。那么位运算还有什么其他应用呢?
下面举了一个小例子——权限处理:将每种权限定义成一个二进制的数,那么通过简单、高效的位运算就可以进行权限的赋予、禁用和判断,代码如下:
/**
* @Author zhangshenao
* @Date 2019-09-03
* @Description 使用位运算进行权限操作
*/
public class Permission {
//权限定义
public static final int QUERY = 1 << 0;
public static final int MODIFY = 1 << 1;
public static final int DELETE = 1 << 2;
//当前权限状态
private int state;
public static Permission valueOf(int state) {
Permission p = new Permission();
p.state = state;
return p;
}
//判断是否有权限,采用位运算
public boolean isEnableQuery() {
return (state & QUERY) == QUERY;
}
public boolean isEnableModify() {
return (state & MODIFY) == MODIFY;
}
public boolean isEnableDelete() {
return (state & DELETE) == DELETE;
}
//增加权限,使用位运算
public void enable(int permission) {
state = state | permission;
}
//禁用权限,使用位运算
public void disable(int permission) {
state = state & ~permission;
}
public static void main(String[] args) {
Permission permission = valueOf(0);
permission.enable(QUERY);
permission.enable(MODIFY);
System.err.println("isEnableQuery: " + permission.isEnableQuery());
System.err.println("isEnableModify: " + permission.isEnableModify());
System.err.println("isEnableDelete: " + permission.isEnableDelete());
}
}
其实类似的处理在JDK代码中也有很多体现,如Class类,使用一些二进制的值表示一个Class的相关属性,如是否是注解、是否是枚举等:
public final class Class<T> implements java.io.Serializable,
GenericDeclaration,
Type,
AnnotatedElement {
private static final int ANNOTATION= 0x00002000;
private static final int ENUM = 0x00004000;
private static final int SYNTHETIC = 0x00001000;
}
这样就可以通过位运算很快地判断出一个Class的相关属性:
public boolean isAnnotation() {
return (getModifiers() & ANNOTATION) != 0;
}