Array size: number of buckets in the proximity map.
Hit count: count of items that hashed to a particular bucket.
Location: Location[x] correlates to a record in Data[x]; but this stores which hash bucket the element belongs to.
Proximity map: Holds the first index (of the Data array) for an element that hashes to this bucket. Elements defined in ProxMap[x] have an above zero value in HitCount[x]
Data: array which holds the elements within the map
Step 1: initialize memory, helper arrays.
Step 2: hash members of unsorted array to find the buckets they will belong to and count memberships
Step 3: insertion sort elements of the unsorted array to their neighborhood in the sorted array
ProxMaps want a hash function where keys can be kept in ascending order as well as spread evenly across the buckets.
The college paper uses a technique:
- Convert all keys to integers
- Find the highest and lowest integers
- Convert all keys to a float in the range of [0, 1] based on the highest and lowest integer
- Round the floats