Latchless, non-blocking dynamically resizable segmented hash index

A method comprising:

• organizing a hash table based upon a hash function into a plurality of segments, wherein each segment of the plurality of segments includes a set of buckets;
• inserting hash records into the hash table based on a first number of bucket-identifying bits;
• without changing the hash function used for the hash table:
• dynamically resizing the hash table without blocking access to the hash table, wherein dynamically resizing the hash table includes:
• selecting a particular segment of the plurality of segments for resizing;
• wherein the particular segment includes a plurality of first buckets;
• adding to the hash table one or more companion segments of the particular segment;
• wherein the one or more companion segments include a companion segment that includes a second plurality of buckets;
• redistributing hash records from one or more buckets in the first plurality of buckets to one or more buckets in the second plurality of buckets based on a second number of bucket-identifying bits that is different than the first number of bucket-identifying bits;
• while dynamically resizing the hash table, allowing one or more requesting entities to continue to perform lookups using the hash table and the hash function;
• wherein the method is performed by one or more computing devices.

One or more non-transitory media storing instructions which, when executed by one or more computing devices, cause:

• organizing a hash table based upon a particular hash function into a plurality of segments, wherein each segment of the plurality of segments includes a set of buckets;
• inserting hash records into the hash table based on a first number of bucket-identifying bits;
• dynamically resizing the hash table without blocking access to the hash table, wherein dynamically resizing the hash table includes:
• selecting a particular segment of the plurality of segments for resizing;
• wherein the particular segment includes a first plurality of buckets;
• adding to the hash table one or more companion segments of the particular segment;
• wherein the one or more companion segments include a companion segment that includes a second plurality of buckets;
• redistributing hash records from one or more buckets in the first plurality of buckets to one or more buckets in the second plurality of buckets based on the particular hash function and a second number of bucket-identifying bits that is different than the first number of bucket-identifying bits;
• while dynamically resizing the hash table, allowing one or more requesting entities to continue to perform lookups using the hash table and the particular hash function.