You can read Marlinspike's 2017 description of an approach they were then rolling out – & AFAIK still use – at: https://signal.org/blog/private-contact-discovery/

Note it relies on SGX for privacy. (Anything they did earlier may have involved even more trust of Signal Inc's servers.)

Hashes across the (tiny!) space of all phone numbers are easy to reverse via brute-force.

But also, again: how do you think Signal is able to notify you when any phone number in your contacts – even if you're not in theirs! – first joins Signal?