hashing | Juego 2 (enstringmiento separado)

¿Cuáles son las posibilidades de colisiones con la mesa grande?  
Las colisiones son muy probables aunque tengamos una mesa grande para guardar las llaves. Una observación importante es la paradoja del cumpleaños . Con solo 23 personas, la probabilidad de que dos personas tengan el mismo cumpleaños es del 50%.

¿Cómo manejar las colisiones?  
Existen principalmente dos métodos para manejar la colisión: 

1. Enstringmiento separado 
2. Direccionamiento abierto 

En este artículo, solo se analiza el enstringmiento por separado. Discutiremos el direccionamiento abierto en la próxima publicación. 

Enstringmiento separado: 
 la idea detrás del enstringmiento separado es implementar la array como una lista enlazada llamada string. El enstringmiento separado es una de las técnicas más populares y comúnmente utilizadas para manejar las colisiones. 

La estructura de datos de lista enlazada se utiliza para implementar esta técnica. Entonces, lo que sucede es que, cuando varios elementos se codifican en el mismo índice de ranura, estos elementos se insertan en una lista de enlaces únicos que se conoce como string. Aquí, todos los elementos que tienen un hash en el mismo índice de ranura se insertan en una lista enlazada. Ahora, podemos usar una tecla K para buscar en la lista enlazada simplemente recorriendo linealmente. Si la clave intrínseca de cualquier entrada es igual a K, significa que hemos encontrado nuestra entrada. Si hemos llegado al final de la lista enlazada y aún no hemos encontrado nuestra entrada, significa que la entrada no existe. Por lo tanto, la conclusión es que en un enstringmiento separado, si dos elementos diferentes tienen el mismo valor hash, almacenamos ambos elementos en la misma lista enlazada, uno tras otro.

Consideremos una función hash simple como » key mod 7 » y una secuencia de teclas como 50, 700, 76, 85, 92, 73, 101. 

Puede consultar el siguiente enlace para comprender cómo implementar un enstringmiento separado con C++.
Programa en C++ para hash con enstringmiento 

ventajas:

1. Simple de implementar. 
2. La tabla hash nunca se llena, siempre podemos agregar más elementos a la string. 
3. Menos sensible a la función hash o factores de carga. 
4. Se usa principalmente cuando se desconoce cuántas y con qué frecuencia se pueden insertar o eliminar claves. 

Desventajas: 

1. El rendimiento de caché del enstringmiento no es bueno ya que las claves se almacenan mediante una lista vinculada. El direccionamiento abierto proporciona un mejor rendimiento de caché ya que todo se almacena en la misma tabla. 
2. Desperdicio de espacio (algunas partes de la tabla hash nunca se usan) 
3. Si la string se hace larga, el tiempo de búsqueda puede volverse O(n) en el peor de los casos. 
4. Utiliza espacio extra para enlaces. 

Desempeño del enstringmiento: 
el desempeño del hash se puede evaluar bajo el supuesto de que cada clave tiene la misma probabilidad de tener un hash en cualquier ranura de la tabla (hashing uniforme simple).  

 m = Number of slots in hash table
 n = Number of keys to be inserted in hash table
 
 Load factor α = n/m 
  
 Expected time to search = O(1 + α)
 
 Expected time to delete = O(1 + α)

Time to insert = O(1)

 Time complexity of search insert and delete is 
 O(1) if  α is O(1)

Estructuras de datos para strings de almacenamiento: 

• listas enlazadas
  • Buscar: O(l) donde l = longitud de la lista enlazada
  • Borrar: O(l)
  • Insertar: O(l)
  • No compatible con caché
• Arrays de tamaño dinámico (Vectores en C++, ArrayList en Java, lista en Python)
  • Búsqueda: O(l) donde l = longitud de la array
  • Borrar: O(l)
  • Insertar: O(l)
  • Compatible con caché
• BST autoequilibrado (árboles AVL, árboles negros rojos)
  • Buscar: O(registro(l))
  • Borrar: O(registro(l))
  • Insertar: O(l)
  • No compatible con caché
  • Java 8 en adelante use esto para HashMap

Publicación siguiente:  
Direccionamiento abierto para el manejo de colisiones