Hashtables (dizionario ecc.) Con chiavi intere

Question

Sono stato sconcertante per alcuni giorni ... sentitevi liberi di abbattere qualsiasi mia ipotesi.

Stiamo usando un dizionario con chiavi intere. Suppongo che il valore della chiave in questo caso sia usato direttamente come hash. Questo significa (se le chiavi sono raggruppate su un piccolo intervallo) che la distribuzione dell'hash della chiave (come la stessa chiave, giusto?) Sarà in un intervallo simile e quindi una scelta sbagliata per un hashtable?

Sarebbe meglio fornire a IEqualityComparer che ha fatto qualcosa di intelligente con i numeri primi e la matematica del modulo per calcolare un hash meglio distribuito?

Answer 1

Non è usato direttamente in quanto il dizionario sarà ancora chiedere la chiave per il suo hash - ma il valore hash di un Int32è solo il valore, in modo dalla spinta della tua domanda è rilevante, sì.

Credo che il modo in cui funziona il dizionario .NET non si basa su valori di hash distribuiti uniformemente. Ci vuole hash % bucketCount dove bucketCount è sempre primo. (Questo viene dalla memoria però - potrei sbagliarmi.)

Si potrebbe ancora finire con un set di chiavi inefficiente, ovviamente se sono distanziati dal numero di bucket. Ma sarà sempre così: un tavolo hash sarà sempre O (1) per tutte le chiavi se hanno valori hash univoci e la tabella ha mantenuto un set di bucket per ogni possibile hash :) In realtà tende a non essere un problema Se ti capita di sapere che è sarà essere un problema, quindi sì, un aiuto personalizzato IEqualityComparer<T> potrebbe aiutare.

Answer 2

Supponendo che si stia utilizzando un'implementazione di tabella hash di libreria standard, è probabile che la chiave sia non l' hash, anche se la chiave è un numero intero, esattamente per la ragione che si fa notare.

Così mentre la logica relativa alle distribuzioni hash è corretta, l'ipotesi iniziale che le chiavi integer significhino che hash = keys non è probabilmente.

Se ho torto re: .NET allora oh beh; questa è più di una risposta generalizzata. :)

Answer 3

Prima di fare qualcosa di intelligente, testerei la sua velocità così com'è, e vedere se è adatto a voi. Se non lo è, prova la cosa intelligente. Ma mi aspetterei che sarebbe meglio lasciar perdere; è più importante che gli hash non entrino in collisione, e finché ciò accade, la vita andrà bene.