A storage device, such as a NAND flash device, includes a controller that maintains a temperature for a plurality of data blocks, the temperature calculated according to a function that increases with a number of valid data objects in the block and recency with which the valid data objects have been accessed. Blocks with the lowest temperature are selected for garbage collection. Recency for a block is determined based on a number of valid data objects stored in the block that are referenced in a hot list of a LRU list. During garbage collection, data objects that are least recently used are invalidated to reduce write amplification.