Не знаете, какой тип списка выбрать?

Question

Я не так разбираюсь в структурах данных Java (но обучения) и не знал, какой тип списка выбрать. Моя проблема заключается в том, что я создаю службу сокета, которая берет данные и проверяет их против списка, если он не существует, он передает данные для обработки и добавляет номер идентификатора данных в список, так что те же данные не будут (служба, обрабатывающая данные, не знает, существует ли дублируемая работа или нет, поэтому она действует как фильтр).

Я читал, что arraylist работает быстро, но я просто понял, что он требует от меня знать размер списка раньше, чего я не делаю, поскольку он продолжает расти (он наверняка поразит несколько миллиардов предметов). Я думал, что просто использую целое целое число [], но думал, что спрошу, есть ли лучший способ.

Есть несколько особенностей, связанных с моим процессом, мои данные сами по себе сложны, но для поиска я конвертирую данные в хэш-код и проверяю на это, поэтому все мои данные являются целыми (положительными/отрицательными) и обслуживанием запросы клиентов выполняются с помощью runnable, поэтому, если есть что-то, что я могу сделать, чтобы сделать данные более эффективными, я могу это сделать (я думал, так как все его Целые, возможно, сортируют его так часто, чтобы сделать петли быстрее?). Является ли целое число [] достаточно хорошим или есть что-то лучше?

Answer 1

Если идентификатором является число или строка, вы можете использовать HashSet<IDType>, где IDType - тип идентификатора (например, int). Это обеспечивает оптимальное время поиска, и каждый элемент хранится только один раз.

ArrayList тоже будет работать, но для поиска в нем вам нужно будет пройти весь список (возможно, в худшем случае), сравнивая каждый элемент.

Answer 2

it will surely hit several billion items 

Я очень сомневаюсь в этом. Это будет гигабайт данных.

Если у вас действительно есть миллиарды предметов, я бы рекомендовал сохранить их в базе данных, а не в памяти. Вам, конечно, разрешено кэшировать подмножество в памяти, чтобы ускорить выполнение некоторых запросов, но долгосрочное решение - это база данных, которая сохранит значения, даже если сервер опустится.

Запрос базы данных для проверки и проверки наличия идентификатора будет стоить всего миллисекунды. Я думаю, что это лучшее долгосрочное решение, чем хранение их в памяти.

Answer 3

Ну, если вы пытаетесь проверить драгоценные предметы, то в любом случае вам придется хранить все предметы. Я бы предложил использовать HaspMap. Кроме того, вы можете использовать несколько hashmaps, если этого может быть недостаточно.

Вы можете легко проверить, выполнив

if(map.containsKey(blah)) 
    //Do something 

Использование более чем один hashmap, если вы считаете, что элементы могут быть дифференцированы на основе чего-то. Это может быть быстрее. Кроме того, поскольку эти предметы являются большими, я бы предложил использовать LinkedHashMap вместе с HashMap, чтобы сделать некоторое кеширование. Это ускорит процесс, так как LinkedHashMap будет хранить часто встречающиеся элементы в своем приоритете Q.

Answer 4

Если вы уже хотите хэшировать данные, почему бы не использовать одну из хешированных коллекций, например. HashSet или HashMap, а не список?