Parecería que el tema de los diccionarios, las tablas hash y todo tipo de códigos hash está pintado de arriba a abajo, y cada segundo desarrollador, al ser despertado de una siesta vespertina alrededor de las 01:28 a.m., esboza rápidamente el algoritmo de equilibrio Hashtable en una hoja de papel, demostrando simultáneamente todas las propiedades en notación Big-O.
Quizás ser tan consciente del tema de nuestra conversación puede hacer un flaco favor al inculcar un falso sentido de confianza: "¡Es así de simple! ¿Qué podría salir mal aquí?"
¡Al final resultó que sí! ¿Qué se puede encontrar exactamente en un par de cuentos de viernes de programadores, justo después de un breve programa educativo sobre qué es una tabla hash?
Dado que el artículo todavía es viernes, el programa educativo será extremadamente corto y no riguroso académicamente.
Tabla hash para los más pequeños
Seguramente, muchos de ustedes acudieron a policlínicos, oficinas de vivienda, oficinas de pasaportes y otras instituciones de un mayor nivel de filantropía del antiguo modelo. Cuando tú, inclinándote hacia la ventana, dices tu apellido (dirección, número de pasaporte y número de marcas de nacimiento), la abuela diente de león del otro lado asiente, se va arrastrando los pies hacia las entrañas de la oficina y, después de un rato, trae tu papel. : ya sea una tarjeta médica o incluso un nuevo pasaporte.
La magia que no permite al empleado más rápido del mundo encontrar el documento deseado entre miles de otros no es más que una tabla hash encarnada en el mundo físico:
Con esta organización de datos, cada objeto tiene un código hash correspondiente. En el caso de una clínica, el código hash puede ser su apellido.
La tabla hash en sí es una especie de "cómoda" con cajones, cada uno de los cuales contiene objetos agrupados de una determinada manera por sus códigos hash. Uno se pregunta por qué es necesaria esta agrupación especial y por qué no utilizar los valores hash en sí mismos como inscripción en las cajas. Bueno, probablemente porque un conjunto de casillas para todos los apellidos posibles en el mundo no cabrá en todos los policlínicos.
: , . "" "", .
( IT), , .
, , - :
- - , .
, "".- - .
, , - , - , .- - , ( ).
- , - , . , .( , ) . , , - , , - .
( ) .
, EF
. -
public class Document
{
public Int32 Id {get; set;}
public String Name {get; set;}
...
}Entity Framework. - .
-:
HashSet<Document> _openDocuments;- , , :
var newDocument = new Document(); // document is created
_openDocuments.Add(newDocument); // document is open, nobody else can edit it.
context.Documents.Add(newDocument);
await context.SaveChangesAsync(); // so it's safe to write the document to the DB, test , ?
Boolean test = _openDocuments.Contains(newDocument);, false, . , - EF Document.
EF Id , ORM . , Id 0, - :
var newDocument = new Document(); // newDocument.Id == 0
_openDocuments.Add(newDocument);
context.Documents.Add(newDocument);
await context.SaveChangesAsync(); // newDocument.Id == 42, , - , , , Document :
public class Document
{
public Int32 Id {get; set;}
public String Name {get; set;}
public override int GetHashCode()
{
return Id;
}
}: - - 0, 42.
: , , , - , GetHashCode Equals . .
, GetHashCode, .
-
- , ( ) , . [20, 20], [30, 30] [20, 20], [20, 20] [30, 30]. , -:
private static IEnumerable<Size> FilterRectangles(IEnumerable<Size> rectangles)
{
HashSet<Size> result = new HashSet<Size>();
foreach (var rectangle in rectangles)
result.Add(rectangle);
return result;
}, , - O(n^2), O(n). , Computer Science, , , , .
HashSet , Size - FCL. , , - :
var a = new Size(20,20).GetHashCode(); // a == 0
var b = new Size(30,30).GetHashCode(); // b == 0, - ( , , , ), , -, .
, , : SizeF, , , :
var a = new SizeF(20,20).GetHashCode(); // a == 346948956
var b = new SizeF(30,30).GetHashCode(); // b == 346948956, a b ! 346948956...
, - , FCL, :
var a = Int64.MinValue.GetHashCode(); // a == 0
var b = Int64.MaxValue.GetHashCode(); // a == 0, .... , , .
? , :
.
- ... (. Resharper).
. - .