Java 컬렉션 구현을 선택하는 경험 법칙?

Java 컬렉션 구현을 선택하는 경험 법칙?

---

누구나 List, Map 또는 Set과 같은 Java Collection 인터페이스의 다른 구현 중에서 선택하는 데 좋은 경험 법칙이 있습니까?

예를 들어, 일반적으로 Vector 또는 ArrayList, Hashtable 또는 HashMap을 사용하는 이유 또는 어떤 경우에 선호합니까?

---

나는 항상 다음과 같은 사용 사례에 따라 사례별로 결정을 내 렸습니다.

• 계속 주문해야합니까?
• null 키 / 값이 있습니까? Dups?
• 여러 스레드에서 액세스 할 수 있습니까?
• 키 / 값 쌍이 필요합니까?
• 랜덤 액세스가 필요합니까?

그런 다음 편리한 5 판 Java를 Nutshell로 나누고 ~ 20 개 정도의 옵션을 비교합니다. 5 장에는 무엇이 적절한 지 파악하는 데 도움이되는 멋진 작은 표가 있습니다.

좋아, 아마도 간단한 ArrayList 또는 HashSet이 트릭을 할 것이라는 것을 알고 있다면 모든 것을 찾지 않을 것입니다. ;) 그러나 나의 의도 된 사용에 대해 원격으로 복잡한 것이 있다면, 당신은 내가 책에 있다고 확신합니다. BTW, 벡터는 '오래된 모자'로되어 있지만 몇 년 동안 사용하지 않았습니다.

---

Sergiy Kovalchuk의 블로그 항목에있는 이 치트 시트가 정말 마음에 듭니다 .

더 자세한 내용은 Alexander Zagniotov의 순서도 였지만 불행히도 오프라인 상태입니다. 그러나 Wayback Machine에는 블로그 사본이 있습니다 .

---

위의 답변에서 List, Set 및 Map의 차이점을 알고 있다고 가정합니다. 구현 클래스 중에서 선택하는 이유는 또 다른 것입니다. 예를 들면 :

목록 :

1. ArrayList 는 검색 속도가 빠르지 만 삽입 속도가 느립니다. 많이 읽지 만 많이 삽입 / 제거하지 않는 구현에 좋습니다. 데이터를 하나의 연속 메모리 블록에 보관하므로 확장해야 할 때마다 전체 배열을 복사합니다.
2. LinkedList 는 검색 속도가 느리지 만 삽입 속도는 빠릅니다. 많이 삽입 / 제거하지만 많이 읽지 않는 구현에 좋습니다. 하나의 연속 메모리 블록에 전체 배열을 유지하지 않습니다.

세트:

1. HashSet 은 반복 순서를 보장하지 않으므로 세트 중 가장 빠릅니다. 오버 헤드가 높고 ArrayList보다 느리므로 해싱 속도가 중요한 요소가 될 때 많은 양의 데이터를 제외하고는 사용하지 마십시오.
2. TreeSet 은 데이터를 순서대로 유지하므로 HashSet보다 느립니다.

Map : HashMap 및 TreeMap의 성능 및 동작은 Set 구현과 유사합니다.

Vector 및 Hashtable은 사용하지 않아야합니다. 새 컬렉션 계층이 출시되기 전에는 동기화 된 구현이므로 느립니다. 동기화가 필요한 경우 Collections.synchronizedCollection ()을 사용하십시오.

---

이론적으로는 유용한 Big-Oh 장단점이 있지만 실제로는 거의 중요하지 않습니다.

실제 벤치 마크에서, ArrayList밖으로 수행 LinkedList에도 큰리스트와 같은 조작으로 "전면 근처의 삽입을 많이." 학자들은 실제 알고리즘이 점근 곡선을 압도 할 수있는 일정한 요소를 가지고 있다는 사실을 무시합니다. 예를 들어, 연결 목록은 모든 노드에 대한 추가 개체 할당이 필요하므로 노드 생성 속도가 느려지고 메모리 액세스 특성이 훨씬 더 나빠집니다.

내 규칙은 :

1. 항상 ArrayList, HashSet 및 HashMap (즉, LinkedList 또는 TreeMap 아님)으로 시작하십시오.
2. 유형 선언은 항상 인터페이스 (예 : List, Set, Map) 여야하므로 프로파일 러 또는 코드 검토가 그렇지 않은 것으로 입증되면 아무것도 손상시키지 않고 구현을 변경할 수 있습니다.

---

첫 번째 질문에 대해 ...

목록,지도 및 세트는 다른 용도로 사용됩니다. http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html 에서 Java Collections Framework에 대해 읽어 볼 것을 제안 합니다.

좀 더 구체적으로 말하면 :

• 배열과 같은 데이터 구조가 필요하고 요소를 반복해야하는 경우 List 사용
• 사전과 같은 것이 필요하면 Map을 사용하십시오.
• 무언가가 세트에 속하는지 여부 만 결정해야하는 경우 세트를 사용하십시오.

