なぜ型取りの代わりにビット演算を使うのか

なぜ型取りの代わりにビット演算を使うのか
文書ディレクトリ

なぜ型取り

の代わりにビット演算を用いるのか.

引用

引用する
hashでkeyを検索すると、&置換%を使うことがよくあります.まず2つのコードを見てみましょう.

JDK 6の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のべき乗の場合(油断、最初は書いていません)、この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サイクル(注意、最小!!)が必要であることが明らかになった.だから後で自分で書くときにも、前者の書き方を使うことができる.