map.remove() isn't removing the records from a map [duplicate]

Question

When I update a contact in Salesforce, I want to update the contact's related object's records (Contact Information object) address if it exists else insert a record.

I am using the below code but in the event of an update, Along with updating the lookup's record, it is inserting an additional record every time for an update.

I am using a Map(mp) to record a list of updates and remove them from a list of contacts map(conMapIDs). but my code isn't removing them properly(after verifying using debugs)

Any thoughts on what I'm doing incorrectly here?

private static void updateContactInfoFromContact(Map<Id,Contact> newConMap , Map<Id,Contact> OldConMap){
    Set<Id> conIdSet = new Set<Id>();
    Map <Contact,Contact_Information__c> mp = New Map<Contact,Contact_Information__c>();
    Map <Contact,Id> conMapIDs = new Map <Contact,Id>();
    List<Contact_Information__c> ConInfotoUpdate = new List<Contact_Information__c>();
    Map<String,Schema.RecordTypeInfo> RTsByName = Schema.SObjectType.Contact_Information__c.getRecordTypeInfosByName();
    for(Contact con: newConMap.values()){
      if(String.isNotBlank(con.MailingStreet) && String.isNotBlank(con.MailingCity) && String.isNotBlank(con.MailingState) && String.isNotBlank(con.MailingCountry) && String.isNotBlank(con.MailingPostalCode)){
        conIdSet.add(con.id);
        conMapIDs.put(con,con.Id);  
      }
    }
    system.debug('conIdSet Contents:' + conIdSet);
    List<Contact_Information__c> contactsInfoToUpdate = [select id, Line_1__c,Line_2__c,State__c,City__c, Country__c,Zip__c,Address_Type__c, Make_Address_Primary__c, Address__c,
     contact__r.MailingStreet,contact__r.MailingCity,contact__r.MailingState, contact__r.MailingCountry,contact__r.MailingPostalCode from  Contact_Information__c
     Where contact__c IN:conIdSet AND Make_Address_Primary__c = true];
    system.debug('contactsInfoToUpdate query results' + contactsInfoToUpdate );
    for(Contact_Information__c conInfo : contactsInfoToUpdate){
      if(conInfo.contact__r.MailingStreet != conInfo.Line_1__c || conInfo.contact__r.MailingState != conInfo.State__c || conInfo.contact__r.MailingCity != conInfo.City__c ||
        conInfo.contact__r.MailingCountry != conInfo.Country__c || conInfo.contact__r.MailingPostalCode != conInfo.Zip__c){            
        conInfo.Line_1__c = conInfo.contact__r.MailingStreet;
        conInfo.State__c = conInfo.contact__r.MailingState;
        conInfo.City__c = conInfo.contact__r.MailingCity;
        conInfo.Country__c = conInfo.contact__r.MailingCountry;
        conInfo.Zip__c = conInfo.contact__r.MailingPostalCode;
        conInfo.Address_Type__c = 'Business';
      } 
      ConInfotoUpdate.add(conInfo);
      mp.put(conInfo.contact__r,conInfo);
      system.debug('values in mp' + mp);
    }

    system.debug('values in conMapIDs before remove' + conMapIDs);  
    if(ConInfotoUpdate.size() > 0){
      system.debug('ConInfotoUpdate.size()' + ConInfotoUpdate.size());
      update ConInfotoUpdate;
    }
    for(Contact cc : mp.keyset()){
       system.debug('values in CC' + cc);
        conMapIDs.remove(cc);

    }

    system.debug('values in conMapIDs after remove' + conMapIDs);      
    for(Contact c : conMapIDs.keySet()){
        if(c.MailingCity != null && c.MailingCountry != null && c.MailingPostalCode != null && c.MailingState != null && c.MailingStreet != null){
        system.debug('before insert check for contact' + c.Name);  
           Contact_Information__c ci = new Contact_Information__c(RecordTypeId = RTsByName.get('Address').getRecordTypeId(), Contact__c = c.Id, Make_Address_Primary__c = true, Line_1__c = c.MailingStreet.split(',')[0], State__c = c.MailingState, City__c = c.MailingCity, Country__c = c.MailingCountry, Zip__c = c.MailingPostalCode, Address_Type__c = 'Business');
            if(c.MailingStreet.split(',').size() == 2)
                ci.Line_2__c = c.MailingStreet.split(',')[1];
        insert ci;
        system.debug('inserted records for'+ c.Name);
        }
      }
  }