Este repositório implementa um hashmap genérico com sondagem quadrática. Também há supporte para sondagem linar utilizando a flag de compilador LINEAR_PROBING=1.
Para compilar este programa, serão necessários o g++ (C++ 17) e o make.
Dependendo de seu sistema, pode ser possível instalá-los com sudo apt install build-essential.
Para o desenvolvimento é recomendado o clang-format. Você pode instalá-lo com sudo apt install clang-format
Também é recomendada a extensão Clang-Format para VSCode.
- Instale os requisitos
- Clone este repositório
- Compilando e executando:
makepara compilar e executar com parâmetros padrãomake LINEAR_PROBING=1para compilar e executar com sondagem linear (invés de quadrática)make hashmappara compilarmake runpara executar com parâmetros padrãomake cleanpara deletar arquivos gerados
Note que o algoritmo de sondagem é definido em tempo de compilação, então lembre-se de executar make clean entre compilações com flags diferentes.
Os experimentos executados estão descritos no script executável benchmark.sh.
O código será compilado para cada tipo de sondagem e serão gerados novos conjuntos de dados na pasta inputs/.
Após, o script irá executar o programa sobre os conjuntos de dados gerados, salvando estatísticas em outputs/.
Essas estatísticas podem ser lidas com o notebook Jupyter visualize.ipynb, que gerará os gráficos utilizados no relatório.