We would have no way to locate your contacts. If they were synced with a google account, you can try and get them from there. Or if you had saved them to your card.
You could also try logging into your account with your carrier/service provider, and looking at the call log. While it won't give you names, it will give you numbers and call times. You can gain some of the info through there.
Otherwise, there would be no way to get them.