Conclusions

This book explored the hash table data structure. It covered how to map keys from a large space—whereby you assume that the keys are uniformly distributed—into a small space of table bins. It considered a table's performance as a function of the number of bins versus how many keys are stored in a table. It also considered a table’s performance as a function of the number of bins versus how many keys are stored in a table. This book covered strategies for handling collisions when two or more different keys map to the same bin and the performance consequences of the choice of strategy. It also discussed how to dynamically adjust the size of tables to avoid having them fill up and incurring high runtime performance penalties as a consequence, while ensuring that you do not allocate tables larger than necessary and incur memory penalties as a consequence.