Java - Optimieren Sie das Suchen einer Zeichenfolge in einer Liste

Question

Ich habe eine ArrayList von Objekten, wobei jedes Objekt eine Zeichenfolge 'Wort' und ein Datum enthält. Ich muss überprüfen, ob das Datum für eine Liste von 500 Wörtern abgelaufen ist. Die ArrayList könnte bis zu einer Million Wörter und Daten enthalten. Die Daten, die ich als ganze Zahlen speichere, versuchen das Wort, nach dem ich suche, in der ArrayList zu finden.

Gibt es eine Möglichkeit, dies schneller zu machen? In Python habe ich ein dict und mWords ['foo'] ist ein einfaches Nachschlagen, ohne die ganzen 1 Million Elemente im mWords-Array durchlaufen zu müssen. Gibt es so etwas in Java?

for (int i = 0; i < mWords.size(); i++) { 
     if (word == mWords.get(i).word) { 
      return mWords.get(i); 
     } 
    } 

Answer 1

stecken Wenn die Worte werden dann einzigartige HashMap verwenden . Ich meine, { "a", 1}, { "b", 2}

Map<String, Integer> wordsAndDates = new HashMap<String, Integer>(); 
wordsAndDates.put("a", 1); 
wordsAndDates.put("b", 2); 

und wordsAndDates.get("a") return 1

Wenn nicht Sie nicht HashMap verwenden sollten, weil es vorherigen Wert überschreibt. Ich meine

wordsAndDates.put("a", 1); 
wordsAndDates.put("b", 2); 
wordsAndDates.put("a", 3); 

und wordsAndDates.get("a") return 3

In einem solchen Fall, dass Sie ArrayList und suchen darin

Answer 2

Wenn Sie mit einem ArrayList nicht stecken sollten Sie irgendeine Art von Hash-basierte Datenstruktur verwenden. In diesem Fall scheint es so, als ob ein HashMap gut passen sollte (es ist ziemlich nah an Pythons dict). Dies gibt Ihnen eine O (1) Lookup-Zeit (im Vergleich zu Ihrer aktuellen Methode der linearen Suche).

Answer 3

Sie wollen eine Map in Java verwenden

Map<String,Integer> mWords = new HashMap<String, Integer>(); 
mWords.put ("foo", 112345); 

Answer 4

Was Collections.binarySearch() (NB: Die Liste muss sortiert werden), wenn ou mit dem ArrayList