Worm hashing

• US 10,223,396 B2
• Filed: 08/26/2016
• Issued: 03/05/2019
• Est. Priority Date: 05/27/2016
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Roustant, Bruno
• Primary Examiner(s): Singh, Amresh
• Application Number:
  US15/249,271
• Publication Number:
  US 20170344545A1
• Time in Patent Office: 921 Days
• Field of Search: None
• CPC Class Codes: G06F 16/214 Database migration support
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

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.

Claims

1. A non-transitory computer-readable medium having stored thereon instructions that, when executed by one or more hardware processors, are configurable to cause the one or more processors to:

maintain an entries array having a pre-selected number of initially empty buckets and structured as a circular array in a physical memory system coupled with the one or more hardware processors, wherein each of the pre-selected number of entries in the entries array has a corresponding index value;

maintain a chaining array having the pre-selected number of buckets and structured as a circular array in the physical memory system coupled with the one or more hardware processors, wherein 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;

perform a hash operation on data to be stored to determine a hash value corresponding to the data with the one or more hardware processors;

store the 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;

store the data in another bucket in the entries array when the bucket in the entries array corresponding to the hash value is occupied by a head-of-chain entry;

link the bucket storing the data to the head-of-chain entry with the chaining array with the one or more hardware processors.

2. The non-transitory computer-readable medium of claim 1 wherein a sign bit in the corresponding chaining array entry indicates whether the corresponding entries array bucket contains a head-of-chain entry or a tail-of-chain entry.

3. The non-transitory computer-readable medium of claim 1 further comprising instructions that, when executed by one or more processors, are configurable to cause the one or more processors to displace a movable tail-of-chain entry from the bucket in the entries array corresponding to the hash value to a free bucket within the entries array.

4. The non-transitory computer-readable medium of claim 3 wherein the free bucket within the entries array is within a maximum chaining range.

5. The non-transitory computer-readable medium of claim 1 further comprising instructions that, when executed by one or more processors, are configurable to find the free bucket by analyzing the entries array within a maximum chaining range.

6. The non-transitory computer-readable medium of claim 5 wherein the analyzing the entries comprises linear probing up to the maximum chaining range.

7. The non-transitory computer-readable medium of claim 1 further comprising instructions that, when executed by one or more processors, are configurable to recursively displace one or more tail-of-chain entries in the entries array to free a bucket to add new data in the entries array when there is no free bucket available within the maximum chaining range.

8. The non-transitory computer-readable medium of claim 7 further comprising instructions that, when executed by one or more processors, are configurable to enlarge both the entries array and the chaining array if no free bucket can be found within a maximum chaining range through recursive displacement.

9. The non-transitory computer-readable medium of claim 8 further comprising re-hashing and restoring data stored in buckets of the entries array in response to enlargement of the entries array and the chaining array.

10. The non-transitory computer-readable medium of claim 9 further comprising re-hashing and restoring data stored in buckets of the entries array in response to enlargement of the entries array and the chaining array.

11. The non-transitory computer-readable medium of claim 1 further comprising instructions that, when executed by one or more processors, are configurable to enlarge both the entries array and the chaining array if no free bucket can be found within a maximum chaining range.

12. A computer-implemented method comprising:

maintaining, with one or more processors, an entries array having a pre-selected number of initially empty buckets and structured as a circular array in a physical memory system coupled with one or more hardware processors, wherein each of the pre-selected number of entries in the entries array has a corresponding index value;

maintaining, with one or more processors, a chaining array having the pre-selected number of buckets and structured as a circular array in the physical memory system coupled with the one or more hardware processors, wherein 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;

performing, with one or more processors, a hash operation on data to be stored to determine a hash value corresponding to the data;

storing, with one or more processors, the 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;

storing, with one or more processors, the data in another bucket in the entries array when the bucket in the entries array corresponding to the hash value is occupied by a head-of-chain entry;

linking, with one or more processors, the bucket storing the data to the head-of-chain entry with the chaining array.

13. The method of claim 12 wherein a sign bit in the corresponding chaining array entry indicates whether the corresponding entries array bucket contains a head-of-chain entry or a tail-of-chain entry.

14. The method of claim 12 further comprising displacing, with one or more processors, a movable tail-of-chain entry from the bucket in the entries array corresponding to the hash value to a free bucket within the entries array.

15. The method of claim 14 wherein the free bucket within the entries array is within a maximum chaining range.

16. The method of claim 12 further comprising finding, with one or more processors, the free bucket by analyzing the entries array within a maximum chaining range.

17. The method of claim 16 wherein the analyzing the entries comprises linear probing up to the maximum chaining range.

18. The method of claim 12 further comprising instructions that, when executed by one or more processors, are configurable to recursively displace one or more tail-of-chain entries in the entries array to free a bucket to add new data in the entries array when there is no free bucket available within the maximum chaining range.

19. The method of claim 18 further comprising instructions that, when executed by one or more processors, are configurable to enlarge both the entries array and the chaining array if no free bucket can be found within a maximum chaining range through recursive displacement.

20. The method of claim 19 further comprising re-hashing and restoring data stored in buckets of the entries array in response to enlargement of the entries array and the chaining array.

21. The method of claim 12 further comprising instructions that, when executed by one or more processors, are configurable to enlarge both the entries array and the chaining array if no free bucket can be found within a maximum chaining range.

22. The method of claim 21 further comprising re-hashing and restoring data stored in buckets of the entries array in response to enlargement of the entries array and the chaining array.