¿Cuál es la complejidad del tiempo de búsqueda de HashSet <T> (IEqualityComparer <T>)?

Question

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 en una lista, ya que tiene esta complejidad de tiempo.

Lo que me confunde es el constructor de la HashSet, que toma IEqualityComparer como argumento:

http://msdn.microsoft.com/en-us/library/bb359100.aspx

En el enlace anterior, las observaciones señalan que el "constructor es un (1) Operación O, "pero si este es el caso, tengo curiosidad si la búsqueda todavía es O (1).

En particular, me parece que, si tuviera que escribir un Comparer para pasar al constructor de un HashSet, cada vez que realizo una búsqueda, el código Comparer debería ejecutarse en cada clave para verificar ver si hubo una coincidencia. Esto no sería O (1), sino O (n).

¿La implementación construye internamente una tabla de búsqueda cuando los elementos se agregan a la colección?

En general, ¿cómo puedo averiguar la información sobre la complejidad de las estructuras de datos .NET?

Answer 1

A HashSet funciona a través de hash (a través de IEqualityComparer.GetHashCode) los objetos que inserta y arroja los objetos en cubos por el hash. Los cubos mismos se almacenan en una matriz, de ahí la parte O (1).

Por ejemplo (esto no es exactamente cómo funciona la implementación de C#, simplemente da un sabor) toma el primer caracter del hash y arroja todo con un hash que comienza con 1 en el cubo 1. Hash of 2, bucket 2, y así sucesivamente. Dentro de ese cubo hay otra serie de cubos que se dividen por el segundo personaje en el hash. Así sucesivamente para cada personaje en el hash ...

Ahora, cuando busca algo, lo mezcla y salta a través de los intervalos adecuados. Tiene que hacer varias búsquedas de matriz (una para cada carácter en el hash) pero no crece como una función de N, la cantidad de objetos que ha agregado, de ahí la clasificación O (1).

Para su otra pregunta, aquí es un blog con la complejidad de una serie de operaciones colecciones: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

Answer 2

Sería depende de la calidad de la función hash (GetHashCode()) su aplicación proporciona IEqualityComparer. La función hash ideal debería proporcionar un conjunto aleatorio bien distribuido de códigos hash. Estos códigos hash se usarán como un índice que permite asignar una clave a un valor, por lo que buscar un valor por clave se vuelve más eficiente, especialmente cuando una clave es un objeto/estructura compleja.

el código de Comparer tendría que ejecutarse en cada tecla para comprobar ver si hubiera una coincidencia. Esto no sería O (1), sino O (n).

Así no es como funciona la tabla hash, este es un tipo de búsqueda directa de fuerza bruta. En el caso de hashtable, tendría un enfoque más inteligente que utiliza la búsqueda por índice (código hash).

Answer 3

La búsqueda sigue siendo O (1) si pasa un IEqualityComparer.El conjunto hash sigue usando la misma lógica que si no pasa un IEqualityComparer; simplemente usa las implementaciones de IEqualityComparer de GetHashCode e Equals en lugar de los métodos de instancia de System.Object (o las sustituciones proporcionadas por el objeto en cuestión).

Answer 4

si tuviera que escribir un Comparer para pasar al constructor de un HashSet, cada vez que realizo una búsqueda, el código Comparer debería ejecutarse en cada clave para verificar si había una coincidencia. Esto no sería O (1), sino 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 clave para ver si coincide con la consulta?

Esta creencia es falsa. (¡A menos que el código hash proporcionado por el comparador sea el mismo para cada tecla!) El algoritmo de búsqueda ejecuta el comparador de igualdad en cada clave cuyo código hash coincide con el código hash de la consulta, módulo el número de segmentos en la tabla hash. Así es como las tablas hash obtienen O (1) tiempo de búsqueda.

¿La construcción construye internamente una tabla de búsqueda cuando los elementos se agregan a la colección?

Sí.

En general, ¿cómo puedo averiguar la información sobre la complejidad de las estructuras de datos .NET?

Lea la documentación.