ArrayListでコンパレータを使用して検索

Question

私は今日インタビューをしました。私は2つの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にそれを追加し、値としてDogオブジェクト、その後Mapを検索します。

O(1)挿入およびO(1)検索。

バイナリ検索O(log n)。

Answer 2

私は@Pritam Banerjeeの答えに同意します。最も効率的な検索手法は、このシナリオでHashMapを使用することです。私はHashSetを使用することをお勧めしますが、HashSet＃containsメソッドはbooleanを返します。コードスニペットは次のとおりです。ただ、情報ため

ハッシュベースのコレクション/マップを使用してハッシュコードを実装することを忘れていけないと適切に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のcompareメソッドは異なる方法で動作します。

あなたができることは、登録番号で詳細を検索できる方法を書くことです。このメソッドは、リストを反復して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; 
    } 


}