c# - funciona - hashset vs list
¿Cuál es la complejidad del tiempo de búsqueda de HashSet<T>(IEqualityComparer<T>)? (4)
si tuviera que escribir un Comparer para pasar al constructor de un HashSet, cada vez que realice una búsqueda, el código del Comparer tendría que ejecutarse en cada tecla para verificar si había una coincidencia. Esto no sería O (1), pero O (n).
Llamemos al valor que está buscando para el valor de "consulta".
¿Puede explicar por qué cree que el comparador debe ejecutarse en cada tecla para ver si coincide con la consulta?
Esta creencia es falsa. (¡A menos que, por supuesto, el código hash proporcionado por el comparador sea el mismo para cada clave!) El algoritmo de búsqueda ejecuta el comparador de igualdad en cada clave cuyo código hash coincida con el código hash de la consulta, modulo el número de cubos en la tabla hash. Así es como las tablas hash obtienen O (1) tiempo de búsqueda.
¿La implementación construye internamente una tabla de búsqueda a medida que se agregan elementos a la colección?
Sí.
En general, ¿cómo puedo obtener información sobre la complejidad de las estructuras de datos .NET?
Lea la documentación.
En C # .NET, me gusta usar HashSets debido a su supuesta complejidad de tiempo O (1) para las búsquedas. Si tengo un gran conjunto de datos que se van a consultar, a menudo prefiero usar un HashSet a una lista, ya que tiene esta complejidad de tiempo.
Lo que me confunde es el constructor de HashSet, que toma a IEqualityComparer como un argumento:
http://msdn.microsoft.com/en-us/library/bb359100.aspx
En el enlace anterior, las observaciones indican que el "constructor es una operación O (1)", pero si este es el caso, tengo curiosidad si la búsqueda sigue siendo O (1).
En particular, me parece que, si tuviera que escribir un Comparer para pasar al constructor de un HashSet, cada vez que realice una búsqueda, el código del Comparer tendría que ejecutarse en cada tecla para verificar si había un partido. Esto no sería O (1), pero O (n).
¿La implementación construye internamente una tabla de búsqueda a medida que se agregan elementos a la colección?
En general, ¿cómo puedo obtener información sobre la complejidad de las estructuras de datos .NET?
Dependería de la calidad de la función hash ( GetHashCode() ) que proporciona su implementación de IEqualityComparer . La función hash ideal debería proporcionar un conjunto aleatorio bien distribuido de códigos hash. Estos códigos hash se utilizarán como un índice que permite asignar la clave a un valor, por lo que la búsqueda de un valor por clave se vuelve más eficiente, especialmente cuando una clave es un objeto / estructura compleja.
El código del Comparador tendría que ejecutarse en cada tecla para verificar si había una coincidencia. Esto no sería O (1), pero O (n).
No es así como funciona la tabla hash, es un tipo de búsqueda directa de fuerza bruta. En el caso de la tabla hash, tendría un enfoque más inteligente que utiliza la búsqueda por índice (código hash).
La búsqueda sigue siendo O (1) si pasa un IEqualityComparer. El conjunto de hash todavía usa la misma lógica como si no pasara un IEqualityComparer; solo utiliza las implementaciones de IEqualityComparer de GetHashCode and Equals en lugar de los métodos de instancia de System.Object (o las anulaciones proporcionadas por el objeto en cuestión).
Un HashSet funciona a través de hash (a través de IEqualityComparer.GetHashCode ) los objetos que inserta y arroja los objetos en grupos por el hash. Los propios depósitos se almacenan en una matriz, de ahí la parte O (1).
Por ejemplo (esto no necesariamente es exactamente cómo funciona la implementación de C #, solo le da un sabor) toma el primer carácter del hash y lanza todo con un hash comenzando con 1 en el bucket 1. Hash de 2, bucket 2, y así en. Dentro de ese cubo hay otra serie de cubos que se dividen por el segundo carácter del hash. Así que para cada personaje en el hash ...
Ahora, cuando miras algo, lo aplasta y salta a través de los cubos apropiados. Tiene que hacer varias búsquedas de matrices (una para cada carácter en el hash) pero no crece como una función de N, la cantidad de objetos que ha agregado, por lo tanto, la calificación O (1).
Para su otra pregunta, aquí hay una publicación de blog con la complejidad de una serie de operaciones de colecciones: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html