Release Hash Map yang Windows-Linux Compatible

Code berikut merupakan source code dari kelas hashmap yang dapat digunakan baik windows maupun linux, hehehehe

//file HashMap.h
#ifndef HASH_MAP
#define HASH_MAP

#ifdef WIN32
#include <hash_map>
#define hashmap stdext::hash_map

#else
#include <ext/hash_map>
#define hashmap __gnu_cxx::hash_map

#endif

#endif

sebenarnya hashmap bukan sebuah kelas, hanya alias aja untuk stdext::hash_map di windows atau __gnu_cxx::hash_map untuk linux.  Source diatas dapat digunakan untuk kode yang ada posting ini sebagai contoh penggunaan. Tinggal include aja file HashMap.h di file apapun, dan hashmap langsung dapat digunakan seperti container STL lainnya.

Untuk full compatibility antara windows dan linux, terdapat beberapa hal yang perlu diperhatikan:

• Gunakan tipe dasar sebagai key dan value
• Jika ingin menyimpan tipe bentukan ato object, gunakan pointer terhadap tipe/object tersebut
• Khusus untuk string, akan bermasalah di linux, jadi gunakan const char* saja. Mengubah std::string ke const char* tinggal memanggil fungsi c_str(). Untuk sebaliknya cukup dengan std::string(/*si const char**/)

Sebenarnya banyak implementasi HashMap diluar sana yang independent dan full featured. Ini hanya pembungkus dari hashmap bawaan untuk mengatasi masalah kompatibilitas, karena di windows dan linux berbeda. Semoga bermanfaat, hehe.

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.