Hash perfetto perfetto per n numero di chiavi sconosciute

Question

Ho due array non deviati di numeri interi senza segno a 32 bit, dimensioni N1 e N2, rispettivamente. Ogni array può contenere duplicati. Vorrei mappare ogni valore (2^32 possibili chiavi) in un punto in un byte-array di dimensioni (N1 + N2) per registrare le frequenze di ciascuna chiave. I valori chiave duplicati dovrebbero mappare sulla stessa posizione in questo array. Inoltre, la frequenza di ciascun intero non supera i 100 (motivo per cui ho scelto un byte-array per registrare la frequenza di ogni chiave per salvare lo spazio); Se la possibile frequenza massima dovesse andare al di là di questo, cambierei semplicemente l'array di byte in una serie di pantaloncini o qualcosa del genere.

Alla fine, ho bisogno di una serie di dimensioni N1 + N2 - non necessariamente tutte le voci verranno utilizzate, poiché potrebbero essere stati riscontrati duplicati - con frequenze di ciascun valore chiave unico. Lo scenario peggiore, verrà utilizzato solo un byte (ad esempio, tutti i valori in entrambi gli array sono gli stessi) Leaving ((N1 + N2) - 1) Voci non utilizzate. Scenario migliore del caso, vengono utilizzati tutti gli entrie di byte.

Da quello che ho capito, ho bisogno di trovare un minimamente perfetta funzione di hashing per mappare a conosciuto numero di sconosciuto tasti (n1 + n2; tutti vanno da 0 - 2^32) a a conosciuto Numero di punti (N1 + N2). Sono stato in grado di trovare alcuni altri post, ma entrambe le risposte hanno praticamente detto usa gperf:

È possibile fare una funzione hash perfetta minimale in questa situazione?

Funzione hash perfetta minimale

Il secondo (Funzione hash perfetta minimale) è esattamente quello che sto cercando di fare.

Piuttosto che aspettarsi il codice sorgente da una risposta (sto usando C tra l'altro), preferirei di gran lunga una spiegazione di come creare un minimamente Funzione di hashing perfetta per N-numera di eventuali interi positivi a secchi. Potrei facilmente farlo con una serie di mappature dirette da 4 GB per ogni possibile numero intero con molto spazio inutilizzato, ma preferirei provare a ridurre questa enorme inefficienza di spazio. Spero anche di non usare librerie esterne, principalmente per scopi educativi per saperne di più sull'hashing, di per sé.

Answer 1

Questo è chiaramente impossibile. Se hai N numeri, non c'è modo di trovare una funzione che li farà avere tutti a valori distinti nell'intervallo [0, n) a meno che tu non sappia quali saranno questi numeri in anticipo. Altrimenti, data tale funzione (con N <2^32, ovviamente), ci sarà almeno una coppia di numeri interi in modo tale che entrambi quegli numeri interi hanno lo stesso valore, in modo che la funzione non sia perfetta se quei numeri interi si abbiano entrambi nell'input.

Se rilassi le condizioni per consentire la creazione della funzione al volo, questo diventa possibile, ma solo in modo davvero banale e inutile. Vale a dire, una funzione hash potrebbe costruirsi mentre va registrando ogni numero che viene alimentato in esso e generando un nuovo output unico per ognuno (diciamo, contando da 0). Ma una tale funzione avrebbe bisogno di una tabella hash (o qualcosa di equivalente) come parte della sua implementazione, quindi non sarebbe certo inutile implementazione Un tavolo hash!

Answer 2

Secondo il Principio di piccione, avrai "slot di hash" occupati da più di un numero. In altre parole: numeri diversi si "hash" allo stesso valore.

Ora, mi chiedo se potresti beneficiare di un Filtro Bloom. Da Wikipedia:

Sono possibili partite false positive, ma i falsi negativi non lo sono; cioè una query restituisce "possibilmente in set" o "sicuramente non nel set".

Se qualcosa è "sicuramente" non nel set di chiavi, puoi andare avanti (la sua frequenza è una), e se eventualmente è nel set, allora lo elabora ulteriormente per accumulare la sua vera statistica.