Shri Khalpada breaking down how Shazam works:

Computers can flip the script. Instead of asking ”which song matches this sequence of sounds?”, the phone asks ”for each of these sounds, which songs contain them?” for each hash in the clip. It’s the same idea as the index at the back of a book: rather than re-reading every page to find a word, you jump to the word’s entry and see every page it lives on. 

This essentially makes the lookup operation O(1)O(1), meaning it takes roughly the same amount of time whether you have 100 songs or 100 million. More precisely, the phone goes straight to each hash’s address rather than scanning through songs, and the number of possible hashes is large enough that each address only contains a handful of entries, even across millions of songs.