A multi-threaded garbage collector operates in increments and maintains, for each of a plurality of car sections in which it has divided a portion of the heap, a respective remembered set of the locations at which it has found references to objects in those car sections. It stores the remembered sets in respective hash tables, whose contents it updates in a scanning operation, executed concurrently by multiple threads, in which it finds references and records their locations in the appropriate tables. Occasionally, one of the threads replaces the hash table for a given car section. Rather than wait for the replacement operation to be completed, a thread that has an entry to be made into that car section's remembered set accesses the old table to find out whether the entry has already been made. If so, no new entry is necessary. Otherwise, it places an entry into the old table and sometimes places an insertion record containing that entry into a linked list associated with that car section. When the reclaiming thread has finished transferring information from the old table to the new table, it transfers information from the linked list of insertion records into the new table, too. In this way, the replacement process is not a bottleneck to other threads' performing update operations.