Java - Оптимизация поиска строки в списке

Question

У меня есть ArrayList объектов, где каждый объект содержит строку «слово» и дату. Мне нужно проверить, прошла ли дата для списка из 500 слов. ArrayList может содержать до миллиона слов и дат. Даты, которые я храню как целые числа, поэтому проблема заключается в попытке найти слово, которое я ищу в ArrayList.

Есть ли способ сделать это быстрее? В python у меня есть dict и mWords ['foo'] - это простой поиск без прокрутки всего 1 миллиона элементов в массиве mWords. Есть что-то подобное в java?

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

Answer 1

Если слова являются уникальными, то использовать HashMap , Я имею в виду, { "а", 1}, { "Ъ", 2}

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

и wordsAndDates.get("a") return 1

Если нет, вы не должны использовать HashMap, поскольку он отменяет предыдущее значение. Я имею в виду

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

и wordsAndDates.get("a") return 3

В таком случае вы можете использовать ArrayList и искать в нем

Answer 2

Если вы не застряли с ArrayList вы должны использовать какой-то структуры данных хэш на основе. В этом случае кажется, что HashMap должен хорошо поместиться (он довольно близок к dict). Это даст вам время поиска O (1) (по сравнению с вашим текущим методом линейного поиска).

Answer 3

Вы хотите использовать Map в Java

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

Answer 4

насчет Collections.binarySearch() (NB: список должен быть отсортирован), если НУ застряли с ArrayList