Apa cara terbaik untuk menggunakan HashMap di C ++?

Saya tahu bahwa STL memiliki API HashMap, tetapi saya tidak dapat menemukan dokumentasi yang baik dan menyeluruh dengan contoh yang baik mengenai hal ini.

Setiap contoh yang baik akan dihargai.

Pustaka standar mencakup wadah yang dipesan dan peta yang tidak berurutan ( std::mapdan std::unordered_map). Dalam peta terurut, elemen diurutkan berdasarkan kunci, masukkan dan akses ada di O (log n) . Biasanya perpustakaan standar secara internal menggunakan pohon merah-hitam untuk peta yang dipesan. Tapi ini hanyalah detail implementasi. Dalam peta yang tidak terurut, masukkan dan akses ada di O (1). Itu hanyalah nama lain untuk hashtable.

Contoh dengan (dipesan) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Keluaran:

23
Kunci: halo Nilai: 23

Jika Anda perlu memesan dalam wadah Anda dan baik-baik saja dengan runtime O (log n) maka gunakan saja std::map.

Jika tidak, jika Anda benar-benar membutuhkan tabel hash-table (O (1)), periksa std::unordered_map, yang memiliki mirip dengan std::mapAPI (misalnya dalam contoh di atas Anda hanya perlu mencari dan mengganti mapdengan unordered_map).

The unordered_mapwadah diperkenalkan dengan C ++ 11 standar revisi. Jadi, tergantung pada kompiler Anda, Anda harus mengaktifkan fitur C ++ 11 (mis. Ketika menggunakan GCC 4.8 Anda harus menambahkan -std=c++11ke CXXFLAGS).

Bahkan sebelum rilis C ++ 11 GCC didukung unordered_map- di namespace std::tr1. Jadi, untuk kompiler GCC lama Anda dapat mencoba menggunakannya seperti ini:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Ini juga merupakan bagian dari boost, yaitu Anda dapat menggunakan boost-header yang sesuai untuk portabilitas yang lebih baik.

A hash_mapadalah versi yang lebih lama dan tidak standar tentang apa yang untuk tujuan standardisasi disebut unordered_map(awalnya dalam TR1, dan termasuk dalam standar sejak C ++ 11). Seperti namanya, itu berbeda dari std::mapterutama dalam menjadi unordered - jika, misalnya, Anda iterate melalui peta dari begin()ke end(), Anda mendapatkan barang-barang dalam rangka oleh kunci ¹ , tetapi jika Anda iterate melalui unordered_mapdari begin()ke end(), Anda mendapatkan item dalam pesanan kurang lebih sewenang-wenang.

Sebuah unordered_mapbiasanya diharapkan memiliki kompleksitas konstan. Artinya, penyisipan, pencarian, dll, biasanya pada dasarnya membutuhkan jumlah waktu yang tetap, terlepas dari berapa banyak item dalam tabel. Suatu std::mapmemiliki kompleksitas yang logaritmik pada jumlah item yang disimpan - yang berarti waktu untuk memasukkan atau mengambil item tumbuh, tetapi cukup lambat , ketika peta bertambah besar. Misalnya, jika diperlukan 1 mikrodetik untuk mencari satu dari 1 juta item, maka Anda dapat mengharapkannya mengambil sekitar 2 mikrodetik untuk mencari satu dari 2 juta item, 3 mikrodetik untuk satu dari 4 juta item, 4 mikrodetik untuk satu dari 8 juta barang, dll.

Dari sudut pandang praktis, itu sebenarnya bukan keseluruhan cerita. Secara alami, tabel hash sederhana memiliki ukuran tetap. Menyesuaikannya dengan persyaratan ukuran variabel untuk wadah serba guna agak tidak sepele. Akibatnya, operasi yang (berpotensi) menumbuhkan tabel (misalnya, penyisipan) berpotensi relatif lambat (yaitu, sebagian besar cukup cepat, tetapi secara berkala satu akan jauh lebih lambat). Pencarian, yang tidak dapat mengubah ukuran tabel, umumnya jauh lebih cepat. Akibatnya, sebagian besar tabel berbasis hash cenderung terbaik ketika Anda melakukan banyak pencarian dibandingkan dengan jumlah penyisipan. Untuk situasi di mana Anda memasukkan banyak data, lalu beralih melalui tabel sekali untuk mengambil hasil (misalnya, menghitung jumlah kata unik dalam file) kemungkinan bahwastd::map akan sama cepat, dan sangat mungkin bahkan lebih cepat (tapi, sekali lagi, kompleksitas komputasinya berbeda, sehingga juga dapat bergantung pada jumlah kata unik dalam file).

^{1 Jika urutannya ditentukan oleh parameter templat ketiga saat Anda membuat peta, std::less<T>secara default.}

Berikut adalah contoh yang lebih lengkap dan fleksibel yang tidak dihilangkan termasuk untuk menghasilkan kesalahan kompilasi:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Masih tidak terlalu berguna untuk kunci, kecuali mereka ditetapkan sebagai pointer, karena nilai yang cocok tidak akan berhasil! (Namun, karena saya biasanya menggunakan string untuk kunci, mengganti "string" untuk "const void *" dalam deklarasi kunci harus menyelesaikan masalah ini.)

Bukti yang std::unordered_mapmenggunakan peta hash di stdlibc GCC ++ 6.4

Ini disebutkan di: https://stackoverflow.com/a/3578247/895245 tetapi dalam jawaban berikut: Struktur data apa yang ada di dalam std :: map di C ++? Saya telah memberikan bukti lebih lanjut tentang implementasi stdlibc ++ 6.4 GCC oleh:

• GDB langkah debugging ke dalam kelas
• analisis karakteristik kinerja

Berikut adalah pratinjau grafik karakteristik kinerja yang dijelaskan dalam jawaban itu:

Cara menggunakan kelas kustom dan fungsi hash dengan unordered_map

Jawaban ini memaku: C ++ unordered_map menggunakan tipe kelas khusus sebagai kuncinya

Kutipan: kesetaraan:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Fungsi hash:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Bagi kita yang mencoba mencari tahu cara hash kelas kita sendiri sementara masih menggunakan templat standar, ada solusi sederhana:

1. Di kelas Anda, Anda perlu mendefinisikan overload operator kesetaraan ==. Jika Anda tidak tahu bagaimana melakukan ini, GeeksforGeeks memiliki tutorial hebat https://www.geeksforgeeks.org/operator-overloading-c/

2. Di bawah namespace standar, nyatakan struct template yang disebut hash dengan classname Anda sebagai tipe (lihat di bawah). Saya menemukan blogpost hebat yang juga menunjukkan contoh menghitung hash menggunakan XOR dan bitshifting, tapi itu di luar ruang lingkup pertanyaan ini, tetapi juga termasuk petunjuk terperinci tentang bagaimana menyelesaikan menggunakan fungsi hash juga https://prateekvjoshi.com/ 2014/06/05 / using-hash-function-in-c-for-user-defined-class /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

3. Jadi untuk mengimplementasikan hashtable menggunakan fungsi hash baru Anda, Anda hanya perlu membuat std::mapatau std::unordered_mapseperti yang biasa Anda lakukan dan gunakan my_typesebagai kuncinya, pustaka standar akan secara otomatis menggunakan fungsi hash yang Anda tetapkan sebelumnya (dalam langkah 2) untuk hash kunci kamu.

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}