Hashing Adaptativo no SBCL: Tornando as Tabelas Hash Mais Rápidas e Robus

Uma palestra no ELS de 2024 focou em hashing adaptativo, com o objetivo de tornar as tabelas hash de uso geral mais rápidas e robustas. A teoria tradicional de tabelas hash se preocupa principalmente com custos assintóticos de pior caso, negligenciando o impacto de fatores constantes no desempenho do mundo real. Esta pesquisa introduz uma abordagem adaptativa online, ajustando a função hash com base na distribuição real da chave para reduzir colisões e melhorar a utilização do cache. Experimentos demonstram melhorias significativas na redução de comparações esperadas e na aceleração das operações PUT, particularmente com distribuições de chaves específicas. As tabelas hash internas do SBCL agora empregam essa técnica, alternando dinamicamente funções hash (incluindo pesquisa linear, hash de deslocamento de bits e MurmurHash) com base em contagens de colisões e tamanho da tabela hash. Para chaves compostas como strings e listas, uma estratégia de truncamento é usada, ajustando dinamicamente o comprimento de truncamento quando ocorrem muitas colisões. Essa melhoria aprimora a velocidade da tabela hash do SBCL em casos comuns e a robustez em outros.