PHast -- Perfect Hashing made fast

Informations de base

• ID de l'article: 2504.17918
• Titre: PHast -- Perfect Hashing made fast
• Auteurs: Piotr Beling (Université de Łódź, Pologne), Peter Sanders (Institut de technologie de Karlsruhe, Allemagne)
• Classification: cs.DS cs.DB cs.PF
• Date de publication: 22 octobre 2025 (version arXiv)
• Lien de l'article: https://arxiv.org/abs/2504.17918

Résumé

Les fonctions de hachage parfait attribuent des « noms » uniques à des clés arbitraires en utilisant seulement quelques bits par clé. C'est un élément essentiel dans des applications telles que les tables de hachage statiques, les bases de données ou la bioinformatique. Cet article introduit l'approche PHast qui combine les requêtes les plus rapides disponibles, une construction très rapide et une consommation d'espace raisonnable (inférieure à 2 bits par clé). PHast améliore le placement des seaux qui hache d'abord chaque clé k dans un seau, puis recherche la graine du seau s de sorte qu'une fonction de placement mappe les paires (s,k) de manière sans collision. PHast peut utiliser des fonctions de hachage à petite plage avec mappage linéaire, codage de largeur fixe des graines et construction parallèle. Ceci est réalisé en utilisant de petites tranches chevauchantes de valeurs autorisées et un mécanisme de « bumping » pour gérer l'assignation infructueuse de graines. Une variante appelée PHast+ utilise le placement additif, qui permet la recherche de graines en parallèle au niveau des bits, accélérant la construction d'un ordre de magnitude.

Contexte et motivation de la recherche

Définition du problème

Une fonction de hachage parfait (PHF) est une fonction injective qui mappe un ensemble de clés {k₁, ..., kₙ} vers {0, ..., m-1}. Lorsque m = n, on parle de fonction de hachage parfait minimal (MPHF). C'est un élément essentiel dans les applications telles que les bases de données, l'indexation de texte et la bioinformatique.

Motivation de la recherche

1. Défi d'optimisation multi-objectifs: La conception d'une MPHF fait face à un problème d'optimisation multi-objectifs impliquant la consommation d'espace, le temps de construction et le temps de requête
2. Limite théorique inférieure: La limite théorique inférieure d'une MPHF est log₂ e ≈ 1,44 bits par clé
3. Besoins pratiques: En pratique, les PHF sont couramment utilisées pour accélérer les structures de données statiques, ce qui rend les requêtes rapides essentielles

Limitations des méthodes existantes

1. Méthodes de placement de seaux: CHD, FCH, PTHash, PHOBIC, etc. nécessitent des fonctions d'allocation de seaux non linéaires ou un codage de graines de longueur variable, affectant la vitesse des requêtes
2. Méthodes de division récursive: Bien que très efficaces en espace, elles ont des temps de requête plus lents et nécessitent le décodage d'informations de navigation de longueur variable
3. Méthodes d'empreinte digitale: Nécessitent au moins e bits par clé et les requêtes nécessitent des opérations de rang sur des vecteurs de bits
4. Surcharge de construction parallèle: Les constructions parallèles existantes nécessitent des étapes de requête supplémentaires pour récupérer les valeurs de décalage

Contributions principales

1. Mappage linéaire des seaux: Évite l'allocation non linéaire des seaux grâce au mappage linéaire vers de petites tranches chevauchantes, permettant une construction multi-thread cache-friendly
2. Mécanisme de bumping: Permet l'utilisation de fonctions de hachage à petite plage et de codage de graines de largeur fixe, évitant les recherches locales complexes
3. Assignation heuristique de graines: Réduit la consommation d'espace en sélectionnant les graines qui occupent le moins de valeurs de fonction
4. Variante PHast+: Utilise une fonction de placement additif pour permettre la recherche de graines en parallèle au niveau des bits, accélérant la construction d'un ordre de magnitude
5. Évaluation expérimentale complète: Comparaison détaillée des performances avec les méthodes existantes

