If they were synced to your GMail account (i.e. stored as Google contacts and you have syncing enabled) you should just be able to resync them.
Otherwise, unless you made a backup they are probably gone (might depend on how you lost them, which we don't know, but if the database has been emptied there's very little to be done).