[ Java ] Collection

 

데이터들을 효율적으로 관리할 수 있게 해주는 프레임워크입니다. 

배열의 경우 한 번 크기가 정해지면 별경할 수 없으므로 삭제나 추가 등의 작업을 할 때 어려운 점이 많지만 Collection 에서는 삭제, 수정, 검색 등의 작업을 효율적으로 할 수 있는 다양한 메소드들을 제공해 주기 때문에 효과적으로 데이터를 관리할 수 있습니다.

 

 

 Vector

ArrayList의 구버전으로 ArrayList와 사용법이 같습니다.

 

 ArrayList

내부적으로 데이터를 배열에서 관리하며 추가, 삭제시 임시 배열을 생성하여 데이터를 복사하는 구조입니다.

대량의 자료를 추가, 삭제할 시 메모리 소모가 크고, 시간이 오래걸려 성능저하가 발생하며, 사이즈가 고정되어 있기때문에 사이즈를 초과할시 사이즈가 늘어난 배열을 생성하여 데이터를 옮겨야하기에 복잡한 연산과 메모리가 필요하다는 단점이 있습니다. 하지만 데이터마다 Index를 가지고 있기 때문에 검색에 뛰어납니다.

Vector와 달리 기본적으로 동기화가 적용되지 않고 동기화가 필요한 경우에만 메소드를 이용해서 동기화 처리를 해줍니다.

 

 LinkedList

데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있습니다. ( 양방향 LinkedList )

ArrayList와 달리 데이터의 추가, 삭제시 불필요한 데이터의 복사가 없어 데이터의 추가, 삭제시에 유리한 반면 데이터를 검색 시에는 처음부터 노드를 순회해야 하기 때문에 느립니다.

 

 

 Map 

HashMap과 HashTable은 Java API의 이름입니다. HashMap과 HashTable은 제공하는 기능은 같습니다. 다만 HashMap은 보조 해시 함수(Additional Hash Funtion)을 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(Hash collistion)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있습니다. HashTable에 비해 HashMap은 지속적으로 개선되고 있습니다. 

 

HashTable과 HashMap을 정의한다면, 'Key'에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array라고 할 수 있습니다. 이 associate array를 지칭하는 다른 용어는 Map, Dictionary, Symbol Table 등이 있습니다. associative array를 지칭하기 위하여 HashTable에서는 Dictionary라는 이름을 사용하고, HashMap에서는 그 명칭이 그대로 말하듯이 Map이라는 용어를 사용합니다.

 

 해시 충돌을 해결하기 위한 방법 - JAVA 8 기준

두 가지 방법 모두 Worst Case O(M)입니다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비하여 캐시 효율이 높습니다. 따라서 데이터 개수가 충분히 적다면 Open Addressing이 Separate Chaining보다 더 성능이 좋습니다.

 

 

1. Open Addressing

데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식입니다. 데이터를 저장/조회할 해시 버킷을 찾을 때에는 Linear Probing, Quadratic Probing 등의 방법을 사용합니다. 

2. Separate Chaining

각 배열의 인자는 Index가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head)입니다.

 

아래와 같은 이유로 Java HashMap에서는 Separate Chaining 방식을 사용합니다.

1. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문입니다.
2. HashMap에 저장된 key-value 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chainging보다 느립니다.
3. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문입니다. Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있습니다. ( 보조 해시 함수 )

Java8 부터는 데이터의 개수가 많아지면, Separate Chaining에서 링크드 리스트 대신 트리(Red-Black Tree)를 사용합니다. 링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 Key-Value 쌍의 개수입니다. 예를 들어 변경 기준이 8개라면 하나의 해시 버킷에 8개의 Key-Value 쌍이 모이면 링크드 리스트를 트리로 변경합니다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경합니다. 트리로 변경하는 기준과 링크드 리스트로 변경하는 기준이 차이가 나는 이유는 어떤 한 Key-Value 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문입니다.

 

보조 해시 함수 ( Supplement hash function )

index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있습니다. 그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야합니다.

 

 

 

출처

1. Naver D2 - Java HashMap은 어떻게 동작하는가?