Slides TD Parcial2-151-164

Vista previa del material en texto

Función de hash: propiedades
▶ h es una función de hash.
▶ Hay más valores distintos en U que hashes resultantes posibles.
Es decir, puede haber colisiones.
▶ Una colisión son dos valores c1, c2 ∈ U tal que h(c1) = h(c2).
▶ Ante esto, es deseable que h tenga una distribución uniforme:
que el conjunto de valores posibles U se reparta, a través de h
uniformemente en el conjunto de valores de salida.
▶ Es deseable que costo de evaluar h() sea O(1), lo asumiremos
durante la clase.
7
Tabla de hash: colisiones
Dado que hay más claves posibles que posiciones de tabla, pueden
ocurrir colisiones: múltiples claves k1, k2, . . . , kn que se mapeen a
una misma posición de la tabla.
Tratamiento de colisiones. Ante colisiones se suele aplicar dos
técnicas:
▶ Encadenamiento: En cada posición de la tabla se mantiene una
lista de las claves guardadas en esa posición.
▶ Direccionamiento Abierto: Se guarda una única clave en cada
posición. Ante una colisión, se busca otra posición para la clave
a almacenar (con algún método).
9
Encadenamiento
Ante una colisión, simplemente almacenamos las claves que
colisionan en una lista.
Operaciones
▶ Agregar una clave c no presente: calcular el hash h(c) y agregar
la clave a la lista que está en la posición h(c).
▶ Buscar/Borrar una clave c : calcular el hash h(c) y recorrer la
lista correspondiente.
11
12
Encadenamiento � complejidades
Complejidades:
▶ Agregar una clave c no presente:
▶ Peor caso: O(1)
▶ Caso promedio: O(1)
▶ Buscar/Borrar una clave c : calcular el hash h(c) y recorrer la
lista correspondiente.
▶ Peor caso: O( |lista en h(c)| )
▶ Caso promedio: O(1), si la cantidad de slots de la tabla es
proporcional a la cantidad de claves almacenadas.
13
Direccionamiento Abierto
Ante una colisión, buscamos una nueva posición para la clave
repetida.
Técnicas de búsqueda
▶ Búsqueda lineal: Buscamos una posición vacía a partir de la
posición inicial.
h2(k, i) = (h(k) + i) mód |tabla|
▶ Búsqueda cuadrática: buscamos nuevas posiciones con saltos
cuadráticos desde la posición inicial.
h2(k, i) = (h(k) + c1 ∗ i + c2 ∗ i2) mód |tabla|
▶ Hashing doble: aplicamos otra función de hash para obtener una
nueva posición candidata.
h2(k, i) = (h(k) + i ∗ h′(k)) mód |tabla|
14
15
16
17
Hashing de tipos arbitrarios
▶ Las funciones de hash toman números enteros,
▶ Si queremos usar un tipo de datos T podemos primero
interpretar cada instancia de T como un número, para luego
aplicarle h(),
▶ También se podría usar una función de hash especí�ca para el
tipo T.
1 // Ejemplo: hash para string, suma simple de los caracteres
2 long hash(const std::string & s) {
3 long res = 0;
4 for (char c : s)
5 res += c;
6 return res;
7 }
18
Tabla de hash: recomendaciones
Regla general: Tabla de tamaño m número primo (ayuda con las
colisiones), un 30% más grande que la cantidad de claves que se
espera almacenar.
Algunos métodos de hashing
▶ H(k) = k mód m (�método de división�). m primo y no muy
cercano a una potencia de 2.
▶ H(k) = ⌊m(parte_decimal(kA))⌋ (�método de multiplicación�).
m = 2p y A = s/2w con 0 < s < 2w y w = log2(k).
Sugerencia de Knuth: A = (
√
5− 1)/2 = 0.6180339887...
19
Tabla de hash en la std
▶ std::unordered_set<T> y std::unordered_map<T,V> están
implementados sobre tablas de hash.
▶ Son equivalentes a std::set y std::map.
▶ Búsqueda, inserción y borrado en O(1) para el caso promedio.
Requisitos: que el tipo T tenga de�nido operator== (comparación) y
una función de hash, provista de la siguiente manera:
1 struct mi_hash {
2 size_t operator() (const T& key) const;
3 }
C++ std provee una buena struct hash<T> para muchos tipos
básicos T (numéricos, strings, punteros...), pero si no está de�nida
es necesario implementar este template para el T especí�co.
20
Tabla de hash en la std
1 struct mi_hash_string {
2 size_t operator() (const string& key) const{
3 long res = 0;
4 for (char c : key)
5 res += c;
6 return res;
7 }
8 };
9
10 int main(){
11 // Utilizando la función de hash de C++;
12 unordered_set<string> d1;
13 d1.insert("hola");
14
15 // Utilizando mi función de hash;
16 unordered_set<string, mi_hash_string> d2;
17 d2.insert("hola");
18 }
21
Tabla de hash en la std
1 struct point {
2 double x, y;
3 bool operator==(const point& other) const {
4 return x == other.x && y == other.y;
5 }};
6 // defino el hash de std para point
7 template<> struct std::hash<point> {
8 size_t operator()(const point& p) const {
9 return p.x*p.x+p.y*p.y;
10 }
11 };
12 int main() {
13 std::unordered_set<point> s;
14 s.insert({1,1});
15 s.insert({2,2});
16 for (auto p : s) {
17 std::cout << p.x << "," << p.y << std::endl;
18 }}
22