Searching in ArrayList with more than one arguments

Yesterday, I was given following task to implement in technical round. I do not want you to implement all the tasks, I tried myself but I stuck at question 3. My question is how do I implement to search by registration number? Because as per question 5, it should be more efficient. I tried with HashMap but could not solve it.

1. Maintains a list of dogs in alphabetical order, first by name, then by breed.
2. Provides a method for adding new dogs.
3. Provides a method for searching by registration number.
4. Provides a method for search by Name.
5. Employs the most efficient search techniques available.
6. Constructor that accepts an initial list of dogs.
7. What simple construct could be done to improve the Dog class

DogSort.java

public class DogSort {

    public static void main(String[] args) {
        ArrayList<Dog> listDog = new ArrayList<Dog>();

        Scanner sc = new Scanner(System.in);

        listDog.add(new Dog("Max", "German Shepherd", "33"));
        listDog.add(new Dog("Gracie","Rottweiler","11"));
        listDog.add(new Dog("Sam", "Beagle", "22"));
        System.out.println(listDog);

        System.out.println("Select one of the following commands: ");
        System.out.println(
                "Press 1: Sort by name\n"+
                "Press 2: Sort by breed\n" +
                "Press 3: Add new dog\n" +
                "Press 4: Search by registration number\n" +
                "Press 5: Serach by Name\n ");

        int i = sc.nextInt();
        switch (i){
            case 1: Collections.sort(listDog, Dog.COMPARE_BY_NAME);
                System.out.println(listDog);
                break;
            case 2:
                Collections.sort(listDog, Dog.COMPARE_BY_BREED);
                System.out.println(listDog);
                break;
            default:
                System.out.println("Invalid input");
                break;       
        }

    } 
}

Dog.java

class Dog {
    private String name;
    private String breed;
    private String registrationNumber;


    public Dog(String name, String breed, String registrationNumber) {
        this.name = name;
        this.breed = breed;
        this.registrationNumber = registrationNumber;
    }

    public String getName() {
        return this.name;
    }

    public String getBreed() {
        return this.breed;
    }

    public String getRegistrationNumber() {
        return this.registrationNumber;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setBreed(String breed) {
        this.breed = breed;
    }

    public void setRegistrationNumber(String registrationNumber) {
        this.registrationNumber = registrationNumber;
    }

    @Override
    public String toString() {
        return this.name;
    }


    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
    };

    public static Comparator<Dog> COMPARE_BY_BREED = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.breed.compareTo(other.breed);
        }
    };
}