Exemplary methods for verifying data integrity for garbage collection with limited memory include maintaining a data structure that includes a plurality of entries, storing states of a group of segments compressed therein. In response to receiving a request for transitioning a segment from a first state to a second state, retrieving a first entry value of an entry associated with the first segment, generating a second entry value based on the first entry value, the first state, the second state, and a value obtained from a first lookup table based on the first segment. The methods also include writing back the second entry value to the first entry of the data structure. In one embodiment, in response to determining all entries of the data structure reach a predetermined final state, performing a garbage collection process on the segments stored in the storage system.