在hash中查找key的时候,经常会发现用&取代%,先看两段代码吧,
JDK6中的HashMap中的indexFor方法:
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
Redis2.4中的代码段:
n.size = realsize;
n.sizemask = realsize-1;
//此处略去xxx行
while(de) {
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
大家可以看到a%b取模的形式都被替换成了a&(b-1) ,当hashtable的长度是2的幂的情况下(疏忽,一开始没写),这两者是等价的,那为什么要用后者呢?
另一方面,为什么hashtable的长度最好要是2的n次方呢,这个不在本次讨论范围之列,原因简单说一下就是1、分布更均匀 2、碰撞几率更小 详情自己思考,JDK中的HashMap就会在初始化时,保证这一点:
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
redis中也有类似的保证:
/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size)
return i;
i *= 2;
}
}
言归正传,大家都知道位运算的效率最高,这也是&取代%的原因,来看个程序:
int main(int argc, char* argv[])
{
int a = 0x111;
int b = 0x222;
int c = 0;
int d = 0;
c = a & (b-1);
d = a % b;
return 0;
}
看反汇编的结果:
13: c = a & (b-1);
00401044 mov eax,dword ptr [ebp-8]
00401047 sub eax,1
0040104A mov ecx,dword ptr [ebp-4]
0040104D and ecx,eax
0040104F mov dword ptr [ebp-0Ch],ecx
14: d = a % b;
00401052 mov eax,dword ptr [ebp-4]
00401055 cdq
00401056 idiv eax,dword ptr [ebp-8]
00401059 mov dword ptr [ebp-10h],edx
可以看到,&操作用了:3mov+1and+1sub %操作用了:2mov+1cdp+1idiv
我们可以查阅Coding_ASM_-_Intel_Instruction_Set_Codes_and_Cycles资料,发现前者只需5个CPU周期,而后者至少需要26个CPU周期(注意,是最少!!!) 效率显而易见。所以以后自己在写的时候,也可以使用前者的写法。
分享到:
相关推荐
斐波那契数列的几种时间复杂度优化 以下代码因不同算法而时间复杂度不同个人归类为不同版本,总结如下。 1.尽量不要用递归,纵使好看,但...4.用位运算来代替乘法、除法以及取模。 5.有数学公式用数学公式@.@....
本程序主要是BloomFilter算法的简化实现 因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。 算法原理: 其首先申请一块大内存,并把内存中...
&= 运算符 对变量和表达式执行按位“与”运算,结果赋给变量。 && 运算符 对两个表达式执行逻辑连接运算。 * 运算符 将两个表达式的值相乘。 *= 运算符 将变量与表达式的值相乘,结果赋给变量。 + 运算符 将两个...
Stein 的算法用算术移位、比较和减法代替除法。Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。欧几里德算法是计算两个数...
欢迎使用 JScript 语言参考 这些方便实用的信息将帮助您了解 JScript 的各个部分。 在“字母顺序的关键字列表”中,可以找到按字母顺序列出的所有 JScript 语言的主题。如果只需要查看某个主题(例如对象),则有对...
&= 运算符 对变量和表达式执行按位“与”运算,结果赋给变量。 && 运算符 对两个表达式执行逻辑连接运算。 * 运算符 将两个表达式的值相乘。 *= 运算符 将变量与表达式的值相乘,结果赋给变量。 + 运算符 将两个...
5.9 什么时候应该用宏代替函数? 5.10 使用宏更好,还是使用函数更好? 5.11 在程序中加入注释的最好方法是什么? 5.12 #include和#include“file”有什么不同? 5.13 你能指定在编译时包含哪一个头文件吗? ...
然后再申明一个OleDbDataReader,来读取数据,用的是ExecuteReader(),objDataReader.Read()就开始读取了,在输出的时候我们要注意Text属性接受的只能是字符串,所以我们要把读出的数据都转化为字符串才行。...
5.9. 什么时候应该用宏代替函数? 83 5.10. 使用宏更好,还是使用函数更好? 83 5.11. 在程序中加入注释的最好方法是什么? 83 5.12. #include 和#include“file”有什么不同? 84 5.13. 你能指定在编译时包含哪一个...
4 软 件 最 终 产 品 :用 Java 语 言 开 发 的 软 件 可 以 具 有 可视化 、 可 听 化 、 可 操作 化 的 效 果 ,这 要 比 电 视 、 电 影 的 效果 更 为 理 想 ,因 为 它 可 以做 到 "即 时 、 交 互、 动 画 与 ...