Increase multi_index_container performance and erase performance

I have a boost multi_index_container declared below which is indexed with hash_unique id (unsigned long) and hash_non_unique transaction id (long). Inserting and retrieving items is fast, but when I remove items it is much slower. I expected this to be constant time when the key is hashed.

eg To erase items from a container

for 10000 elements, it takes about 2.53927016 seconds

for 15,000 elements, it takes about 7.37100068 seconds

for 20,000 elements, it takes about 21.391720757 seconds

Am I missing something or expected behavior?

class Session
{
  public:
    Session () {
      // increment unique id
      static unsigned long counter = 0;
      boost :: mutex :: scoped_lock guard (mx);
      counter ++;
      m_nId = counter;
    }

    unsigned long GetId () {
     return m_nId;
    }
    long GetTransactionHandle () {
    return m_nTransactionHandle;
    }
    ....
private:
  unsigned long m_nId;
  long m_nTransactionHandle;
  boost :: mutext mx;
  ....
};

typedef multi_index_container<
  Session*,
  indexed_by< 
    hashed_unique< mem_fun<Session,unsigned long,&Session::GetId> >,
    hashed_non_unique< mem_fun<Session,unsigned long,&Session::GetTransactionHandle> >
    >  //end indexed_by
  > SessionContainer;
typedef SessionContainer::nth_index<0>::type SessionById;


int main() {
  ...
   SessionContainer container;
   SessionById *pSessionIdView = &get<0>(container);
   unsigned counter = atoi(argv[1]);
   vector<Session*> vSes(counter);
   //insert
   for(unsigned i = 0; i < counter; i++) {
     Session *pSes = new Session();
     container.insert(pSes); 
     vSes.push_back(pSes);
   }
   timespec ts;
   lock_settime(CLOCK_PROCESS_CPUTIME_ID, &ts);
   //erase
   for(unsigned i = 0; i < counter; i++) {
      pSessionIdView->erase(vSes[i]->getId());
      delete vSes[i];
   }
   lock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
   std::cout << "Total time taken for erase:" << ts.tv_sec << "." << ts.tv_nsec << "\n";
   return (EXIST_SUCCESS);
}