In che modo hash 4 si raddoppia in un size_t?

Question

In che modo hash 4 si raddoppia in un size_t?

#1 da (3 voti)
#2 da (2 voti)

-3

Ho delle caselle di delimitazione sul tipo di chiave.

Box {
  double mins[2];
  double maxs[2];
}

E voglio avere Box come tipo di chiave nel linguaggio di programmazione D, quindi devo implementare:

size_t toHash() const @safe pure nothrow {
   size_t hash;
   for(size_t k=0; k < 2; k++) {
       // do something here
   }
   return hash;
}

Dovrei avere una lista collegata sull'output dell'array associativo e cercare nell'elenco di una collisione? Dovrei trovare qualche limite ragionevole del doppio che è nella mia applicazione, quindi trovare una formula spostando?

Non sai cosa fare qui.

object-oriented collections design-patterns d hashing

posta EnjoysMath 11.02.2016 - 16:26

fonte

2 risposte

3

L'hashing ha senso solo in combinazione con un confronto di uguaglianza. Ma se i tipi contengono valori doppi come nell'esempio, qualsiasi paragone di uguaglianza ragionevole dovrebbe funzionare con un "epsilon", qualcosa come

   bool Equal(Box b1,Box b2, double epsilon)
   {
      return fabs(b1.mins[0]-b2.mins[0])<epsilon &&
             fabs(b1.mins[1]-b2.mins[1])<epsilon &&
             fabs(b1.maxs[0]-b2.maxs[0])<epsilon &&
             fabs(b1.maxs[1]-b2.maxs[1])<epsilon;
   }

Tuttavia, questo rende l'hashing inutile, perché ora le caselle "uguali" secondo questo confronto non sono garantite per produrre lo stesso codice hash se sono "quasi" uguali (per qualsiasi funzione hash sensibile, a patto che non implementa banalmente la funzione di hashing restituendo sempre 0).

L'hashing di qualcosa come le doppie coordinate ha solo senso quando puoi mapparle su un intervallo discreto, il che significa che hai una sorta di mappatura da double a int . E non appena hai coordinate intere, dovrebbe essere facile creare un valore hash per loro (ad esempio, come mostrato qui ).

risposta data 11.02.2016 - 17:35

fonte

Leggi altre domande sui tag object-oriented collections design-patterns d hashing

È un modo efficace per rimuovere tutte le righe da un file che non contiene una stringa certa? [chiuso] Che cos'è un diagramma appropriato per descrivere l'architettura del software

score 2 · Accepted Answer

Se puoi generare un hash univoco garantito, fallo. Tuttavia, ciò significa che le coordinate della casella devono essere relativamente piccole (ad esempio se una casella può essere compresa tra 0 e 1, con incrementi di 0,1, allora sono 10 passi per ogni coordinata, rendendo possibili 10 ^ 4 valori univoci, assumendo 2 caselle può sovrapporsi)

Nella maggior parte dei casi non sarai in grado di garantire un hash unico, quindi genera quello che puoi e capisci che i tuoi hash potrebbero collidere. Se questo è il caso, dipende da cosa stai cercando di fare - penso che vorrai memorizzare questi hash clashing in una lista di raccolte simili e quando leggi un box, esegui iterate su tutti gli scontri per trovare quello che vuoi. Il punto è che puoi saltare rapidamente quasi tutte le caselle non necessarie per arrivare a quello che volevi.

SO ha una buona spiegazione di quali sono le tabelle hash e in che modo vengono utilizzate.

Nel tuo caso, potresti voler considerare un singolo angolo per identificare le tue scatole se non si sovrappongono, la dimensione della scatola è irrilevante in tal caso. Qualunque cosa tu faccia, prova a calcolare l'hash il più velocemente possibile in quanto verrà calcolato spesso.