Help! someone has hacked into my phone/apple id and their contacts appeared out of no where in my contacts app and safari browser as well

I was using my phone as per normal and texting my Friend through WhatsApp, when suddenly his name disappeared. So I went to the contacts app and discovered almost 100 foreign contacts of random people as though it’s another person’s phone. I tried to restore my phon, but it didn’t help.