Hidden contacts are typically synced to your Google account or other backup services. When you restore your contacts on a new device, the hidden contacts will remain hidden.