List와 Set 간의 성능 및 메모리 할당 비교

List와 Set 간의 성능 및 메모리 할당 비교

---

성능, 메모리 할당 및 유용성 측면에서 List와 Set의 비교를 알고 싶습니다.

개체 목록에서 고유성을 유지해야하는 요구 사항이없고 삽입 순서를 유지할 필요도없는 경우 ArrayList와 SortedSet / HashSet을 서로 바꿔서 사용할 수 있습니까? 목록 / 세트 대신 Collections 클래스를 직접 사용하는 것이 좋을까요?

추신 나는 또한 java에서 제공하는 특정 기능을 나열하거나 설정할 필요가 없습니다. 추가 프로그래밍 노력없이 동적으로 성장할 수 있기 때문에 Array 대신 List / Set을 사용하고 있습니다.

---

순서에 신경 쓰지 않고 요소를 삭제하지 않으면이 데이터 구조에서 요소를 찾아야하는지 여부와 이러한 조회가 얼마나 빨리 필요한지에 따라 결정됩니다.

a에서 값으로 요소를 찾는 것은 HashSet입니다 O(1). 에서 ArrayList, 그것은이다 O(n).

컨테이너를 사용하여 여러 고유 한 개체를 저장하고 마지막에 순서에 관계없이 반복 ArrayList하는 경우 더 간단하고 경제적이기 때문에 더 나은 선택 일 것입니다.

---

HashSetArrayList동일한 수의 요소 보다 약 5.5 배 더 많은 메모리를 소비하며 (둘 다 선형이지만) 반복 속도가 상당히 느립니다 (동일한 무증상에도 불구하고). 빠른 Google 검색은 HashSet반복에 비해 ArrayList.

당신이 고유성 또는 성능에 대해 걱정하지 않는 경우 contains, 다음 사용합니다 ArrayList.

---

요소 만 추가하고 나중에 반복 할 계획이라면 ArrayList교체 할 배열에 가장 가깝기 때문에 가장 좋은 방법이 있습니다. LinkedList어떤 Set구현 보다 메모리 효율성이 높고 삽입, 반복 및 임의 액세스가 빠릅니다.

---

비교해 보면 List와 Set 사이에서 검색하면 밑줄 Hashing 알고리즘으로 인해 Set이 더 나을 것입니다.

목록의 경우 최악의 시나리오에서 포함은 끝까지 검색합니다. Set의 경우 해싱과 버킷으로 인해 일부만 검색합니다.

샘플 사용 사례 : 1 ~ 100_000 정수를 ArrayList 및 HashSet에 추가합니다. ArrayList 및 HashSet에서 각 정수를 검색합니다.

Set은 9 밀리 초가 걸리며 List는 16232 초가 걸립니다.

private static void compareSetvsList(){
    List<Integer> list = new ArrayList<>() ;
    Set<Integer> set = new HashSet<>() ;

    System.out.println("Setting values in list and set .... ");
    int counter = 100_000  ;

    for(int i =0 ; i< counter ; i++){            
        list.add(i);
        set.add(i);
    }

    System.out.println("Checking time .... ");
    long l1 = System.currentTimeMillis();
    for(int i =0 ; i< counter ; i++) list.contains(i);

    long l2 = System.currentTimeMillis();
    System.out.println(" time taken for list : "+ (l2-l1));

    for(int i =0 ; i< counter ; i++)set.contains(i);

    long l3 = System.currentTimeMillis();
    System.out.println(" time taken for set : "+ (l3-l2));

    //      for 10000   time taken for list : 123        time taken for set : 4
    //      for 100000  time taken for list : 16232          time taken for set : 9
    //      for 1000000 time taken for list : hung       time taken for set : 26

}

---

컬렉션에 고유 한 요소가 있어야하는 요구 사항이없는 경우 ArrayList매우 구체적인 요구 사항이없는 한 사용하십시오 .

컬렉션에 고유 한 요소 만 있어야하는 요구 사항이있는 경우 HashSet매우 구체적인 요구 사항이없는 한 사용하십시오 .

관련하여 SortedSet(그리고 그것의 구현 TreeSet의 JavaDoc에 따라) :

요소에 대한 전체 순서를 추가로 제공하는 Set입니다. 요소는 자연 순서를 사용하거나 일반적으로 정렬 된 세트 생성 시간에 제공되는 비교기를 사용하여 정렬됩니다.

set이는 일반적으로 필요하지 않은 요소가 항상에서 정렬되어야하는 매우 구체적인 사용 사례를 대상으로한다는 것을 의미합니다 .

---

자주 HashSet사용해야 할 경우 사용하십시오 .contains(T).

예:

private static final HashSet<String> KEYWORDS = Stream.of(new String[]{"if", "do", "for", "try", "while", "break", "return"}).collect(Collectors.toCollection(HashSet::new));

public boolean isKeyword(String str) {
     return KEYWORDS.contains(str);
}

ReferenceURL : https://stackoverflow.com/questions/10799417/performance-and-memory-allocation-comparison-between-list-and-set