Hashing di una tupla di interi con valore massimo

Question

Hashing di una tupla di interi con valore massimo

#1 da (2 voti)

1

Sto prendendo in considerazione una funzione di hash per una somma di tupla e valori massimi, ad esempio (3 ,2, 5 ) - dove ogni elemento della tupla ha un valore massimo N .

Il mio piano è di trattare gli elementi della tupla come le cifre di un numero in base N , in modo che nel caso banale di N = 10 la tupla (3 ,2, 5 ) hash a 325 o 213 se N = 8 .

(1) Questa tecnica di hashing è imperfetta e (2) In caso contrario, ha un nome e (3) Esistono modi migliori per cancellare una tupla di numeri interi.

hashing

posta Olumide 07.06.2016 - 23:39

fonte

1 risposta

Leggi altre domande sui tag hashing

Servizi REST con un'applicazione locale o remota Applicazione mobile basata su API di test parallelo

score 2 · Accepted Answer

Mentre questo funzionerà e in alcune situazioni darà buoni risultati, ci sono due pericoli con questo approccio:

considerando una tupla con valori M in cui la portata ha N massimo, il calcolo del valore di hash sarà overflow se M * N > il tuo limite di tipo intero. Se hai N o M grandi questo è un problema che puoi correggere usando un moltiplicatore più piccolo. Questo, tuttavia, peggiorerà per N e M più piccoli, quindi dovresti scegliere il tuo approccio a seconda di quanto probabile sia l'overflow.
se si utilizzano i codici hash per l'archiviazione in una tabella hash, si noti che il codice hash verrà preso come modulo della tabella. Ciò significa che se il tuo N è un fattore della dimensione della tabella e i tuoi singoli valori non sono equamente distribuiti, è più probabile che tu veda le collisioni. Garantire che il moltiplicatore sia coprime con le dimensioni della tabella è l'approccio migliore; i modi semplici per farlo sono scegliere una dimensione del tavolo principale o un moltiplicatore primo I nella funzione hash. Poiché la maggior parte delle moderne implementazioni di hah table scelgono automaticamente le dimensioni che non sono in genere prime, di solito dovresti usare i primi nella tua funzione hash. Un approccio sarebbe avere una lista di numeri primi e scegliere il più piccolo > = N. Penso che questo risolva il problema.