Which Queue provides better performance? (Queue + Hashmap or just Queue)

Is it better (in terms of performance, OO design and readability) to manage a queue of events using a map (id/object) and then have queue to hold just the ID's like below:

1.

private Map<Integer,Person> allPeople = new HashMap<>(); //id, person Object   
private Queue<Integer> peopleQueue = new LinkedList<Integer>(); //a queue of IDs

When a new item added to the map, then method adds the id to the queue: q.add(id); Then the program retrieves the correct person object by something like:

int id = peopleQueue.remove();
Person p = Map.get(id);
//etc etc

Is above 'better' than doing:

2.

private List<Person> allPeople = new HashList<Person>();
private Queue<Person> peopleQueue = new LinkedList<Person>();  

//then in method I would have
peopleQueue.add(person);

Then to retrieve an id I would do:

int id = (peopleQueue.remove()).getId();

for(Person person: allPeople){
    if(person.getId().equals(id)){
        return person;
    }
}

The system must handle a large number of people, surely it would be quicker using my first implementation rather than iterating through each person.getId() until a match is found?