dalvik哈希算法

时间：2010-08-20 来源：hunterzy416

采用的是现成探测的方法：
static bool resizeHash(HashTable* pHashTable, int newSize)
{
    HashEntry* pNewEntries;
    int i;

    assert(countTombStones(pHashTable) == pHashTable->numDeadEntries);
    //LOGI("before: dead=%d\n", pHashTable->numDeadEntries);

    pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashEntry));
    if (pNewEntries == NULL)
        return false;

    for (i = 0; i < pHashTable->tableSize; i++) {
        void* data = pHashTable->pEntries[i].data;
        if (data != NULL && data != HASH_TOMBSTONE) {
            int hashValue = pHashTable->pEntries[i].hashValue;
            int newIdx;

            /* probe for new spot, wrapping around */
            newIdx = hashValue & (newSize-1);
            while (pNewEntries[newIdx].data != NULL)
                newIdx = (newIdx + 1) & (newSize-1);

            pNewEntries[newIdx].hashValue = hashValue;
            pNewEntries[newIdx].data = data;
        }
    }

    free(pHashTable->pEntries);
    pHashTable->pEntries = pNewEntries;
    pHashTable->tableSize = newSize;
    pHashTable->numDeadEntries = 0;

    assert(countTombStones(pHashTable) == 0);
    return true;
}

个人备注：
1. 哈希表的建立，是以2的N次方为大小的，目的是为了mod运算的时候直接使用&操作符，提高运算性能。
2. 由于采用线性探测，这个时候涉及到了删除操作带来的麻烦，因此删除数据的时候，不知直接将data置空，而是让他等于HASH_TOMBSTONE

相关阅读更多 +