Il semblerait que le sujet des dictionnaires, des tables de hachage et de toutes sortes de codes de hachage soit peint de haut en bas, et chaque développeur sur deux, réveillé d'une sieste en début de soirée vers 01h28, esquisse rapidement l'algorithme d'équilibrage de Hashtable sur un morceau de papier, prouvant simultanément toutes les propriétés de notation big-O.
Peut-être qu'être si bien conscient du sujet de notre conversation peut nous rendre un mauvais service en insufflant un faux sentiment de confiance: "C'est aussi simple que ça! Qu'est-ce qui pourrait mal tourner ici?"
En fait, c'est possible! Que peut-on trouver exactement dans quelques contes du vendredi de programmeurs, juste après un bref programme éducatif sur ce qu'est une table de hachage.
Comme l'article est encore vendredi, le programme éducatif sera extrêmement court et pas rigoureux sur le plan académique.
Table de hachage pour les plus petits
Certes, bon nombre d'entre vous sont allés dans des polycliniques, des bureaux de logement, des bureaux de passeport et d'autres institutions d'un niveau accru de philanthropie de l'ancien modèle. Lorsque vous, penché vers la fenêtre, dites votre nom de famille (adresse, numéro de passeport et nombre de taches de naissance), la grand-mère de pissenlit de l'autre côté hoche la tête, se traîne dans les entrailles du bureau, puis après un court laps de temps apporte votre feuille de papier : que ce soit une carte médicale, ou même un nouveau passeport.
La magie qui ne permet pas à l'employé le plus rapide du monde de trouver le document nécessaire parmi des milliers d'autres n'est rien de plus qu'une table de hachage incarnée dans le monde physique:
Avec cette organisation des données, chaque objet a un code de hachage correspondant. Dans le cas d'une clinique, le code de hachage peut être votre nom de famille.
La table de hachage elle-même est une sorte de «commode» à tiroirs, dont chacun contient des objets regroupés d'une certaine manière par leurs codes de hachage. Pourquoi, on se demande, ce regroupement spécial est-il nécessaire, et pourquoi ne pas utiliser les valeurs de hachage elles-mêmes comme inscription sur les boîtes? Eh bien, probablement parce qu'un ensemble de cases pour tous les noms de famille possibles dans le monde ne rentrera pas dans chaque polyclinique.
: , . "" "", .
( 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).
. - .