(Cuándo) es la búsqueda de tabla hash O (1)?

71

A menudo se dice que la búsqueda de tabla hash funciona en tiempo constante: se calcula el valor hash, lo que le da un índice para una búsqueda de matriz. Sin embargo, esto ignora las colisiones; en el peor de los casos, todos los elementos caen en el mismo depósito y el tiempo de búsqueda se vuelve lineal ( ). $\Theta(n)$

¿Existen condiciones en los datos que pueden hacer que la búsqueda de tablas hash sea realmente ? ¿Es eso solo en promedio, o puede una tabla hash tener peor búsqueda? $O(1)$ $O(1)$

Nota: vengo desde la perspectiva de un programador aquí; cuando almaceno datos en una tabla hash, casi siempre son cadenas o algunas estructuras de datos compuestos, y los datos cambian durante la vida útil de la tabla hash. Entonces, aunque aprecio las respuestas sobre los hashes perfectos, son lindos pero anecdóticos y no prácticos desde mi punto de vista.

Seguimiento de PS: ¿Para qué tipo de datos son las operaciones de tabla hash O (1)?

algorithm-analysis data-structures runtime-analysis hash-tables Gilles 'SO- deja de ser malvado'
fuente

3

¿Se puede vivir con

tiempo de acceso amortizado? En general, el rendimiento de la tabla hash dependerá en gran medida de la sobrecarga de tablas hash dispersas que esté preparado para tolerar y de cómo se distribuyan los valores hash reales.

O (1)

$\cal{O}(1)$

Raphael

55

Ah, por cierto: puede evitar el comportamiento lineal del peor de los casos utilizando árboles de búsqueda (equilibrados) en lugar de listas.

Raphael

1

@Raphael Estaría muy interesado en una respuesta que explique (en líneas generales) cuándo puedo contar con

amortizado y cuándo no puedo. En cuanto a cómo se distribuyen los valores hash, esa es realmente mi pregunta: ¿cómo puedo saberlo? Sé que se supone que las funciones hash distribuyen bien los valores; pero si siempre lo hicieran, el peor de los casos nunca se alcanzaría, lo que no tiene sentido.

O (1)

$O(1)$

Gilles 'SO- deja de ser malvado'

1

También tenga cuidado con la optimización prematura; para datos pequeños (varios miles de elementos), a menudo he visto que los árboles binarios balanceados

superan a las tablas hash debido a una sobrecarga menor (las comparaciones de cadenas son mucho más baratas que los hashes de cadenas).

O (\log n)

$O(\log n)$

isturdy

Continuemos esta discusión en el chat .

Raphael

41

Hay dos configuraciones en las que puede obtener peor de los casos. $O(1)$

Si su configuración es estática, entonces el hashing FKS obtendrá las garantías peor de los casos . Pero como indicó, su configuración no es estática. $O(1)$
Si usa el hash de Cuckoo, las consultas y eliminaciones son peor de los casos, pero la inserción es solo esperada. El hash de cuco funciona bastante bien si tiene un límite superior en el número total de inserciones y establece que el tamaño de la tabla sea aproximadamente un 25% más grande. $O(1)$ $O(1)$

Hay más información aquí .

Suresh
fuente

3

¿Podrías expandirte en FKS y Cuckoo? Ambos términos son nuevos para mí.

Gilles 'SO- deja de ser malvado'

1

¿Qué pasa con el hashing dinámico perfecto? Tiene

búsquedas en el peor de los casos y

inserción y eliminación amortizadas. ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8165 )

O (1)

$O(1)$

O (1)

$O(1)$

Joe

2

FKS son las iniciales de (Fredman, Komlós, Szemerédi) y Cuckoo es el nombre de una especie de novia. Es útil para este tipo de picadillo, porque los polluelos de cuco empujan los huevos del nido. Esto se parece un poco a cómo funciona este método hasing.

uli

1

@Suresh: ¿En serio? Pensé que necesitabas funciones independientes de

, que siempre asociaba con la necesidad de expansores. Estoy corregido. Eliminaré mi comentario en un momento.

\log n

$\log n$

Louis

1

Para hacer un comentario más útil sobre esta respuesta, como señala @Suresh, el hash de cuco funcionará bien sin las sofisticadas (y grandes) funciones de hash utilizadas para analizarlo teóricamente.

Louis

21

Esta respuesta resume partes de TAoCP Vol. 3, Cap. 6.4.

