Comment sont gérées les collisions par hachage?
j'ai récemment appris un peu sur les valeurs de hachage, et donc aussi entendu parler du problème des collisions de hachage.
Je me suis donc demandé: comment y faire face?
E. G. Le Dictonary de Swift utilise des valeurs de hachage avec ses clés. Je suppose qu'il cherche ses valeurs via le hachage. Alors, comment le Dictionary de Swift stockerait-il alors des valeurs pour différentes clés, qui ont le même hachage?
3 réponses
fondamentalement , il y a deux principales façons de gérer les collisions de hachage - chaînage séparé , lorsque les éléments avec des codes de hachage en collision sont stockés dans une structure de données séparée , et adressage ouvert , lorsque les données de collision sont stockées dans un autre seau disponible qui a été sélectionné en utilisant un algorithme.
les deux stratégies ont de nombreuses sous-Stratégies, décrit dans Wikipedia . La stratégie exacte utilisée par une mise en œuvre particulière est, sans surprise, spécifique à la mise en œuvre, de sorte que les auteurs peuvent la modifier à tout moment pour quelque chose de plus efficace sans briser les hypothèses de leurs utilisateurs.
A ce point, la seule façon de savoir comment Swift gère les collisions serait de démonter la bibliothèque (c'est-à-dire, à moins que vous ne travailliez pour Apple, et que vous ayez accès au code source). les Curieux n'ont qu'à NSDictionary , et a déterminé qu'il utilise sonde linéaire , la variation la plus simple de la technique d'adressage ouvert.
il y a deux techniques de base:
- Resucée l'aide d'un autre premier, généralement N - 2 où N est l'original, le premier, choisie de telle sorte que les deux N et N-2 sont premiers.
- utilisez une liste par hachage.
ou les deux.
Swift dictionnaires utilise en abordant et linéaire de détection.
voici un lien vers la documentation source expliquant tout: https://github.com/apple/swift/blob/master/stdlib/public/core/HashedCollections.swift.gyb