Worm hashing
An entries array having a pre-selected number of initially empty buckets and structured as a circular array is maintained. Each of the pre-selected number of entries in the entries array has a corresponding index value. A chaining array having the pre-selected number of buckets and structured as a circular array is also maintained. Each of the pre-selected number of entries in the chaining array has the same corresponding index value as the corresponding bucket in the entries array. A hash operation is performed on data to be stored to determine a hash value corresponding to the data. The data is stored in a bucket in the entries array corresponding to the hash value as an unmovable head-of-chain entry, and moving previous data, if any, stored in the entries array corresponding to the hash value if the previous data has a different hash value. The data is stored in another bucket in the entries array if the bucket in the entries array corresponding to the hash value is occupied by a head-of-chain entry. The bucket storing the data is linked to the head-of-chain entry with the chaining array.
1. A non-transitory, computer-readable medium having stored thereon instructions that, when executed by one or more processors, are configurable to cause the one or more processors to:
maintain multiple chains of entries in one or more circular arrays of buckets, wherein a single hash value corresponds to a single chain of entries in the multiple chains of entries and each chain of entries has one unmovable head-of-chain entry at an index equal to a hash value for data stored therein, and one or more tail-of-chain entries having the same hash value as the head-of-chain entry, but occupying a different bucket in the chain of entries;
perform a hash operation, with the one or more hardware processors, on new data to be stored to determine a hash value corresponding to the new data;
store the new data in a bucket in the entries array corresponding to the hash value as an unmovable head-of-chain entry, and moving previous data, if any, stored in the entries array corresponding to the hash value when the previous data has a different hash value, wherein moving the previous data comprises:
moving a current tail-of-chain entry to a near free bucket if the near free bucket is found before a subsequent entry in the entries array and updating links between the buckets having entries,
moving the current tail-of-chain entry to a far free bucket if the far free bucket is found after the subsequent entry of the entries array and within a maximum offset range, wherein the current tail-of-chain entry is moved to the far free bucket to become a new tail-of-chain and a previous link for the entry is modified to point to a next entry in the chain.
2. The non-transitory, computer-readable medium of claim 1 further comprising instructions that, when executed by the one or more processors, are configurable to cause the one or more processors to:
determine, with the one or more hardware processors, no free buckets are available in the entries array;
cause, with the one or more hardware processors, the entries array to be enlarged;
re-hash, with the one or more hardware processors, the enlarged entries array; and
add, with the one or more hardware processors, at least one entry to the entries array.
3. The non-transitory computer-readable medium of claim 1 wherein a sign bit in an array entry indicates whether the corresponding bucket contains a head-of-chain entry or a tail-of-chain entry.
4. The non-transitory, computer-readable medium of claim 1 wherein the near free bucket is found through a linear probing of the one or more circular arrays.
5. The non-transitory, computer-readable medium of claim 1 wherein the far free bucket is found through a linear probing of the one or more circular arrays.
6. The non-transitory, computer-readable medium of claim 1 , wherein a data item lookup comprises:
performing a single hash computation for the data item;
iterating from the head-of-chain entry matching the computed hash value through the corresponding chain until the data item is found.
7. A method comprising:
maintaining multiple chains of entries in one or more circular arrays of buckets, wherein a single hash value corresponds to a single chain of entries in the multiple chains of entries and each chain of entries has one unmovable head-of-chain entry at an index equal to a hash value for data stored therein, and one or more tail-of-chain entries having the same hash value as the head-of-chain entry, but occupying a different bucket in the chain of entries;
performing a hash operation, with the one or more hardware processors, on new data to be stored to determine a hash value corresponding to the new data;
storing the new data in a bucket in the entries array corresponding to the hash value as an unmovable head-of-chain entry, and moving previous data, if any, stored in the entries array corresponding to the hash value when the previous data has a different hash value, wherein moving the previous data comprises:
moving a current tail-of-chain entry to a near free bucket if the near free bucket is found before a subsequent entry in the entries array and updating links between the buckets having entries,
moving the current tail-of-chain entry to a far free bucket if the far free bucket is found after the subsequent entry of the entries array and within a maximum offset range, wherein the current tail-of-chain entry is moved to the far free bucket to become a new tail-of-chain and a previous link for the entry is modified to point to a next entry in the chain.
8. The method of claim 7 further comprising:
determining, with the one or more hardware processors, no free buckets are available in the entries array;
causing, with the one or more hardware processors, the entries array to be enlarged;
re-hashing, with the one or more hardware processors, the enlarged entries array; and
adding, with the one or more hardware processors, at least one entry to the entries array.
9. The method of claim 7 wherein a sign bit in an array entry indicates whether the corresponding bucket contains a head-of-chain entry or a tail-of-chain entry.
10. The method of claim 7 wherein the near free bucket is found through a linear probing of the one or more circular arrays.
11. The method of claim 7 wherein the far free bucket is found through a linear probing of the one or more circular arrays.
12. The method of claim 7 , wherein a data item lookup comprises:
performing a single hash computation for the data item;
iterating from the head-of-chain entry matching the computed hash value through the corresponding chain until the data item is found.
13. A system comprising:
a memory system having one or more memory devices;
one or more hardware processors coupled with the memory system, the one or more hardware processors configurable to maintain multiple chains of entries in one or more circular arrays of buckets, wherein a single hash value corresponds to a single chain of entries in the multiple chains of entries and each chain of entries has one unmovable head-of-chain entry at an index equal to a hash value for data stored therein, and one or more tail-of-chain entries having the same hash value as the head-of-chain entry, but occupying a different bucket in the chain of entries, to perform a hash operation, with the one or more hardware processors, on new data to be stored to determine a hash value corresponding to the new data, to store the new data in a bucket in the entries array corresponding to the hash value as an unmovable head-of-chain entry, and moving previous data, if any, stored in the entries array corresponding to the hash value when the previous data has a different hash value, wherein moving the previous data comprises moving a current tail-of-chain entry to a near free bucket if the near free bucket is found before a subsequent entry in the entries array and updating links between the buckets having entries and moving the current tail-of-chain entry to a far free bucket if the far free bucket is found after the subsequent entry of the entries array and within a maximum offset range, wherein the current tail-of-chain entry is moved to the far free bucket to become a new tail-of-chain and a previous link for the entry is modified to point to a next entry in the chain.
14. The system of claim 13 further comprising:
determining, with the one or more hardware processors, no free buckets are available in the entries array;
causing, with the one or more hardware processors, the entries array to be enlarged;
re-hashing, with the one or more hardware processors, the enlarged entries array; and
adding, with the one or more hardware processors, at least one entry to the entries array.
15. The system of claim 13 wherein a sign bit in an array entry indicates whether the corresponding bucket contains a head-of-chain entry or a tail-of-chain entry.
16. The system of claim 13 wherein the near free bucket is found through a linear probing of the one or more circular arrays.
17. The system of claim 13 wherein the far free bucket is found through a linear probing of the one or more circular arrays.
18. The system of claim 13 , wherein a data item lookup comprises:
performing a single hash computation for the data item;
iterating from the head-of-chain entry matching the computed hash value through the corresponding chain until the data item is found.