Time-Outs With Time-Reversed Linear Probing

• US 20110066603A1
• Filed: 09/14/2009
• Published: 03/17/2011
• Est. Priority Date: 09/14/2009
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Thorup, Mikkel
• Granted Patent: US 8,306,958 B2
• Time in Patent Office: Days
• US Class Current: 707/696
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A current key is received at a current arrival time at a computer. An index in an array corresponding to the current key is determined using a hash function. A previous key and a previous arrival time are retrieved from the array at the index. The array is transformed by replacing the previous key and the previous arrival time with the current key and the current arrival time in the array at the index. The previous key and the previous arrival time are inserted into a nearest eligible sequential index in the array.

Claims

1. A computer-implemented method for implementing timeouts in a hash table, the method comprising computer-implemented operations for:

receiving a current key at a current arrival time at a computer;

determining an index in an array corresponding to the current key using a hash function;

retrieving a previous key and a previous arrival time stored in the array at the index;

transforming the array by replacing the previous key and the previous arrival time with the current key and the current arrival time in the array at the index; and

inserting the previous key and the previous arrival time into a nearest eligible sequential index in the array.

2. The computer-implemented method of claim 1, wherein inserting the previous key and the previous arrival time into a nearest eligible sequential index in the array comprises:

incrementing the index to a first incremented index, wherein the array at the first incremented index contains a third key and a third arrival time;

determining whether the previous arrival time is more recent than the third arrival time;

in response to determining that the previous arrival time is more recent than the third arrival time, retrieving the third key and the third arrival time;

upon retrieving the third key and the third arrival time, transforming the array by replacing the third key and the third arrival time with the previous key and previous arrival time in the array at the first incremented index; and

inserting the third key and the third arrival time into a nearest eligible sequential index in the array.

3. The computer-implemented method of claim 2, further comprising computer-implemented operations for:

in response to determining that the previous arrival time is not more recent than the third arrival time, incrementing the first incremented index to a second incremented index, wherein the array at the second incremented index contains a fourth key and a fourth arrival time;

determining whether the previous arrival time is more recent than the fourth arrival time;

in response to determining that the previous arrival time is more recent than the fourth arrival time, retrieving the third key and the third arrival time;

upon retrieving the third key and the third arrival time, transforming the array by replacing the fourth key and the fourth arrival time with the previous key and previous arrival time in the array at the second incremented index; and

inserting the fourth key and the fourth arrival time into a nearest eligible sequential index in the array.

4. The computer-implemented method of claim 1, further comprising computer-implemented operations for:

determining whether the previous arrival time has expired; and

in response to determining that the previous arrival time has expired, discarding the previous key.

5. The computer-implemented method of claim 1, further comprising computer-implemented operations for:

determining whether the previous key is equal to the current key; and

in response to determining that the previous key is equal to the current key, updating the previous arrival time with the current arrival time.

6. The computer-implemented method of claim 1, wherein each key in the array expires in a fixed lifetime.

7. The computer-implemented method of claim 1, wherein each key in the array expires in an individual lifetime.

8. A system for implementing timeouts in a hash table, comprising:

a memory for storing a program containing code for implementing timeouts in the hash table; and

a processor functionally coupled to the memory, the processor being responsive to computer-executable instructions contained in the program and configured to;

receive a current key at a current arrival time,

determine an index in an array corresponding to the current key using a hash function,

retrieve a previous key and a previous arrival time stored in the array at the index,

transform the array by replacing the previous key and the previous arrival time with the current key and the current arrival time in the array at the index, and

insert the previous key and the previous arrival time into a nearest eligible sequential index in the array.

9. The system of claim 8, wherein to insert the previous key and the previous arrival time into a nearest eligible sequential index in the array, the processor is further configured to:

increment the index to a first incremented index, wherein the array at the first incremented index contains a third key and a third arrival time,

determine whether the previous arrival time is more recent than the third arrival time,

in response to determining that the previous arrival time is more recent than the third arrival time, retrieve the third key and the third arrival time,

upon retrieving the third key and the third arrival time, transform the array by replacing the third key and the third arrival time with the previous key and previous arrival time in the array at the first incremented index, and

insert the third key and the third arrival time into a nearest eligible sequential index in the array.

10. The system of claim 9, wherein the processor is further configured to:

in response to determining that the previous arrival time is not more recent than the third arrival time, increment the first incremented index to a second incremented index, wherein the array at the second incremented index contains a fourth key and a fourth arrival time,

determine whether the previous arrival time is more recent than the fourth arrival time,

in response to determining that the previous arrival time is more recent than the fourth arrival time, retrieve the third key and the third arrival time,

upon retrieving the third key and the third arrival time, transform the array by replacing the fourth key and the fourth arrival time with the previous key and previous arrival time in the array at the second incremented index, and

insert the fourth key and the fourth arrival time into a nearest eligible sequential index in the array.

11. The system of claim 8, wherein the processor is further configured to:

determine whether the previous arrival time has expired, and

in response to determining that the previous arrival time has expired, discard the previous key.

12. The system of claim 8, wherein the processor is further configured to:

determine whether the previous key is equal to the current key, and

in response to determining that the previous key is equal to the current key, update the previous arrival time with the current arrival time.

13. The system of claim 8, wherein each key in the array expires in an individual lifetime.

14. A computer-readable medium having instructions stored thereon for execution by a processor to provide a method for implementing timeouts in a hash table, the method comprising:

receiving a current key at a current arrival time;

determining an index in an array corresponding to the current key using a hash function;

retrieving a previous key and a previous arrival time stored in the array at the index;

transforming the array by replacing the previous key and the previous arrival time with the current key and the current arrival time in the array at the index; and

inserting the previous key and the previous arrival time into a nearest eligible sequential index in the array.

15. The computer-readable medium of claim 14, wherein inserting the previous key and the previous arrival time into a nearest eligible sequential index in the array comprises:

incrementing the index to a first incremented index, wherein the array at the first incremented index contains a third key and a third arrival time;

determining whether the previous arrival time is more recent than the third arrival time;

in response to determining that the previous arrival time is more recent than the third arrival time, retrieving the third key and the third arrival time;

upon retrieving the third key and the third arrival time, transforming the array by replacing the third key and the third arrival time with the previous key and previous arrival time in the array at the first incremented index; and

inserting the third key and the third arrival time into a nearest eligible sequential index in the array.

16. The computer-readable medium of claim 15, further comprising:

in response to determining that the previous arrival time is not more recent than the third arrival time, incrementing the first incremented index to a second incremented index, wherein the array at the second incremented index contains a fourth key and a fourth arrival time;

determining whether the previous arrival time is more recent than the fourth arrival time;

in response to determining that the previous arrival time is more recent than the fourth arrival time, retrieving the third key and the third arrival time;

upon retrieving the third key and the third arrival time, transforming the array by replacing the fourth key and the fourth arrival time with the previous key and previous arrival time in the array at the second incremented index; and

inserting the fourth key and the fourth arrival time into a nearest eligible sequential index in the array.

17. The computer-readable medium of claim 14, further comprising:

determining whether the previous arrival time has expired; and

in response to determining that the previous arrival time has expired, discarding the previous key.

18. The computer-readable medium of claim 14, further comprising:

determining whether the previous key is equal to the current key; and

in response to determining that the previous key is equal to the current key, updating the previous arrival time with the current arrival time.

19. The computer-readable medium of claim 14, wherein each key in the array expires in a fixed lifetime.

20. The computer-readable medium of claim 14, wherein each key in the array expires in an individual lifetime.