使用比较器在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); 
    } 
} 

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 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

它注册加入一个HashMap的Key和Dog对象的值，然后搜索Map。

O(1)插入和O(1)搜索。

二进制搜索O(log n)。

Answer 2

我同意@Pritam Banerjee的回答。最有效的搜索技术是在这种情况下使用HashMap。我会建议使用HashSet，但HashSet＃包含方法返回布尔值，所以只需使用map。这是代码片段。

只是为了信息当使用基于散列的集合/地图，不要忘记来实现的hashCode妥善equals方法。

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）

Answer 3

对于第一个问题，即通过注册号此处搜索细节代码

import java.util.Comparator; 
import java.util.TreeMap; 

public class DogSort { 

    public static void main(String[] args) { 
     TreeMap<Integer, Dog> listDogs = new TreeMap<>(); 
     listDogs.put(33, new Dog("Max", "German Shepherd", "33")); 
     listDogs.put(11, new Dog("Gracie", "Rottweiler", "11")); 
     System.out.println(listDogs); 
     System.out.println(listDogs.containsKey(11)); 
     System.out.println(listDogs.get(11)); 
    } 
} 

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); 
     } 
    }; 

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

} 

使用arraylist得到登录号码的狗的详细是非常困难的，但是与地图相当容易。

而且你可以重写hashcode和equals方法，但是arraylist比较方法的工作方式不同。

你可以做的是你可以写一个方法，可以通过注册号查询详细信息。该方法必须迭代列表并找到Dog对象，并且如果列表已排序，则需要实现自己的二进制搜索以根据注册号获取Dog对象。

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 

public class DogSort { 

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

     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); 
     System.out.println(listDog.contains(new Dog("Max", "Rottweiler", "33"))); 
    } 
} 

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); 
     } 
    }; 

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

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     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 (registrationNumber == null) { 
      if (other.registrationNumber != null) 
       return false; 
     } else if (!registrationNumber.equals(other.registrationNumber)) 
      return false; 
     return true; 
    } 


}