ZedmeeHash: una nuova funzione di hash 32/64

Senza celare un pizzico di orgoglio, non temo di affermare di appartenere alla categoria degli informatici pionieri. Una tale affermazione in una disciplina in continuo e velocissimo cambiamento equivale praticamente a riconoscere il proprio anacronismo, ad auto celebrare la propria obsolescenza, insomma a definirsi dinosauri senza però che tutto ciò scalfisca la propria autostima; anzi esattamente il contrario. 

Ho iniziato a studiare informatica alle superiori nel 1981 esattamente lo stesso anno di uscita del primo PC IBM, la macchina con annesso sistema operativo che rappresentano una pietra miliare nella storia di questa disciplina. Ricordo bene che a stessa parola “informatica” era ai più sconosciuta e che per fare capire l’indirizzo scolastico dovevo specificare di studiare la “programmazione dei calcolatori elettronici” 

Prima della mia generazione non esistevano informatici, ma coloro che si occupavano di questa disciplina sia in ambito scientifico che professionale erano perlopiù matematici, fisici o ingegneri; grazie alle loro ricerche e al lavoro e ai loro sforzi al limite dell'eroismo siamo arrivati a questo punto, dove "l'informatica" è praticamente entrata in ogni aspetto della nostra esistenza, e non c'è praticamente macchina o strumento costruito dall'uomo che non dipenda da un microprocessore e da un software. 

Quindi la nostra vita è assolutamente dipendente da una miriade di microprocessori e da un’infinità di programmi. Gli uomini che hanno gettato le basi di questa civiltà cibernetica sono i nostri padri fondatori; fra questi cito Donald Knuth, Edsger Dijkstra e Niklaus Wirth, ma ovviamente sono moltissimi gli scienziati e o ricercatori che hanno contribuito alla nascita di questa disciplina; oggi gran parte di loro sono molto anziani o già deceduti.

Io non ho fatto tempo a vedere e usare i primi strumenti, un mix di meccanica e semplice elettronica, come le schede perforate, le memorie a nuclei magnetici, o i dischi a tamburo e tutte le paleo tecnologie informatiche utilizzate nei tempi eroici dai padri fondatori, e di fronte al marasma delle app, degli aggiornamenti, smartphone, tablet, pc, smartTV, password, pin, otp e altre diavolerie sono assolutamente certo che sia loro, i padri fondatori, sia gli informatici pionieri come me, mantengano un atteggiamento distaccato se non apertamente dissociato e guardino con un certo sospetto queste cose, almeno nella maggior parte di essi. Io, come informatico tout court, sono stato e sempre rimarrò attratto dai fondamenti di questa disciplina per come l'ho appresa a partire dagli anni scolastici e universitari. 

Tutto giocava attorno a due fattori limitanti e impattanti che allora avevano i computer: poca o pochissima memoria e velocità di esecuzione molto ma molto bassa. E quando dico poca memoria parlo di qualche decina di KB (il VIC20, uno dei primi Home Computer acquistabili dalle famiglie ne aveva 5; il Commodor 64, arci noto, non più di 64); la lentezza delle allora CPU potrebbe essere paragonata alla velocità di una lumaca confrontata con la velocità di un cavallo di quelle attuali. 