Explication détaillée de la méthode

Définition de la tâche

Étant donné un ensemble de n clés, construire une fonction de hachage parfait f telle que:

• f soit injective (sans collision)
• Le temps de requête soit aussi rapide que possible
• Le temps de construction soit raisonnable
• La consommation d'espace soit faible (objectif < 2 bits par clé)

Architecture de l'algorithme principal

Fonction Map-or-Bump

PHast est basé sur la méthode « map-or-bump », qui mappe n clés vers {0, 1, ..., m-1}:

f(k) = {
  ⌊αh(k)⌋ + p(s, h(k))  si s > 0
  fallback_for_bumped(k)  sinon
}

Où:

• h(k) est une fonction de hachage u-bit (u = 64)
• s = seeds⌊βh(k)⌋ est la graine
• α, β sont des facteurs d'échelle
• p(s, h(k)) est la fonction de placement

Composants techniques clés

1. Allocation linéaire des seaux:
   • Indice du seau: ⌊B/2ᵘ · cᵢ⌋
   • Valeur de début de tranche: ⌊(m-L+1)/2ᵘ · cᵢ⌋
   • Valeur de sortie: ⌊(m-L+1)/2ᵘ · cᵢ⌋ + p(s, cᵢ)
2. Assignation de graines par fenêtre:
   • Utilise une fenêtre glissante de taille W = 256
   • Gestion des seaux non ensemencés par file de priorité
   • Fonction de priorité: ℓ(s) - 1024b (s est la taille du seau, b est l'indice du seau)
3. Mécanisme de bumping:
   • Les seaux pour lesquels aucune graine ne peut être trouvée sont marqués comme « bumped » (valeur de graine = 0)
   • Environ 1% des seaux sont « bumped », avec un impact minimal sur le temps de requête attendu

Optimisation PHast+

PHast+ utilise une fonction de placement additif pour une construction rapide:

p(s, c) = c mod L + s - 1        // Formule 3.2
p(s, c) = (c + δs) mod L         // Formule 3.3

Recherche de graines en parallèle au niveau des bits:

• Test simultané de 64 graines consécutives pour la faisabilité
• Détection rapide des collisions par opérations bit à bit
• Accélération de la construction d'environ 10 fois

Construction parallèle

1. Parallélisation sans communication:
   • Le tableau de graines est divisé en t blocs et t-1 espaces
   • Les threads calculent en parallèle les graines dans les blocs
   • Taille des espaces: ⌈LB/(m-L+1)⌉ seaux
2. Conception cache-friendly:
   • Traitement des seaux dans l'ordre des indices
   • Utilisation d'un tampon circulaire pour représenter la bitmap d'occupation
   • Modèle d'accès mémoire séquentiel

Configuration expérimentale

Environnement expérimental

• Matériel: AMD Ryzen 5600G @3.9GHz (6 cœurs 12 threads)
• Cache: 384KB/3MB/16MB L1/L2/L3
• Compilateur: Rust 1.84.1, GCC 12.2.0
• Nombre de threads: 12 threads (tests multi-thread)

Ensembles de données

• Clés entières aléatoires: 5×10⁷ et 5×10⁸ entiers 64-bit aléatoires
• Clés chaînes aléatoires: Chaînes aléatoires de longueur 10-50 octets
• Fonction de hachage: GxHash (hachage SIMD haute performance)

Méthodes de comparaison

• Placement de seaux: PTHash, PHOBIC, PtrHash
• Division récursive: SIMDRecSplit, Bipartite ShockHash
• Méthodes d'empreinte digitale: FiPS, FMPH, FMPHGO
• Récupération de fonction statique: SicHash

Métriques d'évaluation

• Consommation d'espace: bits par clé
• Temps de requête: nanosecondes par requête
• Temps de construction: nanosecondes par clé
• Accélération parallèle: performance mono-thread vs multi-thread

Résultats expérimentaux

Performance principale

Performance des requêtes (5×10⁷ clés)

• PHast: 9-22 ns/requête, espace 1,82-2,33 bits/clé
• PHast+: 10-15 ns/requête, espace 1,84-2,24 bits/clé
• PtrHash: 14-17 ns/requête, espace 2,12-2,99 bits/clé
• PTHash: 40-54 ns/requête, espace 2,11-3,19 bits/clé

Performance de construction (5×10⁷ clés, mono-thread)

• PHast+: 61-140 ns/clé (configuration la plus rapide)
• PHast: 133-5322 ns/clé (dépendant de la taille de graine)
• PtrHash: 75-192 ns/clé
• FMPH: 40-57 ns/clé (mais espace plus grand)

Accélération parallèle

• PHast: 8,5-9,6× accélération (allocation de graines hautement parallélisable)
• PHast+: 4,1-5,4× accélération
• PtrHash: 3,6-5,1× accélération

Résultats d'optimisation des paramètres

Configuration optimale (minimisation d'espace)

Expériences d'ablation

1. Sélection heuristique de graines: Après suppression, l'espace passe de 1,92 à 2,39 bits/clé
2. Taille de fenêtre: À W=1, l'espace augmente à 2,20 bits/clé, W>256 n'apporte pas d'amélioration significative
3. Limite de tranche: La suppression de la limite de tranche augmente significativement la consommation d'espace
4. Ordre de traitement des seaux: Le traitement par taille décroissante (comme CHD) entraîne une consommation d'espace plus importante

Travaux connexes

Évolution des méthodes de placement de seaux

1. CHD: Allocation linéaire de seaux mais construction lente, nécessite un codage de graines de longueur variable
2. FCH/PTHash: Allocation non linéaire simple de seaux, atténue partiellement les problèmes
3. PHOBIC: Fonction d'allocation de seaux optimale, mais requêtes plus lentes
4. PtrHash: Variante PHOBIC optimisée pour les requêtes, utilisant la recherche locale

Autres catégories de méthodes

• Méthodes d'empreinte digitale: Construction rapide mais espace plus grand, requêtes nécessitant des opérations de rang
• Division récursive: Espace proche de la limite théorique mais requêtes lentes
• Récupération de fonction statique: Nécessite un sondage multi-position complexe

Unicité de PHast

PHast évite le codage de longueur variable et la recherche locale complexe grâce au mécanisme de bumping, tout en conservant la simplicité de l'allocation linéaire de seaux.

Conclusion et discussion

Conclusions principales

1. Performance des requêtes: PHast réalise un temps de requête proche de l'optimal théorique
2. Efficacité de construction: PHast+ offre une vitesse de construction extrêmement rapide
3. Efficacité d'espace: Réalise une bonne consommation d'espace tout en maintenant des requêtes rapides
4. Compatibilité parallèle: Construction parallèle sans surcharge de requête supplémentaire

Limitations

1. Espace vs méthodes récursives: Toujours pas aussi proche de la limite théorique que les méthodes de division récursive
2. Grands ensembles de données: Pour 5×10⁸ clés, l'accès mémoire devient un goulot d'étranglement
3. Ajustement des paramètres: Nécessite de sélectionner les paramètres appropriés selon le scénario d'application

Directions futures

1. Construction en mémoire externe: Implémenter l'algorithme en mémoire externe décrit à la section 6
2. Requêtes par lot: Supporter les optimisations de requêtes par lot similaires à PtrHash
3. Accélération GPU: Explorer les possibilités de parallélisation GPU
4. Extension k-perfect: Supporter les cas où k clés peuvent être mappées à la même valeur

Évaluation approfondie

Avantages

Innovation technique

1. Philosophie de conception simplifiée: Évite les mécanismes complexes grâce au bumping, incarnant le principe « moins c'est plus »
2. Mappage linéaire: Restaure la simplicité de l'allocation linéaire de seaux tout en résolvant ses problèmes
3. Optimisation en parallèle au niveau des bits: La recherche de graines en parallèle au niveau des bits de PHast+ est une innovation d'ingénierie importante
4. Conception cache-friendly: Le traitement séquentiel et la conception du tampon circulaire considèrent les caractéristiques des CPU modernes

Suffisance expérimentale

1. Comparaison complète: Comparaison détaillée des performances couvrant toutes les principales méthodes existantes
2. Évaluation multidimensionnelle: Analyse des compromis entre espace, temps de requête et temps de construction
3. Étude des paramètres: Expériences détaillées d'ajustement des paramètres et d'ablation
4. Reproductibilité: Implémentation open-source et configuration expérimentale détaillée

Insuffisances

Limitations de la méthode

1. Surcharge d'espace: Écart d'environ 0,4 bits/clé par rapport aux méthodes récursives
2. Sensibilité aux paramètres: Nécessite d'ajuster plusieurs paramètres selon le nombre de clés et la taille de graine
3. Analyse théorique: Manque de preuve théorique rigoureuse de la complexité spatiale

Insuffisances expérimentales

1. Ensembles de données uniques: Utilise principalement des données aléatoires, manque de tests sur des données d'applications réelles
2. Hiérarchie mémoire: Analyse insuffisante de l'impact des différents niveaux de cache
3. Stabilité à long terme: Pas de test de performance d'utilisation à long terme à grande échelle

Évaluation de l'impact

Contribution académique

1. Valeur théorique: Démontre que les méthodes simples peuvent être compétitives grâce à l'optimisation d'ingénierie
2. Méthodologie: Fournit une perspective « simplifier plutôt que complexifier » pour la conception de structures de données
3. Établissement de références: Établit de nouveaux repères pour la performance des requêtes de hachage parfait

Valeur pratique

1. Application directe: Peut être utilisé dans les bases de données, moteurs de recherche et autres scénarios nécessitant des requêtes rapides
2. Référence d'ingénierie: La conception cache-friendly et la parallélisation peuvent être appliquées à d'autres structures de données
3. Contribution open-source: L'implémentation Rust fournit un outil de haute qualité à la communauté

Scénarios d'application

Applications idéales

1. Tables de hachage statiques: Scénarios où l'ensemble de clés est fixe et les requêtes sont fréquentes
2. Index de base de données: Systèmes de base de données nécessitant une recherche rapide de clés-valeurs
3. Bioinformatique: Applications telles que l'indexation de k-mer nécessitant un grand nombre de requêtes
4. Systèmes de cache: Caches mémoire nécessitant une réponse de requête extrêmement rapide

Conditions de limitation

1. Mémoire suffisante: Nécessite suffisamment de mémoire pour stocker la structure de données complète
2. Données statiques: Ne convient pas aux scénarios avec mises à jour fréquentes
3. Requêtes intensives: Convient aux applications où la fréquence des requêtes est bien supérieure à celle de la construction

Références

Travaux connexes clés

1. PHOBIC: Hermann et al. « Perfect hashing with optimized bucket sizes and interleaved coding »
2. PtrHash: Groot Koerkamp « PtrHash: Minimal Perfect Hashing at RAM Throughput »
3. PTHash: Pibiri & Trani « PTHash: Revisiting FCH minimal perfect hashing »
4. SIMDRecSplit: Bez et al. « High performance construction of RecSplit based minimal perfect hash functions »

Fondements théoriques

1. Fredman & Komlós: Limite théorique inférieure des fonctions de hachage parfait
2. Belazzougui et al.: Travaux fondateurs sur les méthodes de placement de seaux

L'article PHast démontre que dans le domaine de l'ingénierie algorithmique, grâce à une compréhension approfondie de la nature du problème et des caractéristiques du matériel moderne, les méthodes simples, après optimisation minutieuse, peuvent atteindre ou même surpasser les performances des méthodes complexes. Cela fournit un aperçu important pour la conception de structures de données: parfois, la clé pour résoudre un problème n'est pas d'ajouter de la complexité, mais de trouver la bonne direction de simplification.