The contacts in your email may be different from the Contacts app, since Mail can check your past emails for addresses. Real quick though, is there a list of address books (local, iCloud, Facebook, etc) on the left side of the Contacts app, and maybe you are "in" the wrong one?
The first thing you should do to make sure you still have your addresses on iCloud, provided you used to sync them to iCloud, is to log on to icloud.com with your Apple ID and password. If you see your contacts on there, you're good.
Then you should be able to go to the iCloud account settings in System Preferences (you can use the Spotlight option in System Preferences to find it if you need help) and make sure you're signed in to iCloud and that you have Contacts selected to sync.
If they are not on iCloud, and you have a Time Machine backup, open Contacts and go in to Time Machine to restore them.