$V$ $n$ $A$ $m$ $h : V \to [0..M)$ $M \ll |V|$ $\alpha = \frac{n}{m}$ $A$ $m=M$ $m \ll M$ $m$

$h$ $\mathcal{O}(1)$

$[0..M)$ $C_n^S$ $C_n^U$

Encadenamiento

$\frac{n}{m}$

C_{n}^{S} \approx 1 + \frac{α}{2} and C_{n}^{U} \approx 1 + \frac{α^{2}}{2} .

$C_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C_n^U \approx 1 + \frac{\alpha^2}{2} .$

Sondeo lineal

$v$

h (v), h (v) - 1, \dots, 0, m - 1, \dots, h (v) + 1

$h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1$

v

$v$

α \to 1

$\alpha \to 1$

C_{n}^{S} \approx \frac{1}{2} (1 + \frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{2} (1 + {(\frac{1}{1 - α})}^{2}) .

$C_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).$

α < 0.75

$\alpha < 0.75$

Hashing doble

$M$

C_{n}^{S} \approx \frac{1}{α} \ln (\frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{1 - α} .

$C_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C_n^U \approx \frac{1}{1-\alpha} .$

Tenga en cuenta que eliminar elementos de tablas y extenderlas tiene diferentes grados de dificultad para los métodos respectivos.

$\mathcal{O}(1)$ $\alpha$ $h$

$h$
Hashtable

Rafael
fuente

10

$S$ $\{0, 1, 2, ..., n\}$ $O(1)$ $O(1)$ $l$ $S$ $l$ $x$ $x \in S$ $O(|l|)$ $S$ $O(|S|)$ $O(|l| + |S|)$ $O(|l||S|)$ $O(\log(|l|)|S|)$ $O(|l|)$ $l$

$O(|l|)$

$l$ $U \subset \mathbb{N}$ $S \subseteq U$ $x \in S$ $l$ $l$ $h: U \rightarrow \{true, false\}$ $h$ $h(x) = false$ $x \in U$ $y$ $l$ $h(y) = true$ $O(|l|)$ $O(|U|)$

$l$ $O(|U|)$ $O(|1|)$ $O(|U|)$

$U$ $h$

Patrick87
fuente

O (| l |)

$O(|l|)$

O (| S |)

$O(|S|)$

O (| l | \cdot | S |)

$O(|l|\cdot|S|)$

h

$h$

h : U \to {f a l s e, t r u e}

$h:U\to\{\mathrm{false},\mathrm{true}\}$

h

$h$

@Gilles Básicamente se usa como una tabla de búsqueda para la membresía de la lista. Cuando tiene una función hash perfecta con un inverso conocido y barato, en lugar de almacenar la cosa en sí, solo necesita almacenar 1 bit (ya sea que se haya agregado la cosa con el hash único). Si las colisiones son posibles, creo que hacer esto se conoce como un filtro de Bloom, pero en cualquier caso puede proporcionar un "no" definitivo a la cuestión de la membresía, que todavía es útil en muchos escenarios.

Patrick87

9

$\cal{O}(1)$

$\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$

Nicholas Meyer
fuente

Una función hash perfecta sería perfecta, pero ¿cómo obtengo una? ¿Cuánto me costará? ¿Y cómo sé cuál es el número máximo o esperado de colisiones?

Gilles 'SO- deja de ser malvado'

2

@Gilles, una función hash perfecta es cualquier función que produzca un hash único para todas las entradas posibles. Si sus posibles entradas son finitas (y únicas), esto es fácil de hacer.

Rafe Kettler

1

@RafeKettler Mis entradas son típicamente cadenas o estructuras de datos compuestos, y generalmente agrego y elimino entradas a medida que evolucionan mis datos. ¿Cómo hago un hash perfecto para esto?

Gilles 'SO- deja de ser malvado'

44

Sí, pero ese es el punto. Una función hash perfecta determinista no existe si el dominio es mayor que el rango.

Suresh

@Suresh: si se le permite elegir una nueva función hash y aumentar el tamaño de la tabla cada vez que hay una colisión, siempre puede encontrar una función hash (determinista) que, para los datos que ya están en la tabla más la nueva elemento que está intentando insertar: no tiene colisiones (es "perfecto"). Es por eso que el hashing dinámico perfecto elige periódicamente una nueva función hash aleatoria.

David Cary

(Cuándo) es la búsqueda de tabla hash O (1)?

Respuestas:

Encadenamiento

Sondeo lineal

Hashing doble