Hash-based data structure

1. A non-transitory computer-readable medium comprising:

hash table instructions comprising:

initialization instructions that, when executed, cause one or more processors to perform an initialization process for initializing a lock-free hash table having a storage bitmap, a metadata table, and a storage array;

insert instructions that, when executed, cause one or more processors to perform an insert process for inserting a key-value pair into the lock-free hash table, wherein the insert process includes:

receiving a key and a value;

hashing the key to obtain a hashed key;

mapping the hashed key to a start location, wherein mapping the hashed key to the start location includes:

performing h modulo n, where h is the hashed key and n is a number of slots in the storage array;

locating an unoccupied location in a storage array based on the start location and using a storage bitmap;

adding the value to a slot of the storage array corresponding to the unoccupied location; and

adding the hashed key and the unoccupied location to a mapping entry in a metadata table; and

lookup instructions that, when executed, cause one or more processors to perform a lookup process for returning a value corresponding to a given key from the lock-free hash table.

2. The computer-readable medium of claim 1 , wherein the initialization process includes contiguously creating the storage bitmap, the metadata table, and the storage array as fixed-size memory regions in memory.

3. The computer-readable medium of claim 1 , wherein the insert process does not call an operating-system-level memory function.

4. The computer-readable medium of claim 3 , wherein the insert process does not call a memory manager function of one provided by the hash table instructions.

5. The computer-readable medium of claim 1 , wherein the insert process includes an operation that uses the storage bitmap to identify available slots in the storage array of the lock-free hash table.

6. The computer-readable medium of claim 5 , wherein the insert process identifies available memory in the storage array of the lock-free hash table using linear probing with respect to a start location determined based on the hashed key.

7. The computer-readable medium of claim 5 , wherein the insert process identifies available memory in the storage array of the lock-free hash table using linear probing with respect to a start location determined based on a hashed key.

8. The computer-readable medium of claim 1 , wherein the insert process includes using linear probing to identify available memory locations in the storage array of the lock-free hash table.

9. The computer-readable medium of claim 1 , wherein the insert process uses linear probing to resolve hash collisions.

10. The computer-readable medium of claim 1 , wherein the insert process is lock free with respect to the lock-free hash table.

11. The computer-readable medium of claim 1 , wherein the hashed key is a number.

12. The computer-readable medium of claim 1 , wherein locating the unoccupied location includes:

determining whether a bit of the storage bitmap corresponding to the start location indicates that a slot of the storage array at the start location in the storage array is available.

13. The computer-readable medium of claim 1 , further comprising:

receiving a second key;

hashing the second key to obtain a second hashed key;

mapping the second hashed key to a start location;

locating a second mapping entry in the metadata table corresponding to the second key; and

returning a second value stored in the storage array in a location specified in the mapping entry.