Производительность Hash Set и Array List

Я реализовал метод, который просто зацикливается на наборе CSV-файлов, содержащих данные о нескольких разных модулях. Затем это добавляет 'moduleName' в hashSet. (Код показан ниже)

Я использовал hashSet, поскольку он гарантирует, что дубликаты не будут вставлены вместо ArrayList, который должен был бы использовать метод contains() и выполнять итерацию по списку, чтобы проверить, существует ли он уже.

Я считаю, что использование набора хэшей имеет лучшую производительность, чем список массивов. Я правильно это утверждаю?

Кроме того, может кто-нибудь объяснить мне:

  1. Как работать с производительностью для каждой структуры данных, если она используется?

  2. В чем сложность использования нотации big-O?

    HashSet<String> modulesUploaded = new HashSet<String>();

for (File f: marksheetFiles){
    try {
        csvFileReader = new CSVFileReader(f);
        csvReader = csvFileReader.readFile();
        csvReader.readHeaders();

        while(csvReader.readRecord()){
            String moduleName = csvReader.get("Module");

            if (!moduleName.isEmpty()){
                modulesUploaded.add(moduleName);
            }
        }

    } catch (IOException e) {
        e.printStackTrace();
    }

    csvReader.close();
}
return modulesUploaded;

    }


java arraylist performance algorithm hashset
person user1339335    schedule 17.04.2012    source источник
comment
Вы, вероятно, захотите включить язык, который вы используете, в качестве одного из тегов (вам придется исключить один из других, но язык почти несомненно важнее).   -  person Jerry Coffin    schedule 17.04.2012

Ответы (4)


arrow_upward
50
arrow_downward

Мой эксперимент показывает, что HashSet быстрее, чем ArrayList, начиная с коллекций из 3 элементов включительно.

Полная таблица результатов

| Boost  |  Collection Size  |
|  2x    |       3 elements  |
|  3x    |      10 elements  |
|  6x    |      50 elements  |
|  12x   |     200 elements  |  <= proportion 532-12 vs 10.000-200 elements
|  532x  |  10.000 elements  |  <= shows linear lookup growth for the ArrayList
person Andrey Chaschev    schedule 07.11.2013

arrow_upward
26
arrow_downward

Это совершенно разные классы, поэтому вопрос в том, какое поведение вы хотите?

HashSet гарантирует отсутствие дубликатов, дает вам метод O(1) contains(), но не сохраняет порядок.
ArrayList не гарантирует отсутствие дубликатов, contains() - это O(n), но вы можете контролировать порядок записи.

person biziclop    schedule 17.04.2012

arrow_upward
22
arrow_downward

Я считаю, что использование набора хэшей имеет лучшую производительность, чем список массивов. Я правильно это утверждаю?

Со многими (что бы это ни значило) записями, да. Однако при небольших размерах данных необработанный линейный поиск может быть быстрее, чем хеширование. Где именно находится безубыточность, вам остается только измерить. Я интуитивно чувствую, что с менее чем 10 элементами линейный поиск, вероятно, будет быстрее; с более чем 100 элементами хэширование, вероятно, быстрее, но это только мое ощущение...

Поиск из HashSet выполняется за постоянное время, O(1), при условии, что реализация элементов hashCode является разумной. Линейный поиск из списка занимает линейное время, O(n).

person Joonas Pulakka    schedule 17.04.2012

arrow_upward
5
arrow_downward

Это зависит от использования структуры данных.

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

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

Если порядок имеет значение, но вы хотите сделать много модификаций (добавление и удаление), лучше использовать LinkedList.

Для доступа к конкретному элементу HashSet будет иметь временную сложность как O (1), и если бы вы использовали ArrayList, это было бы O (N), как вы сами указали, вам пришлось бы iterate просмотреть список и посмотреть, является ли элемент нет.

person nits.kk    schedule 05.03.2016