Las tablas hash son estructuras de datos importantes, y el núcleo las utiliza en muchos subsistemas. Es bastante común que cada usuario implemente su propia versión, según las necesidades y la complejidad. Sin embargo, en general, las estructuras de datos como estas están bastante integradas en el corazón de los componentes que las utilizan.
Se deben considerar tres factores al decidir si usar una tabla hash o alguna otra estructura de datos más elegante / más compleja, como los árboles. Estos son (i) la clave y el método hash, (ii) la cantidad de objetos ( n ) y (iii) la cantidad de cubos ( m ) en la tabla. Dado que las búsquedas son O(n/m) , tener una relación 1: 1 se acercará naturalmente a la complejidad constante, O(1) y, por lo tanto, reducirá las colisiones y hará un uso ideal de dichas estructuras de datos. Es por esto que el núcleo no tiene una forma única de manejar las tablas hash, y es mejor que cada usuario decida las mejores condiciones para el trabajo. Del mismo modo, se sabe que las tablas hash son útiles para situaciones en las que el rendimiento es crítico (rutas activas) y es mejor eliminar cualquier sobrecarga adicional que pueda imponer alguna biblioteca / módulo .
En 2012, Sasha Levin pudo unificar algunas de las tablas hash en el kernel, proporcionando un conjunto de interfaces simple y directo. Algunos usuarios populares incluyen las colas de trabajo, el programador de elevadores para bloques de E / S y las páginas transparentes (THP) en la administración de memoria, entre otros. Todos estos están asignados estáticamente .
- ¿Cuál es el algoritmo utilizado por la búsqueda de imagen inversa de Google (es decir, la búsqueda por imagen)? ¿Qué algoritmos necesitaría entender para crear una funcionalidad similar a pequeña escala?
- Para verificar que la lista vinculada es circular, ¿cuál será la condición del bucle? Conozco un proceso adicional como tomar dos punteros. Por favor sugiérame
- ¿La técnica de dos punteros se considera una búsqueda binaria en algunos problemas?
- Plegamiento de proteínas: ¿Qué algoritmos se usan en el juego Foldit?
- ¿Sigue siendo relevante el modelado de objetos, o se ha reemplazado hoy solo con datos y algoritmos?
Por otro lado, las tablas asignadas dinámicamente pueden ser mucho mejores en escenarios desconocidos y permiten una mejor escalabilidad. Esto normalmente se hace usando alguna variante de kmalloc() o alloc_large_system_hash() . La función posterior es particularmente útil para tablas hash grandes y sistemas NUMA, ya que la memoria se distribuye entre los nodos, por lo que tiene una mejor localidad de datos. Esta memoria proviene del inicio temprano. Los usuarios incluyen futexes, la tabla PID y el dcache.
