私は文字列を受け取り、それらを文字列 -> 整数ハッシュ マップに挿入することで、一意の文字列の出現回数をカウントする基本的なプログラムを作成しました。
ストレージには std::tr1::unordered_map を使用し、カスタム ハッシュ関数とカスタム等値関数用にテンプレート化します。キーの種類は、実際にchar*は too-slow ではなくですstd::string。
次に、同じコードを変更して、非常に単純なハッシュ テーブル (実際には、ハッシュによってインデックス付けされた {key, value} 構造体の配列) を使用し、2 のべき乗のサイズと衝突の線形プローブを使用しました。プログラムは 33% 速くなりました。
tr1::unordered_map を使用していたときにハッシュ テーブルのサイズを事前に設定して、サイズが大きくならないようにし、まったく同じハッシュ ルーチンと比較ルーチンを使用していたことを考えると、tr1::unordered_map の動作が 50% 遅くなる理由は次のとおりです。想像できる最も基本的なハッシュマップと比較して?
ここで「単純」と話しているハッシュ マップ タイプのコードは次のとおりです。
typedef struct dataitem {
char* item;
size_t count;
} dataitem_t;
dataitem_t hashtable[HASHTABLE_SIZE] = {{NULL,0}}; // Start off with empty table
void insert(char* item) {
size_t hash = generate_hash(item);
size_t firsthash = hash;
while (true) {
hash &= HASHTABLE_SIZE_MASK; // Bitmasking effect is hash %= HASHTABLE_SIZE
if (hashtable[hash].item == NULL) { // Free bucket
hashtable[hash].item = item;
hashtable[hash].count = 1;
break;
}
if (strcmp(hashtable[hash].item, item) == 0) { // Not hash collision; same item
hashtable[hash].count += 1;
break;
}
hash++; // Hash collision. Move to next bucket (linear probing)
if (hash == firsthash) {
// Table is full. This does not happen because the presizing is correct.
exit(1);
}
}
}