本文共 2842 字，大约阅读时间需要 9 分钟。

为啥要用位运算代替取模

引言

在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就会在初始化时，保证这一点：

1. public HashMap(int initialCapacity, float loadFactor) {
     2.     if (initialCapacity < 0)  3.         throw new IllegalArgumentException("Illegal initial capacity: " +  4.                                            initialCapacity);  5.     if (initialCapacity > MAXIMUM_CAPACITY)  6.         initialCapacity = MAXIMUM_CAPACITY;  7.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  8.         throw new IllegalArgumentException("Illegal load factor: " +  9.                                            loadFactor);  10. 11.     // Find a power of 2 >= initialCapacity  12.     int capacity = 1;  13.     while (capacity < initialCapacity)  14.         capacity <<= 1;  15. 16.     this.loadFactor = loadFactor;  17.     threshold = (int)(capacity * loadFactor);  18.     table = new Entry[capacity];  19.     init();  20. }

redis中也有类似的保证：

1. /* Our hash table capability is a power of two */  2. static unsigned long _dictNextPower(unsigned long size)  3. {  4.     unsigned long i = DICT_HT_INITIAL_SIZE;  5. 6.     if (size >= LONG_MAX) return LONG_MAX;  7.     while(1) {  8.         if (i >= size)  9.             return i;  10.         i *= 2;  11.     }  12. }

言归正传，大家都知道位运算的效率最高，这也是&取代%的原因，来看个程序：

1. int main(int argc, char* argv[])  2. {  3.     int a = 0x111;  4.     int b = 0x222;  5.     int c = 0;  6.     int d = 0;  7. 8.     c = a & (b-1);  9.     d = a % b;  10.  2.     return 0;  3. }    看反汇编的结果：反汇编代码  1. 13:       c = a & (b-1);  2. 00401044   mov         eax,dword ptr [ebp-8]  3. 00401047   sub         eax,1  4. 0040104A   mov         ecx,dword ptr [ebp-4]  5. 0040104D   and         ecx,eax  6. 0040104F   mov         dword ptr [ebp-0Ch],ecx  7. 14:       d = a % b;  8. 00401052   mov         eax,dword ptr [ebp-4]  9. 00401055   cdq  10. 00401056   idiv        eax,dword ptr [ebp-8]  11. 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周期（注意，是最少！！！） 效率显而易见。所以以后自己在写的时候，也可以使用前者的写法。

转载地址：https://blog.csdn.net/qq_22054285/article/details/88125068 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！