Methods, apparatus, systems and articles of manufacture are disclosed for efficient media indexing. An example method disclosed herein includes selecting a first hash seed value based on a first entropy value calculated for a first bucket distribution resulting from use of the first hash seed value to store data in a first hash table, selecting a second hash seed value to be used in combination with the first hash seed value based on a second entropy value calculated on a second bucket distribution resulting from use of the first hash seed value in combination with the second hash seed value, and storing data in the first hash table based on the first hash seed value and a second hash table based on the second hash seed value.