두 번째 질문에 대해 ...

Vector와 ArrayList의 주요 차이점은 전자는 동기화되고 후자는 동기화되지 않는다는 것입니다. Java Concurrency in Practice의 동기화에 대해 자세히 읽을 수 있습니다 .

Hashtable (T는 대문자가 아님)과 HashMap의 차이점은 비슷하고 전자는 동기화되고 후자는 동기화되지 않습니다.

하나의 구현 또는 다른 구현을 선호하는 경험 법칙은 없으며 실제로 필요에 따라 다릅니다.

---

정렬되지 않은 경우 10 개 중 9 번 이상이 가장 좋은 선택은 ArrayList, HashMap, HashSet입니다.

Vector와 Hashtable은 동기화되어 있으므로 약간 느릴 수 있습니다. 동기화 된 구현을 원하는 경우는 드뭅니다. 그러면 해당 인터페이스가 동기화가 유용 할만큼 충분히 풍부하지 않습니다. Map의 경우 ConcurrentMap은 인터페이스를 유용하게 만들기 위해 추가 작업을 추가합니다. ConcurrentHashMap은 ConcurrentMap의 좋은 구현입니다.

LinkedList는 거의 좋은 생각이 아닙니다. 많은 삽입 및 제거를 수행하더라도 색인을 사용하여 위치를 표시하는 경우 올바른 노드를 찾기 위해 목록을 반복해야합니다. ArrayList는 거의 항상 더 빠릅니다.

Map 및 Set의 경우 해시 변형이 트리 / 정렬보다 빠릅니다. 해시 알고리즘은 O (1) 성능을 갖는 반면 트리는 O (log n)입니다.

---

목록은 중복 항목을 허용하는 반면 세트는 하나의 인스턴스 만 허용합니다.

조회를 수행해야 할 때마다 맵을 사용하겠습니다.

특정 구현의 경우지도 및 세트의 순서를 유지하는 변형이 있지만 대부분 속도가 중요합니다. 나는 합리적으로 작은 목록에 ArrayList를 사용하고 합리적으로 작은 집합에 HashSet을 사용하는 경향이 있지만 많은 구현이 있습니다 (직접 작성한 것을 포함하여). HashMap은지도에서 매우 일반적입니다. '합리적으로 작은 것'보다 더 많은 것은 메모리에 대해 걱정하기 시작해야 알고리즘 적으로 훨씬 더 구체적이 될 것입니다.

This page has lots of animated images along with sample code testing LinkedList vs. ArrayList if you're interested in hard numbers.

EDIT: I hope the following links demonstrate how these things are really just items in a toolbox, you just have to think about what your needs are: See Commons-Collections versions of Map, List and Set.

---

As suggested in other answers, there are different scenarios to use correct collection depending on use case. I am listing few points,

ArrayList:

• Most cases where you just need to store or iterate through a "bunch of things" and later iterate through them. Iterating is faster as its index based.
• Whenever you create an ArrayList, a fixed amount of memory is allocated to it and once exceeeded,it copies the whole array

LinkedList:

• It uses doubly linked list so insertion and deletion operation will be fast as it will only add or remove a node.
• Retrieving is slow as it will have to iterate through the nodes.

HashSet:

• Making other yes-no decisions about an item, e.g. "is the item a word of English", "is the item in the database?" , "is the item in this category?" etc.

• Remembering "which items you've already processed", e.g. when doing a web crawl;

HashMap:

• Used in cases where you need to say "for a given X, what is the Y"? It is often useful for implementing in-memory caches or indexes i.e key value pairs For example: For a given user ID, what is their cached name/User object?.
• Always go with HashMap to perform a lookup.

Vector and Hashtable are synchronized and therefore bit slower and If synchronization is needed, use Collections.synchronizedCollection(). Check This for sorted collections. Hope this hepled.

---

I found Bruce Eckel's Thinking in Java to be very helpful. He compares the different collections very well. I used to keep a diagram he published showing the inheritance heirachy on my cube wall as a quick reference. One thing I suggest you do is keep in mind thread safety. Performance usually means not thread safe.

---

Well, it depends on what you need. The general guidelines are:

List is a collection where data is kept in order of insertion and each element got index.

세트 는 중복이없는 요소 모음 입니다 (같은 요소를 다시 삽입하면 추가되지 않음). 데이터에는 질서라는 개념이 없습니다.

지도 모든 가능한 개체가 될 수있는 키로 데이터 요소에 액세스하고 씁니다.

속성 : https://stackoverflow.com/a/21974362/2811258

Java 컬렉션에 대한 자세한 내용은 이 기사를 확인하십시오 .

참고 URL : https://stackoverflow.com/questions/48442/rule-of-thumb-for-choosing-an-implementation-of-a-java-collection