Pertanto, l'abilità era di riuscire a fare programmi che potessero eseguire dei "compiti utili" sottostando alle stringenti limitazioni imposti dall'hardware e dai semplici sistemi operativi (quando c'erano); per esempio si studiava il modo migliore di memorizzare i dati usando il minimo indispensabile di memoria, ma anche di cercarli nel modo più veloce possibile. Quindi sulle strutture dati, sugli algoritmi di ordinamento o di ricerca sono stati fatti una quantità enorme di studi e lavori, iniziati dagli informatici della generazione "eroica" e proseguiti da tutti gli altri per decine e decine di anni. 

Ovviamente come in altri contesti dove si verifica un interesse generale convergente, tutto quello che poteva essere "scoperto" o "inventato" è stato fatto e anche se a rigor di logica questa affermazione non può essere dimostrata almeno in assoluto, ma solo ragionevolmente accettata; quello che oggi è ancora possibile fare sono solo piccoli aggiustamenti o miglioramenti di cose già esistenti.

Ecco che di tanto in tanto emerge qualche annuncio di piccole "invenzioni", tipo una nuova strategia di scelta del pivot nel caso del quicksort o cose simili, ma è un po' come per le esplorazioni geografiche, dove non c’è più possibilità per nuove scoperte o imprese, ma al massimo rimangono inesplorati e inviolati remoti angoli della Terra, tipo le cime di montagne minori da qualche parte in Tibet o della cordigliera Andina. Tuttavia, come ho avuto modo di dire, personalmente sono ancora nostalgicamente attratto dai vecchi argomenti, ovvero i linguaggi di programmazione, le strutture dati, gli algoritmi di compressione e ricerca dati, gli ordinamenti. 

Fra questi argomenti, uno in particolare ha focalizzato la mia attenzione negli ultimi tempi. Si tratta delle funzioni di hashing, ovvero funzioni che in un certo senso fanno qualcosa di contrario all'ordinamento dei dati. Sembrerebbe poco utile disporre di una funzionalità che "disordina" i dati, in quanto è noto che disordinare richiede meno tempo (e intelligenza) che ordinare, e che il disordine è generalmente meno utile (se non assolutamente da evitare) rispetto all'ordine; tuttavia queste funzioni stanno alla base di due applicazioni fondamentali all'informatica: le tabelle di hash che sono una particolare forma di struttura dati e la crittografia dei dati. 

Ricordo che nel famoso libro di Niklaus Wirth "Algorithms + Data Structures = Programs" del 1976, una vera bibbia per gli studenti degli anni successivi alla pubblicazione, alla fine del capitolo dedicato alle strutture dati, dopo la descrizione dei complicati alberi più o meno bilanciati, presentava le tabelle di hash evidenziandone la semplicità ed ne elogiava le incredibili migliori prestazioni rispetto alle strutture più complesse, a fronte di alcuni limiti, che però nel tempo sono stati molto ridotti con l'utilizzo di tecniche avanzate. 

L'altra grande applicazione delle funzioni di hash è la crittografia, un argomento semi sconosciuto fino alla fine degli anni 80 che poi però ha aumentato sempre più di importanza divenendo ai giorni nostri un tema fondamentale con l'avvento delle nuove tecnologie e il problema della protezione dei dati personali da furti e dall'imperante cyber crimine diventato oramai una vera piaga della nostra società e fonte di grandi preoccupazioni su tutti i piani, dalla grande azienda al singolo cittadino. 

Sembra paradossale, in quanto apparentemente va a contraddire il senso comune, ma in una macchina deterministica quale è un calcolatore elettronico è più difficile disordinare che ordinare i dati; questo se non altro perché c'è un solo modo in cui dati possono essere ordinati (o meglio due: crescenti o decrescenti) mentre ci sono un'infinità di modi in cui possono stare disordinati e ogni modo differisce dall'altro; pertanto il tema delle funzioni di hash è ancora un tema che di tanto in tanto fornisce delle novità. 

La cosa che ha destato il mio interesse in questi ultimi tempi, sono le funzioni di hash non-crittografiche, quelle più "vecchie" rispetto alle altre, ma comunque un tema che sembra essere ancora relativamente vivo e promette qualche piccola novità. Infatti, negli ultimi 10 - 15 anni sono state progettate e pubblicate nuove funzioni, fra le quali la MurmurHash, CityHash, xxHash che sembrano le migliori e che sono state rilasciate sia nella versione 32 che nelle versione 64 o maggiore; qualcun'altra nuova funzione invece è stata rilasciata solo a partire dalla 64 bit. 

La "categoria" o "dimensione" di una funzione di hash è data dalla lunghezza del risultato, ovvero di quanti bit è composto ossia 16 o 32 o 64 o 128... bit; di solito si usano le potenze di 2, ma non è una scelta obbligata, si potrebbe ritornare un numero composto da 37 bit o 99, ma si preferisce utilizzare una potenza di 2 in quanto è una dimensione intrinseca dell'architettura dei computer moderni. L'input della funzione invece è una sequenza arbitrariamente lunga di byte (ovvero numeri tra 0 e 255); il risultato prodotto deve essere un numero che sembra non aver nulla a che fare con l'input, ovvero senza alcun apparente legame; input molto simili, magari che differiscono di un solo bit devono produrre output molto ma molto differenti. Questa caratteristica definisce la qualità di una funzione di hash. 

L'altro fattore importante, anche se viene dopo quello qualitativo, è la velocità di esecuzione; ovviamente più è veloce nel produrre il risultato, meglio è. Tuttavia, esistono altri fattori che determinano la “bontà” di una funzione, ovvero la sua "portabilità" e la sua "eleganza"; per portabilità intendo la possibilità che sia implementata in sistemi differenti, ovvero che non dipenda da architetture specifiche (leggi sistemi operativi o cpu) e che si possa scrivere nativamente nei principali linguaggi senza ricorrere a trucchetti (librerie). Per eleganza intendo che il suo codice sia relativamente semplice, corto e non contorto. 

Senza aver alcuna pretesa o speranza di riuscire a scrivere una funzione che potesse anche solo avvicinarsi a quelle che ho citato, negli ultimi tempi mi sono dedicato allo sviluppo di una mia personale funzione, quasi per gioco, giusto per mantenere il cervello in allenamento; tuttavia dopo tante verifiche, ipotesi, versioni e un’infinità di piccoli aggiustamenti mi sono accorto di aver sviluppato una funzione che non solo ottiene risultati spesso migliori di quelle note e praticamente mai peggiori, ma risulta anche esteticamente elegante, semplice e portabile (fattori ritenuti ai più secondari, ma che invece personalmente attribuisco molta importanza).

Dopo aver datole il nome ufficiale di ZedmeeHash, ho deciso di pubblicare il lavoro e di rendere il codice sorgente pubblico in modo che se mai ci sarà qualcuno che vorrà utilizzare questa funzione lo possa fare liberamente. Il repository dove è pubblicata è il seguente: https://github.com/matteo65/ZedmeeHash