Proximity Map Search

Using the data structures created by proximity sorting, find an element within that container in O(1) time.

• Hash the key being searched to find Bucket
• Look up ProxMap[Bucket] to see if the bucket even exists
• If it exists, ProxMap[Bucket] points at the neighborhood where the value is
• Scan the neighborhood for the desired value

• Wikipedia
• Proximity Sorting