Map-HashMap, Set-HashSet, Array-List-ArrayList 의 관계

기본기 채우기

개굴이모자 2022. 9. 24. 00:29

자료 구조에서 많이 쓰이는 Map, Set, List 에 대해서 헷갈리는
Map-HashMap, Set-HashSet, List-ArrayList 간의 관계의 개념을 정리해보고자 한다.

Map은 key-value 형태를 가지는 자료형의 인터페이스로 value의 중복을 허용한다. HashMap, SortedMap 등이 해당 인터페이스를 구현한 예시이다.

HashMap은 HashTable을 사용하고, Hash 알고리즘을 이용해 검색 속도가 매우 빠르다. key-value 를 묶어 하나의 table의 entry로 저장한다.

TreeMap은 key-value를 한쌍으로 데이터를 구성해 이진 검색 트리의 형태로 저장한다. (정확히는 Red-Black Tree로 이진 검색 트리의 향상된 version이다.)

# Hashing이란?

암호 기법의 알고리즘으로 데이터를 추정하기 힘든 조각으로 나누어 값을 생성하는 알고리즘이다.
매우 빠른 연산과 중복 방지를 보장하기 때문에 자료 구조에도 활용된다.

ex ) HashMap, HashSet, SHA 등..

Set은 집합으로 저장 순서를 유지하지 않고 중복 값을 허용하지 않는다. (순서 유지를 원할 경우 LinkedHashSet을 이용한다.)

리스트와 비교해 중복 자료가 불가한 것 외에도 검색 속도에 큰 장점이 있기 때문에 HashSet의 사용을 권장한다. (HashSet, TreeSet, LinkedHashSet 중 HashSet의 성능이 가장 뛰어나기 때문.)

HashSet은 저장 시, 인스턴스의 해시값을 기준으로 저장하고 해싱으로 구현된다. 순서대로 저장된 값의 사용이 어려우므로 LinkedHashSet을 사용하거나 Iterator를 사용해야한다.

TreeSet은 이진 탐색 트리형태로 데이터를 저장하는 컬렉션이다. (정확히는 Red-Black Tree로 이진 검색 트리의 향상된 version이다.)

Array란 Index와 값의 쌍으로 구성된 데이터로, 이들을 하나의 이름으로 그룹핑하여 관리하는 자료구조이다. 정의와 동시에 길이가 정해지며 바꿀 수 없다. 크기가 고정이므로 한 value 가 삭제되면 빈 공간이 되고 메모리가 낭비되며 넘칠 수도 없다.

List는 Array와 달리 빈 공간 없이 데이터를 적재한다. (Java는 빈 공간을 허용하기도 한다.)

불연속적으로 메모리 공간을 차지하며 순차성을 보장하지 못하고 포인터를 이용해 값에 접근한다.

ArrayList는 일반 배열처럼 인덱스로 객체를 관리하나, 크기를 동적으로 늘릴 수 있다. 처음 설정한 저장 용량을 넘어서면 크기를 1.5배 증가시킨다.