Parece que o tópico de dicionários, tabelas de hash e todos os tipos de códigos de hash são pintados de cima a baixo, e a cada segundo desenvolvedor, sendo acordado de um cochilo no início da noite por volta de 01h28, rapidamente esboça o algoritmo de balanceamento de Hashtable em um pedaço de papel, ao longo do caminho provando todas as propriedades em notação big-O.
Talvez estar tão ciente do assunto de nossa conversa possa ser um desserviço ao incutir uma falsa sensação de confiança: "É tão simples!
No fim das contas, pode! O que exatamente pode - em alguns contos de sexta-feira do programador, logo após um curto programa educacional sobre o que é uma tabela hash.
Como o artigo ainda é sexta-feira, o programa educacional será extremamente curto e academicamente pouco rigoroso.
Mesa de hash para os mais pequenos
Certamente, muitos de vocês foram para policlínicas, escritórios de habitação, escritórios de passaportes e outras instituições de um nível elevado de filantropia do modelo antigo. Quando você, inclinando-se para a janela, diga seu sobrenome (endereço, número do passaporte e número de marcas de nascença), a avó dente-de-leão do outro lado acena com a cabeça, sai arrastando os pés para as entranhas do escritório e, em seguida, traz seu pedaço de papel : seja um cartão médico, ou mesmo um novo passaporte.
A magia que não permite que o funcionário mais rápido do mundo encontre o documento necessário entre milhares de outros nada mais é do que uma tabela hash incorporada no mundo físico:
Com essa organização de dados, cada objeto possui um código hash correspondente. No caso de uma clínica, o código hash pode ser seu sobrenome.
A própria tabela hash é uma espécie de "cômoda" com gavetas, cada uma das quais contém objetos agrupados de uma determinada maneira por seus códigos hash. Por que, alguém se pergunta, esse agrupamento especial é necessário e por que não usar os próprios valores hash como a inscrição nas caixas? Bem, provavelmente porque um conjunto de caixas para todos os sobrenomes possíveis no mundo não caberá em todas as policlínicas.
: , . "" "", .
( 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).
. - .