Definição formal de função hash

Question

Eu estava lendo através dos clássicos CLRs com a intenção de revisar a teoria das tabelas de hash, mais especificamente a definição da função de hash Eu só queria uma referência à citação.

Não consigo encontrar uma definição formal dada, mas acho que é justo dizer uma função hash (não univerisal) $ h $ é um mapa surpresa de um conjunto de chaves $ K $ para um subconjunto de inteiros $ u $ , para cada recipiente de matemática $ k \ em k $ definimos $ h (k) $ para ser o valor hash de $ K $ . A partir da explicação dada em Clrs, parece que esta restrição à $ u $ (ser inteiros) pode ser muito restritiva, no entanto, já que eu acho que a definição tem que mostrar alguns aspectos práticos Eu acho que isso pode estar correto.

Você pode me dar: 1. Um papel / livro com uma definição formal 2. Confirme se minha definição estiver correta?

Obrigado

Answer 1

Uma função HASH é usada para mapear um conjunto de chaves para um sub-fluxo dos inteiros (é usado como um índice em uma matriz, no final).Por isso, deve ser (assumindo arrays baseados em zero, como em c), $ h \ colon \ mathcal {u} \ a [0, m - 1] $ se $ \ mathcal {u} $ é o universo das teclas.