Hashing data from address book doesn't work because people write the same addresses and even phone numbers in many different ways. Normalizing it on the client is not really an option either because it requires a lot of data to do decent normalization - not practical to send it all to each client.
Phone numbers are easy to canonicalize: convert to international form.
Email addresses can be effectively canonicalized by lower casing. Not many mail servers are case sensitive these days. Additionally, for the local part, you can generally strip off anything after a "+", and with gmail, you can drop any period in the local part. (Granted, it's not perfect-- so make sure that's not a security concern.)
These techniques have been working fine so far in my app for my "Find My Friends" feature.
