Patent ID: 9152661
Filing Date: 2015-10-06
Classification: G06F

Abstract:
1. A method for searching a data structure, comprising: providing a data structure, wherein the data structure comprises a plurality of data entries stored in an external random access memory (RAM) and a portion of the data structure is stored in an internal cache memory; performing one or more hash functions on each entry of the data structure to generate an encoding that maps to a location in the external RAM; maintaining a count of encodings that map to the location in the external RAM, wherein a first portion of the count of encodings is stored in the internal cache memory and a second portion of the count of encodings is stored in the external RAM, the first portion of the count of encodings comprises an indication of whether the second portion of the count of encodings is used; and the second portion of the count of encodings is an extension of the first portion of the count of encodings; receiving a search string; performing the one or more hash functions on the search string to generate an index to the count of encodings; and searching the data structure in accordance with the count of encodings stored in the internal cache memory and in the external RAM, wherein maintaining the count of encodings comprises: if there is the indication the second portion of the count of encoding is not used, incrementing the first portion of the count in response to a different entry of the data structure that maps to the location in the external RAM, and decrementing the first portion of the count in response to an entry that maps to the location in the external RAM is removed from the data structure.