왜 추출 모형을 비트 연산으로 대체해야 합니까

자세히 보기
 
hash에서 키를 찾을 때% 대신% 를 사용하는 것을 자주 발견할 수 있습니다. 두 단락의 코드를 먼저 보세요.
 
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 주기가 필요하다(주의, 가장 적다!!!)효율은 명백히 알 수 있다.그래서 앞으로 자신이 쓸 때도 전자의 글씨를 사용할 수 있다.
 
 

Coding_ASM_-_Intel_Instruction_Set_Codes_and_Cycles.pdf (79.2 KB)

4

다운로드: 89