  In this work, we aim to study when learned models are better hash functions,
particular for hash-maps. We use lightweight piece-wise linear models to
replace the hash functions as they have small inference times and are
sufficiently general to capture complex distributions. We analyze the learned
models in terms of: the model inference time and the number of collisions.
Surprisingly, we found that learned models are not much slower to compute than
hash functions if optimized correctly. However, it turns out that learned
models can only reduce the number of collisions (i.e., the number of times
different keys have the same hash value) if the model is able to over-fit to
the data; otherwise, it can not be better than an ordinary hash function.
Hence, how much better a learned model is in avoiding collisions highly depends
on the data and the ability of the model to over-fit. To evaluate the
effectiveness of learned models, we used them as hash functions in the bucket
chaining and Cuckoo hash tables. For bucket chaining hash table, we found that
learned models can achieve 30% smaller sizes and 10% lower probe latency. For
Cuckoo hash tables, in some datasets, learned models can increase the ratio of
keys stored in their primary locations by around 10%. In summary, we found that
learned models can indeed outperform hash functions but only for certain data
distributions and with a limited margin.
