unordered_map se utiliza para implementar tablas hash. Almacena pares de valores clave. Para cada clave, se calcula una función hash y el valor se almacena en esa entrada hash. Las funciones hash para tipos de datos estándar (int, char, string, ..) están predefinidas. ¿Cómo usar nuestros propios tipos de datos para implementar tablas hash?
unordered_map permite un tercer parámetro que se usa para especificar nuestra propia función hash.
// Create an unordered_map with given KeyType, // ValueType and hash function defined by // MyHashType unordered_map<KeyType, ValueType, MyHashType> um;
Aquí MyHashFunction es una clase o estructura que debe contener una función de operador() .
También debemos implementar el operador == en nuestra propia clase que se usa para manejar colisiones .
A continuación se muestra un código de muestra donde los objetos de la clase Person se usan como claves. Definimos nuestra propia función hash que utiliza la suma de las longitudes de los nombres y apellidos como clave en la tabla hash. Tenga en cuenta que el propósito de este código es solo demostrar que trabajar con un código simple y que la suma de longitudes puede no ser una buena idea como función hash.
CPP
// CPP program to demonstrate working of unordered_map
// for user defined data types.
#include <bits/stdc++.h>
using namespace std;
// Objects of this class are used as key in hash
// table. This class must implement operator ==()
// to handle collisions.
struct Person {
string first, last; // First and last names
Person(string f, string l)
{
first = f;
last = l;
}
// Match both first and last names in case
// of collisions.
bool operator==(const Person& p) const
{
return first == p.first && last == p.last;
}
};
class MyHashFunction {
public:
// Use sum of lengths of first and last names
// as hash function.
size_t operator()(const Person& p) const
{
return p.first.length() + p.last.length();
}
};
// Driver code
int main()
{
unordered_map<Person, int, MyHashFunction> um;
Person p1("kartik", "kapoor");
Person p2("Ram", "Singh");
Person p3("Laxman", "Prasad");
um[p1] = 100;
um[p2] = 200;
um[p3] = 100;
for (auto e : um) {
cout << "[" << e.first.first << ", "
<< e.first.last
<< "] = > " << e.second << '\n';
}
return 0;
}
[Laxman, Prasad] = > 100 [kartik, kapoor] = > 100 [Ram, Singh] = > 200
Otro ejemplo donde el operador predefinido funciona con una clase hash predefinida para hacer nuestro hash general.
CPP
// CPP program to demonstrate working of unordered_map
// for user defined data types.
#include <bits/stdc++.h>
using namespace std;
struct Person {
string first, last;
Person(string f, string l)
{
first = f;
last = l;
}
bool operator==(const Person& p) const
{
return first == p.first && last == p.last;
}
};
class MyHashFunction {
public:
// We use predefined hash functions of strings
// and define our hash function as XOR of the
// hash values.
size_t operator()(const Person& p) const
{
return (hash<string>()(p.first)) ^
(hash<string>()(p.last));
}
};
// Driver code
int main()
{
unordered_map<Person, int, MyHashFunction> um;
Person p1("kartik", "kapoor");
Person p2("Ram", "Singh");
Person p3("Laxman", "Prasad");
um[p1] = 100;
um[p2] = 200;
um[p3] = 100;
for (auto e : um) {
cout << "[" << e.first.first << ", "
<< e.first.last
<< "] = > " << e.second << '\n';
}
return 0;
}
[Laxman, Prasad] = > 100 [kartik, kapoor] = > 100 [Ram, Singh] = > 200