Methods and apparatus are disclosed to identify media using hash keys. An example method involves when a first metered hash key does not match a first reference hash key, generating, with a processor, an error level using a bitwise comparison of the first metered hash key and a second reference hash key corresponding to a second metered hash key. When the error level satisfies a threshold, the example method involves obtaining, with a processor, media reference data stored in association with the second reference hash key, and storing, with a processor, the media reference data in association with the first metered hash key.