Best ways to handle failure to find a collision-free hash

Aperta
#6 4 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Ferma
Stack tecnologico
go
Ambito
backend

Direzione di ricerca

Inizia tracciando la ricerca senza collisioni del builder e il comportamento di Get, concentrandoti sugli input FNV come c e c2 e sul seed casuale basato sul tempo descritto nell’issue. Esamina quindi il comportamento e i test del package esistente, poi definisci se i tentativi ripetuti, la possibilità di consentire collisioni o il fallback rientrano in questa library; il lavoro è completato quando sono disponibili una decisione documentata e il relativo ambito concordato.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

(I apologize if this is out of scope for this library, and for my relatively shallow understanding of MPHs.)

Using the FNV hash func and even some simple inputs (e.g., keys c and c2, where c is any character), the builder often fails to find a collision-free hash. This is not a limitation of this particular project; implementations of the same algorithm in other languages also frequently fail on this class of inputs. (I say "often" and "frequently" because the random seed is the current time, and sometimes it succeeds.)

Is there a generally accepted solution for handling this occurrence, such as retrying the generation with a different random seed? Or allowing a small number of collisions (and iterating over the collisions in Get) if the cardinality is small? (It might make the most sense to add support for these things in external code, not in this core mph lib. But I notice that gperf supports producing imperfect hashes, so there is some precedent for including them.)

So, basically, how do other people handle the failure to find a collision-free hash in their own code? (Just fall back to a map or another hashing scheme?)

Lingua principale
Go
Stelle
191
Fork
21
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di alecthomas/mph

Tutte le issue di alecthomas/mph

Issue simili

Altre issue su Go

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.