They could use a technique like Google Safe Browsing where you send a partial hash of the url, and they send back the subset of the map containing only urls which could match that hash