Morgan Stanley
Multi-level low-latency hashing scheme

Abstract:

A system for storing and looking up values via hash table is disclosed. The system comprises multiple hash tables, each hash table being associated with a different hashing function and a content addressable memory (CAM). One or more processors receive a request to store a value; generate hashes of the value via each of the hashing functions; determine whether there exists at least one hash table that has a vacancy for the value; and if the determination is positive, insert the value in one of the at least one hash tables having the vacancy, and if the determination is negative, insert the value in the CAM. The processors also receive a request to look up a value; determine whether any of the hash tables or the CAM contain the value; and return the determination of whether the any of the plurality of hash tables or the CAM contain the value.