Scalable, concurrent resizing of hash tables

A data processing system having one or more processors, a memory operatively coupled to said one or more processors, and a hash table loadable in said memory, said hash table having hash buckets each containing items that are chained together in a linked list, program instructions loadable in said memory for programming said one or more processors to perform operations for resizing said hash table, said operations comprising:

• processing each item in said hash table to determine if said item requires logical relocation from a first bucket associated with a first table size that exists at commencement of resizing to a second bucket associated with a second table size that will exist at completion of resizing;
• if said item requires logical relocation, linking said item to said second bucket without moving or copying said item in memory;
• waiting until there are no current hash table readers whose search of said hash table could be affected by unlinking said item from said first bucket;
• and
• unlinking said item from said first bucket without moving or copying said item in memory.

A computer program product, comprising:

• one or more computer-readable storage media;
• program instructions on said one or more media for programming a data processing system to perform operations for resizing a hash table, said data processing system having one or more processors, a memory operatively coupled to said one or more processors, and a hash table loadable in said memory, said hash table having hash buckets each containing items that are chained together in a linked list, said operations comprising:
• processing each item in said hash table to determine if said item requires logical relocation from a first bucket associated with a first table size that exists at commencement of resizing to a second bucket associated with a second table size that will exist at completion of resizing;
• if said item requires logical relocation, linking said item to said second bucket without moving or copying said item in memory;
• waiting until there are no current hash table readers whose search of said hash table could be affected by unlinking said item from said first bucket;
• and
• unlinking said item from said first bucket without moving or copying said item in memory.

A computer-implemented method for resizing a hash table, comprising:

• establishing a hash table in a computer memory operatively coupled to one or more processors;
• said hash table having hash buckets each containing items that are chained together in a linked list;
• processing each item in said hash table to determine if said item requires logical relocation from a first bucket associated with a first table size that exists at commencement of resizing to a second bucket associated with a second table size that will exist at completion of resizing;
• said second bucket being either in said hash table or in a second hash table of different size that is to replace said hash table;
• if said item requires logical relocation, linking said item to said second bucket without moving or copying said item in memory;
• waiting until there are no current hash table readers whose search of said hash table could be affected by unlinking said item from said first bucket;
• and
• unlinking said item from said first bucket without moving or copying said item in memory.