Try to do inserts in constant time.