Ricerca di hash monotonicamente crescente (intero)

Senza cercare di entrare nelle dimostrazioni, direi che una tale bestia non esiste per i numeri interi generici. Il tuo problema alla fine si ridurrebbe a trovare una funzione hash H con x > y → H (x) > H (y); con il vincolo che l'output di H è un insieme finito e assumendo che xεℕ (o in un altro set S con | S | > | image (H) |), ci sarebbe necessariamente x₁ > x₂εℕ con H (Xl) ≤H (x₂).

Se, tuttavia, hai entrambe le variabili da un insieme finito, ad es. Rappresentazioni di interi a N bit r (x). potresti banalmente definire H (x₁, x₂) = r (x₁) || r (x₂) e soddisfare i tuoi requisiti.

Se Integer è limitato, banalmente impossibile a causa del principio del pigeonhole. Se non lo è, banalmente impossibile perché Hash(2,0) - Hash(1,0) è finito, eppure un numero infinito di valori hash Hash(1,y) deve stare nel mezzo.

Stai cercando l'hashing di coordinate? L'equazione normale è:

hash = y * width + x (nel tuo caso sarebbe probabilmente x * height + y)

Quindi se la tua dimensione di hash è un 32 bit con segno allora sqrt (2.147.483.647) darebbe il valore di larghezza, in questo caso 46340. Questo definisce sono min come (-46340, -46340). Il massimo sarebbe (46340, 46340).

-46340 * 46340 + -46340 = -2,147,441,940 e int minimo firmato a 32 bit è -2,147,483,648 46340 * 46340 + 46340 = 2.147.441.940 e il valore massimo con segno int a 32 bit è 2147483648

Per ampi intervalli di x e y, in genere puoi usare solo un 64 bit.

Se conosci operatori bit a bit, puoi semplicemente assegnare bit bassi e alti a xey. Quindi in un numero a 64 bit memorizzerete la x nella top 32 ey nella parte inferiore 32. Questo genererà un hash che segue le vostre regole.

Alcuni punti suggeriscono che la "funzione hash" non è il termine giusto per ciò che vuoi, o che ciò che vuoi non esiste.

Primo, una funzione non può essere strettamente crescente a meno che non sia 1-1, e tipicamente con "hash" intendiamo ottenere un risultato che è più piccolo dell'input (di solito di molti ordini di grandezza). In questo contesto, il massimo che potresti chiedere è una funzione che aumenta debolmente, ad esempio, conserva un byte di alto livello o qualcosa di simile.

In secondo luogo, la domanda collegata mi suggerisce che ciò che è voluto è rendere i risultati uniformemente distribuiti (almeno approssimativamente) preservando l'ordine (monotonicità). È possibile ottenere questo risultato per un set di dati specifico (ordinare ed enumerare), ma definire una funzione master per fare ciò per dati di input arbitrari ("interi generici" come dice Nicos) è impossibile.

In terzo luogo, una funzione monotona sarebbe inutile come una funzione hash crittografica perché le funzioni monotone sono facili da invertire (sconfiggere il scopo di rendere difficile la generazione di un messaggio con un determinato hash).