Flash Memory Hash Table

A computing device, comprising:

• a flash memory, the flash memory comprising:
• a main storage comprising a plurality of entry storage locations distributed among a plurality of erase units, wherein the entry storage locations are configured to store a plurality of entries,
• a persistent tag vector storage comprising a plurality of persistent tag storage locations configured to store a plurality of persistent tags, wherein individual ones of the plurality of persistent tags are associated with corresponding individual ones of the plurality of entries, wherein the persistent tags are configured to identify obsolescence;
• and
• a processor configured in communication with the flash memory.

An article comprising:

• a signal bearing medium comprising machine-readable instructions stored thereon, which, if executed by one or more processors, operatively enable a computing device to:
• determine an input key hash value by hashing an input key of an input key/value pair, wherein the input key/value pair includes an input key and an input value;
• identify a write erase unit based at least in part on the determined input key hash value;
• designate one or more entries in the identified write erase unit with an obsolete value when stored key/value pairs in the entries include a stored key that corresponds to the input key and includes a stored value that does not correspond to the input value;
• and
• compact the write erase unit when the identified write erase unit to be written to is determined to be full, wherein the compaction of the write erase unit is based at least in part on the designated obsolete value.