TIL_64(배열, list, ArrayList, Dictionary)

 

23.11.03. 64차

 

오늘은 기술면접시간에 배열과 list, ArrayList, Dictionary의 차이점에 대해 공부했다.

 

배열은 동일한 데이터 타입의 원소들의 집합으로, 크기가 고정되어 있어 크기 변경을 위해선 새 배열을 생성해야한다는 특징이 있다.
배열의 장점으로는 메모리공간을 연속적으로 사용하기에 오버헤드가 적고, 인덱스를 통한 빠른 접근으로 O(1)의 시간 복잡도로 원소에 접근이 가능하다.
단점으로는 크기가 고정되어 있어 크기 변경을 위해선 새 배열을 생성하고 데이터를 복사해야한다는것과 데이터를 추가하거나 제거할 때 많은 데이터 이동이 필요해 불편하다는 것이다.

list는 Generic 네임스페이스에 있는 제너릭 컬렉션으로, 크기가 동적으로 변경될 수 있고, 각 요소의 데이터 타입이 정해져있다는 특징이 있다.
list의 장점으로는 크기가 동적으로 변경될 수 있어서 데이터의 추가 및 삭제가 유연하다, 또한 제네릭 컬렉션이기 때문에 타입의 안정성을 제공한다.
단점으로는 내부적으로 배열을 사용하기 때문에 크기를 동적으로 조절할 때 오버헤드가 발생할 수 있다는 점이 있다.

ArrayList는 크기도 동적으로 변경될 수 있고, 모든 타입의 객체를 포함할 수 있다는 특징이 있다.
ArrayList의 장점으로는 list와 마찬가지로 데이터의 추가 및 삭제에 유연하며, list와는 다르게 모든 타입의 객체를 한번에 저장할 수 있다는 것이다.
단점으로는 타입을 여러개를 다루다보니 타입의 안정성이 떨어져 잘못된 타입의 데이터를 추가할 위험이 있다.

Dictionary는 key와 값을 동시에 가지고있는 컬렉션으로 내부의 각 항목들은 key와 값을 가지고있으며 key를 통해 값을 참조할 수 있는 특징이 있다.
이 때 각 key들은 유일해야 한다.
Dictionary의 장점으로는 key가 있기때문에 O(1) 시간 복잡도로 빠르게 검색할 수 있고, 데이터간의 연관 관계를 명확하게 표현할 수 있다는 것이다.
단점으로는 key를 통해 값을 불러오는 HashTable 구조상 다른 자료 구조보다 메모리가 클 수 있다는 점이 있다.

꼬리질문 a- Dictionary는 어떻게 구현해야 하는가
a. Dictionary는 <Tkey,TValue> 형태로 HashTable기반으로 구현되어 있다.
hash table이란 key를 사용해 빠르게 값을 검색하는 구조로 각 key에 대해 코드를 계산한 후, Hash 코드를 사용하여 값을 저장하거나 인덱스를 빠르게 결정한다.
따라서 각각의 key들이 중복되지 않도록 구현하면 해당 key값에 대한 계산을 조금 더 빠르게 할 수 있고, 해당 key를 확인하는 과정을 줄일 수 있다. 

꼬리질문 b- Dictionary 검색이 빠른 이유는?
b. 검색이 빠른 이유 역시 위에서 설명한 것 처럼 Hash코드를 사용하는데, 
Hash코드는 key를 배열의 인덱스로 변환하는데 사용하므로 중복되는 key값만 없다면 O(1)의 시간복잡도로 key에 해당하는 값을 검색할 수 있다.
또한 HashTable은 버킷이라는 슬롯에 데이터를 저장하고, Hash코드를 통해 적절한 버킷이 선택되어 버킷에 key와 값 한쌍이 저장된다.
충돌이 발생한 경우에는 연결리스트나 또 다른 메커니즘을 사용해 충돌을 해결한다.
내부에서 동적으로 크기를 조절하기때문에 데이터의 양이 증가할수록 버킷의 수도 증가해서 검색 성능을 최적화한다.