Cosa posso dedurre dalla mappa di Hilbert?

... is a technique for 1D <=> 2D transformation ...

Sì, l'ordinale 1D è il valore hash e viene trasformato in una coordinata 2D nell'immagine

... which preserves locality of the points.

Quindi i valori hash adiacenti saranno punti adiacenti nell'immagine. Ciò significa che se alcuni intervalli di valori hash vengono usati raramente e altri vengono utilizzati in modo denso, saranno visibili nell'output. In altre parole, visualizza uniformità dei valori hash sul loro intervallo di output.

Non ti dice nulla sulle collisioni. Il colore indica il raggruppamento spaziale degli intervalli di valori hash, ma è più decorativo dell'IMO utile.

Considera alcuni esempi di funzioni hash errate:

1. se qualche funzione hash mai imposta il bit superiore del suo valore di output, metà di entrambi i tipi di grafico sarà bianco (la mappa lineare avrà la metà superiore tutta bianca e la mappa Hilbert avere molti grandi quadrati bianchi)
2. se alcune funzioni di hash non impostano mai il bit bottom , metà del grafico sarà ancora bianco, ma in questo caso la mappa lineare mostrerà linee verticali bianche e chiare, e la mappa di Hilbert non essere così utile
3. se vi sono intervalli di valori consecutivi di valori consecutivi che non sono mai impostati, potrebbero essere più facili da individuare come grani bianchi quadrati nella mappa di Hilbert, piuttosto che come linee orizzontali bianche corte sparse sulla mappa lineare.

Modifica: l'immagine originale collegata per facile lettura.

Entrambe le visualizzazioni mappano da 1D a 2D. La visualizzazione "lineare" è simile alla mappatura 1-9 per le posizioni

1 2 3
4 5 6
7 8 9

Mentre la mappa di Hilbert è più simile a

1 2 9
4 3 8
5 6 7

I colori nell'immagine sono solo un gradiente dal rosso al minimo (1) al viola al massimo (9). Quindi nel primo caso si ottiene un gradiente uniforme dall'alto al basso, nel secondo si otterrebbero bordi chiari, ad es. dove 2 bordi 9.

Ci sono due "mancanze" nell'approccio lineare: in primo luogo, la "larghezza" di 3 è arbitraria e potrebbe non avere nulla a che fare con l'algoritmo di hashing. Questo può rendere più difficile vedere i problemi nell'output. Ad esempio, supponiamo che questo hash non emetta mai 2, 5 o 8

1   3
4   6
7   9

Questo è un piccolo, stupido esempio, ma avere un grande gap verticale come quello sarebbe un problema per un vero e proprio hash. Ma, se usi una larghezza di 2 ...

1
3 4
  6
7
9

Ora sembra davvero "casuale". Il secondo difetto è il grande divario che si verifica tra numeri consecutivi quando si passa a una nuova riga, ad es. 3 e 4, 6 e 7. Ciò può anche rendere difficile la visualizzazione dei problemi.

Una mappa di Hilbert evita entrambe le imperfezioni: i numeri consecutivi sono sempre adiacenti e non ha una "larghezza" reale poiché si aggira su se stessa per riempire lo spazio.

Ma penso che l'autore lo includa solo per un po 'di divertimento (nota che lo usa solo per un esempio). Semmai la mappa di Hilbert rende più difficile vedere i difetti nell'hash perché l'occhio umano non può facilmente distinguere il piccolo percorso di torsione nell'immagine. La larghezza della mappa "lineare" è in realtà un vantaggio , non una lacuna. Dà valori che sono multipli una relazione geometrica: cadono tutti lungo linee rette nell'immagine. È vero che visualizzare l'immagine alla larghezza "sbagliata" può renderlo difficile da vedere, ma in genere se provi qualche larghezza diversa i difetti diventeranno immediatamente evidenti. Non credo che la mappa di Hilbert avrebbe questa proprietà.

L'autore della risposta collegata sta usando due diverse visualizzazioni della distribuzione dei valori hash, come un test "mi sembra casuale". Essere indistinguibile da una (buona) uniforme (P) RNG è una caratteristica desiderabile negli usi alcuni delle funzioni di hash. I pattern nelle immagini per hashing "zip code" sono i tipi di pattern, che per un PRNG indicano una distribuzione "cattiva".

Non fornisce informazioni utili sulle collisioni. Dovresti contare i pixel, e non mostrerebbe dove era la collisione. La tabella sulle collisioni è una fonte molto migliore per questo.

Il colore è solo una mappatura del valore hash - > tonalità. Potrebbe essere un'immagine monocromatica e trasmettere le stesse informazioni.