- https://en.wikipedia.org/wiki/Hash_table
- https://en.wikipedia.org/wiki/Open_addressing
- https://en.wikipedia.org/wiki/Space-time_tradeoff
- https://hackage.haskell.org/package/base-4.3.1.0/docs/Data-HashTable.html
- https://www.haskell.org/
- https://www.geeksforgeeks.org/dsa/hash-table-data-structure/
Non cryptographic
- https://en.wikipedia.org/wiki/Non-cryptographic_hash_function
- Jenkins https://en.wikipedia.org/wiki/Jenkins_hash_function
- Fowler–Noll–Vo https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
- MurmurHash3 https://en.wikipedia.org/wiki/MurmurHash
- djb2 https://theartincode.stanis.me/008-djb2/
Cryptografic
- MD5 (already broken) https://en.wikipedia.org/wiki/MD5
- BLAKE2 https://en.wikipedia.org/wiki/BLAKE_(hash_function)
- TinyCrypt https://github.com/intel/tinycrypt
- Jenkins one-at-a-time Hash Function: -> Primeiro, criámos uma versão básica da função que funcionava apenas com Strings. -> Para tornar a função mais útil, introduzimos uma typeclass Hashable. -> A nossa primeira tentativa envolveu converter todos os tipos para uma String, mas rapidamente identificámos que isso não era o ideal. -> De seguida, começamos a usar o Data.ByteString, o que envolveu: · Ter um método toByteString em cada instance da classe Hashable · Garantir a codificação binária correta para diferentes tipos: UTF-8 para strings (para lidar com todos os caracteres) e um Int64 de tamanho fixo para inteiros (para garantir que o hash é o mesmo em qualquer computador). · Resolver um erro de tipos entre ByteStrings strict e lazy. -> Finalmente, testamos a função com caracteres únicos (“1”, “2”, etc.) e descobrimos uma fraqueza: os hashes formavam uma sequência previsível. -> Determinámos que esta é uma propriedade conhecida do algoritmo para inputs muito curtos, pois não tem dados suficientes para criar um “efeito de avalanche” completo.
- Fowler–Noll–Vo Hash Function: -> Uma parte fundamental foi a decisão de implementar a versão de 64 bits do algoritmo (usando Word64). Fizemos esta escolha porque, para qualquer aplicação moderna, é a versão superior: · Reduz drasticamente a probabilidade de colisões (18 quintiliões de hashes possíveis vs. 4 mil milhões na versão de 32 bits). · Não tem qualquer penalidade de desempenho em processadores de 64 bits modernos. -> Introduzimos a lógica matemática central da FNV-1a, que é diferente da Jenkins: um loop que aplica a operação (hash XOR byte) * primo. Para que isto funcionasse, definimos os “números mágicos” padrão para a versão de 64 bits: · offsetBasis: Um valor inicial não-zero para garantir que mesmo inputs vazios ou de zeros produzam um bom hash. · fnvPrime: Um número primo cuidadosamente escolhido pelos criadores do algoritmo para garantir a máxima dispersão dos bits (“efeito de avalanche”). -> Tal como na função Jenkins, notámos que a conversão final de um Word64 (sem sinal) para um Int (com sinal) podia resultar em números negativos. Por isso, usamos a funçao abs -> Ao contrário da função Jenkins, a FNV-1a não exibe a mesma fraqueza para inputs muito curtos. A sua abordagem matemática, que combina XOR com multiplicação por um número primo em cada passo, cria um “efeito de avalanche” mais forte e imediato, mesmo com apenas um ou dois bytes de entrada.
- Comparação de performance de hashing simples, como divisão, com funções de hash mais avançadas, e suas características e propriedades.
- concurrent hashtables
- hashtable properties: https://en.wikipedia.org/wiki/Discrete_uniform_distribution https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test#Discrete_uniform_distribution
- Cuckoo hashing https://en.wikipedia.org/wiki/Cuckoo_hashing