In order to add a location, there are two important steps:
- Compute the hash
- Choose a bucket
Further operations, such as doing a sorted insert, will improve performance too, but they can be omitted by using a tree instead of a list within each bucket.
The location cache implementation uses a simple modulo operation between the hash and the length of the array to choose a bucket, which means that on top of regular hash collisions, choosing the size of the internal storage has a major influence on the performance as well. Choose a size too small and the buckets will overlap, regardless of the hash function!
In Rust code, the first part is done in the first line using the provided boxed hashcode function to create a hash. What follows is finding a bucket by applying something akin to the modulo operation (a binary AND operation between the hash and the highest index of the storage array) and a linear search of the attached list. If the key is found, the attached pair is...
