hash_map

TODO

Nicht im Standard, aber in SGI-STL vorhanden

http://www.heise.de/foren/go.shtml?t=1&T=thread%20mfgkw&sres=1&msg_id=5132619&forum_id=44546&k=310a419ed690e467bb5a41f304f8c900
19. Februar 2004 13:43
Re: Hash Tables mit C++
Klaus Wachtler	

Erik Meusel schrieb am 19. Februar 2004 13:07

> Klaus Wachtler schrieb am 19. Februar 2004 9:56
> ...
> Danke für Dein Beispiel im anderen Posting, mir fehlte bisher im
> Thread einfach der Hinweis darauf, wie man eine Hashfunktion angeben
> kann, das ist alles. ;)
> ...

Dann hilft vielleicht noch folgendes:
Für eine eigene Hashfunktion kann man sich aussuchen, ob man
die template class hash spezialisiert (was man für einen gegebenen
Datentyp des Schlüssels nur einmal machen kann in einem
Programm), oder ob man eine "normale" Funktion schreibt, und dem
Konstruktor der hash_map oder hash_set übergibt.
Dadurch könnte man für mehrere Hashtabellen gleichen Schlüsseltyps
verschiedene Hashfunktionen verwenden.

Beispiel 1 (Spezialisierung hash<double>; damit man hash
spezialisieren
kann, habe ich als Schlüsseltyp double genommen, auch wenn es
eigentlich
dämlich ist):
#include <iostream>
#include <exception>
#include <cstddef>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;


struct eqdouble
{
  bool operator()(double d1, double d2) const
  {
    return  d1 == d2;
  }
};

// Typ eines Funktionsobjekts als Parameter an template
namespace __gnu_cxx
{
  template<> struct hash<double>
  {
    size_t operator()( double d ) const
    {
      return  (size_t)(fabs( d ));
    }
  };
};

int main( int nargs, char **args )
{
  hash_map<double,int,hash<double>,eqdouble>  Map;

  Map[3.14] = 3;
  Map[2.7] = 2;
  Map[2.8] = 15;

  cout << "2.7 -> " << Map[2.7] << endl;

  hash_map<double,int,hash<double>,eqdouble>::iterator   i;
  double key = 2.9;
  if( (i=Map.find( key ))!=Map.end() )
  {
    cout << i->first << " -> " << i->second << endl;
  }
  else
  {
    cout << key << " nicht gefunden!" << endl;
  }
} // main( int nargs, char **args )


Beispiel 2 (das selbe, aber mit einer echten Funktion):
#include <iostream>
#include <exception>
#include <cstddef>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;


struct eqdouble
{
  bool operator()(double d1, double d2) const
  {
    return  d1 == d2;
  }
};

// echte Funktion als Hash-Funktion:
size_t hash_d( double d )
{
  return  (size_t)(fabs( d ));
}

int main( int nargs, char **args )
{
  hash_map<double,int,size_t(*)(double),eqdouble>  Map(10,hash_d);

  Map[3.14] = 3;
  Map[2.7] = 2;
  Map[2.8] = 15;

  cout << "2.7 -> " << Map[2.7] << endl;

  hash_map<double,int,size_t(*)(double),eqdouble>::iterator    i;
  double key = 2.9;
  if( (i=Map.find( key ))!=Map.end() )
  {
    cout << i->first << " -> " << i->second << endl;
  }
  else
  {
    cout << key << " nicht gefunden!" << endl;
  }

} // main( int nargs, char **args )


Beides mit g++ 3.3.2 probiert.

mfgkw



AnyWare@Wachtler.de