Time-outs with time-reversed linear probing
First Claim
Patent Images
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, the inserting comprisingincrementing 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, andinserting the third key and the third arrival time into a nearest eligible sequential index in the array.
1 Assignment
0 Petitions
Accused Products
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.
15 Citations
17 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, the inserting comprising 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A system for implementing timeouts in a hash table, the system comprising:
-
a memory configured to store 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 being 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, wherein in being configured to insert the previous key and the previous arrival time into a nearest eligible sequential index in the array, the processor is 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. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A non-transitory computer-readable medium having instructions stored thereon for execution by a processor to perform operations for implementing timeouts in a hash table, the operations 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, the inserting comprising 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. - View Dependent Claims (13, 14, 15, 16, 17)
-
Specification