Hash Map di C++

Bagi programmer Java, mungkin tidak asing dengan kelas Hash Map. Map atau Dictionary merupakan container yang menyimpan elemennya dengan pasangan Key dan Value. Prinsipnya, untuk mengakses Value yang disimpan, cukup dengan memberikan Key.

Hash Map merupakan jenis Map yang memetakan Key menjadi Value dengan melakukan fungsi Hashing. Oleh karena itu, mengakses Value dari Hash Map mempunyai kompleksitas O(1) apabila diketahui Key-nya. O(1) ini berarti berapapun object yang disimpan didalam Hash Map, mengakses Value suatu Key membutuhkan waktu yang constant.

Sayangnya, STL C++ tidak menyertakan Hash Map, namun pada standard C++0x nanti, akan terdapat Map ini dengan nama unordered_map.

Aku sedikit tertarik dengan performa Hash Map, iseng-iseng melakukan percobaan kecil yang membandingkan Hash Map dengan Map bawaan STL. Kode dapat dilihat dibawah.

#include <stdlib.h>
#include <iostream>
#include <string>
#include <ctime>
#include <cerrno>
#include <ext/hash_map>
#include <map>

/**
 * Untuk mengambil detik saat ini
 */
std::time_t GetCurrentTime()
{
 std::time_t tReturn = std::time(0);
 if (tReturn == std::time_t(-1))
 {
  std::cerr<<"Bad time\n";
  exit(1);
 }
 return tReturn;
}

const int MAX = 8000000;

int main(int argc, char** argv) {
 //Fill Map and Hash Map
 std::map<int,int> tMap;
 __gnu_cxx::hash_map<int,int> tHashMap;
 for(int i = 0; i < MAX; ++i)
 {
  tMap[i] = i;
  tHashMap[i] = i;
 }
 //Map Time
 int tMapBefore = GetCurrentTime();
 for(int i = 0; i < MAX; ++i)
 {
  int j = tMap[i]; //really doing nothing
 }
 int tMapAfter = GetCurrentTime();
 std::cout << "Map: " << tMapAfter - tMapBefore << " second(s)\n";
 //Hash Map Time
 int tHashMapBefore = GetCurrentTime();
 for(int i = 0; i < MAX; ++i)
 {
  int j = tHashMap[i]; //really doing nothing
 }
 int tHashMapAfter = GetCurrentTime();
 std::cout << "Hash Map: " << tHashMapAfter - tHashMapBefore << " second(s)\n";

 return (EXIT_SUCCESS);
}

Hasilnya akan berbeda tergantung kekuatan komputer yang dipakai, namun pasti waktu Hash Map lebih ke kecil daripada Map. Dikomputerku, Hash Map memerlukan waktu 1 detik, padahal Map membutuhkan 5 detik. Mulai besok tampaknya semua penggunaan std::map akan diganti dengan __gnu_cxx::hash_map.