java - 使用比较器在 ArrayList 中搜索

Question

我今天参加了面试，我上了两门 java 课，要求按注册号搜索狗的详细信息。我知道 Java.util.ArrayList.contains(Object) 但不知道当有多个字段时如何实现。

第二个问题是:您可以在此示例中使用的最有效的搜索技术是什么？我考虑过 Collections.binarySearch 但不确定它在本例中是否最有效。如果是这样，我该如何实现？

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"));
    Collections.sort(listDog, Dog.COMPARE_BY_NAME);
                System.out.println(listDog);
    }
}

狗.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 static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
};
//getter and setter methods for all private variable

}

Answer 1

我同意@Pritam Banerjee 的回答。在这种情况下，最有效的搜索技术是使用 HashMap。我建议使用 HashSet，但 HashSet#contains 方法返回 boolean 值，因此只需使用 map。这是代码片段。

Just for Information When using hash based collection/map dont forget to implement hashCode and equals method properly.

public class DogSearch {
    public static void main(String[] args) {
        Map<String, Dog> dogs = new HashMap<String, Dog>();

        Dog max = new Dog("Max", "German Shepherd", "1001");
        Dog gracie = new Dog("Gracie", "Rottweiler", "1002");
        Dog luca = new Dog("Luca", "Labrador", "1003");
        Dog tiger = new Dog("Tiger", "Beagle", "1004");
        Dog meemo = new Dog("Meemo", "Bulldog", "1005");
        Dog lacie = new Dog("Lacie", "German Shorthaired Pointer", "1006");

        dogs.put(max.getRegistrationNumber(), max);
        dogs.put(gracie.getRegistrationNumber(), gracie);
        dogs.put(luca.getRegistrationNumber(), luca);
        dogs.put(tiger.getRegistrationNumber(), tiger);
        dogs.put(meemo.getRegistrationNumber(), meemo);
        dogs.put(lacie.getRegistrationNumber(), lacie);

        Dog result = dogs.get("1002");

        if (result == null) {
            System.out.println("Dog not found");
        } else {
            System.out.println(result);
        }
    }
}

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 static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
    };

    public String getName() {
        return name;
    }

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

    public String getBreed() {
        return breed;
    }

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

    public String getRegistrationNumber() {
        return registrationNumber;
    }

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

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((breed == null) ? 0 : breed.hashCode());
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + ((registrationNumber == null) ? 0 : registrationNumber.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Dog other = (Dog) obj;
        if (breed == null) {
            if (other.breed != null)
                return false;
        } else if (!breed.equals(other.breed))
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        if (registrationNumber == null) {
            if (other.registrationNumber != null)
                return false;
        } else if (!registrationNumber.equals(other.registrationNumber))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Dog [name=" + name + ", breed=" + breed + ", registrationNumber=" + registrationNumber + "]";
    }

}

时间复杂度

插入:O(1)

搜索:O(1)