순서가 있는 여러개의 데이터를 저장할 때면 배열을 주로 이용한다. 또한 배열은 가장 기초적인 자료구조이기도 하며, 다른 자료구조의 기반이 되기도 한다. 이번에는 그러한 자료구조가 어떤 특징을 가지고 무슨 문제를 해결하기 위해 탄생했는지 알아보려 한다.
기본 자료구조
배열과 연결 리스트를 이해하면 다른 자료구조를 이해하고 구현하는데 도움이 된다. 배열이나 연결 리스트를 래핑해서 양 끝에서만 데이터 조작이 가능하게 되면 스택이나 큐가 된다. 끝에서만 데이터를 조작하면 스택인 것이고, 양쪽에서 데이터를 조작할 수 있으면 큐가 된다.
배열이나 연결 리스트를 여러개 사용해서 각 원소에 노드간의 관계를 나타내면 그래프가 된다. 연결 리스트에서 노드가 일관성있게 여러 노드에 대한 정보를 가져 계층 구조를 갖게 하면 트리를 만들어 낼 수 있다. 이처럼 배열과 연결 리스트가 다른 자료구조를 이해할 때 사용되는 기본 개념이다.
배열(Array)
배열은 다수의 동일한 타입의 데이터를 순서를 가지고 저장하기 위한 자료구조다.
배열은 순서를 가지고 저장되며, 메모리상에서도 연속적으로 할당된다. 동일한 타입의 데이터가 저장된다는 말은, 각 데이터의 크기가 동일하다고 볼 수 있다. 배열에 데이터가 담긴 순서를 인덱스라고 하며, 이 인덱스를 통해 배열에서 값을 빠르게 조회할 수 있게 된다.
배열에서 데이터는 순차적으로 저장되니, 맨 앞 메모리 주소만 알면 순서에 맞는 데이터를 조회할 수 있다. 데이터의 크기와 인덱스, 맨 처음 메모리 주소만 있으면 연산이 가능한 것이다.
이런 식으로 조회하면, 조회하는 데에 걸리는 시간 복잡도는 O(1)로 빠른 조회가 가능하다. 순서를 모른다면 결국 O(N)이다 덧붙여, 배열이 순차적으로 연결된 특성으로 인해 배열을 활용하면 공간 지역성을 좋게 만들 수 있다. 하지만 배열은 특정 인덱스에 데이터를 삽입하고 삭제하는 연산에서는 성능이 좋지 않다. 배열의 인덱스를 새로 맞추거나 길이를 재조정하는 것과 같은 비용이 들기 때문이다.
어떤 과정이 일어나는지 살펴보자. 배열에서 특정 인덱스에 데이터를 삽입하려면, 특정 인덱스로부터 마지막 인덱스까지를 한칸씩 뒤로 밀어낸다음 확보한 공간에 데이터를 삽입해야한다. 삭제도 비슷한데, 삽입과는 반대로 특정 인덱스 삭제시 그 특정 인덱스까지 뒤에 있는 데이터들을 앞으로 한칸씩 당겨서 복사해야한다.
이렇게 인덱스를 밀거나 당기면 그에 맞게 크기도 변경되어야 하는데, 이 과정에서 새로운 크기를 가지는 배열을 생성해서 이 배열에다가 기존의 데이터를 덮어씌우게 된다. 이렇게 삽입/삭제시 오버헤드가 발생하게 되는 것이다.
처음부터 크기가 고정되어 있는 데이터들을 담을 것이라면 문제 없겠지만 문제는 그렇지 않은 경우가 더 많다는 것이다.
파이썬에서는 여러 타입이 하나의 배열에 할당할 수 있다
이러면 어떻게 되는 것일까? 배열은 분명 동일한 타입이여야 한다. 이에 대한 답은 파이썬이 데이터를 다루는 방식에 있다. 파이썬에서 모든 타입은 객체로 다뤄진다. 객체라는 말은 실제 값이 아닌 주소값, 즉 참조값을 갖는다. 그렇다보니 실제 배열에는 값이 담기는 것이 아니라, 그 값을 가리키는 참조값들이 연속적으로 저장되는 것이다. 참조값의 크기는 CPU word size와 동일한데, 64bit python이면 8byte의 크기를 가진다.
더 생각해볼 점
주소값 크기가 32 Byte로 나오는 이유
연결 리스트(Linked list)
배열에서 삽입, 삭제 성능 이슈를 해결하기 위해 고안된 자료구조가 연결 리스트다. 연결 리스트는 데이터가 인덱스가 아닌 여러개의 노드로 연결되어 구성되어있다. 하나의 객체로 볼 수 있는 각 노드에는 다음 노드에 대한 정보를 가지고 있다.
연결 리스트에서의 접근은 가장 첫번째 노드로부터 시작되며, 해당 노드로부터 다음 노드에 대한 정보를 얻어 순차적으로 접근해나가는 방식이다.
다음 노드의 참조값을 통해 순차적으로 접근한다는 것이지 메모리 주소가 실제로 순차적인 것은 아니다.
연결 리스트에서 삽입 및 삭제는, 노드에 대한 연결을 맺어주고, 끊어주기만 하면 된다. 그렇다 보니 노드의 위치를 안다는 가정하에, 삽입, 삭제에서 시간 복잡도는 O(1)의 성능을 보인다.
여기서도 노드의 위치를 모른다면, 결국 조회를 해야하므로 O(n)이 된다 
하지만 특정 노드에 대한 탐색을 할 때는, 맨 앞에서부터 시작하여 노드들을 거쳐가야하므로 조회에서는 O(n)의 느린 성능을 갖게 된다. 이러한 점은 보완하기 위해 노드를 양방향으로 연결하여 조회 성능을 끌어올린 이중 연결 리스트가 있다. 이중 연결 리스트에서 index로 조회시, 앞뒤 중 가까운 곳을 시작점으로 둘 수 있어 조회에서 O(n/2)의 성능을 가질 수 있다.
추가적으로, 이렇게 생성된 노드들의 주소값들은 불규칙적이고 주소간의 간격(stride)가 넓어 공간 지역성은 좋지 않게 된다.
문자열(String)
문자열은 각 문자를 배열로 구현한 자료형이다. 그러나, 기본적으로 문자열은 불변함을 가정한다. 불변함을 가정해서 얻는 이득이 크기 때문이다.
자료구조 vs 자료형
자료구조는 데이터를 효율적으로 저장, 관리, 처리하기 위해 데이터를 조직화하는 방법
자료형은 변수에 저장할 수 있는 데이터의 종류와 그 데이터에 대해 수행할 수 있는 연산을 정의하는 개념
애플리케이션을 개발하다보면 쉽게 생성하고, 반복되는 문자열을 사용할 때가 많다. 예를 들어, HTML을 파싱하는 프로그램을 만든다고 하면, HTML 태그의 특성상 열고 닫는 태그는 동일하다. 또한 해당 태그는 매우 반복적으로 나타날 것이다. 그럴 때마다 문자열 객체를 생성해서 사용하게 된다면, 동일한 문자열이라도 결국 그 문자열 크기만큼 메모리를 사용하게 것이다. 따라서, 문자열의 재사용성을 높이기위해 동일한 문자열은 동일한 객체로 처리하는 방법이 필요하다.
문자열 인턴이 이를 구현하는 방법이다. 문자열 생성시, 특정 문자열에 대한 참조값을 문자열 인턴 풀에 복사해놓고, 반복되어 호출하는 경우에 그 참조값을 재사용하게 된다. 만약 문자열이 변경되면, 다른 문자열을 생성하여 그 문자열의 참조값이 할당되게 되는 것이다. 이를 통해 기존 문자열의 불변성을 보장하면서 새로운 문자열을 생성할 수 있다.
불변성을 통해 쓰레드 안정성을 얻을 수 있다. 문자열이 변경되지 않으므로, 여러 쓰레드가 동시에 접근을 하더라도, 동일한 값을 얻어낼 수 있기 때문이다. 그러나, 문자열 수정시에는 문자열 인턴 풀에 새로운 문자열을 만들어지게 되는데, 이 문자열 인턴 풀을 공유하여 사용하는 경우, 쓰레드 안정성을 얻기 위한 별도의 처리가 필요하다.
생성된 문자열은 같은 참조값을 갖기에, 해시 함수를 거쳐도 동일함을 보장받을 수 있다. 따라서 해시 키(Hash key)로 사용하기 적절한 구조가 된다.
해시 키(Hash key)는 해시 테이블에서 값을 다루는 데 사용하는 데이터이다.
해시 테이블(Hash table)
배열에서는 오직 인덱스로만 데이터를 조회할 수 있는 한계가 있다. 그러나, 우리가 자료를 검색할 때는 사실 문자열로 검색하는 것이 가장 직관적이다. 해시 테이블은 이러한 요구를 만족시킨다.
해시 테이블은 키와 값으로 이뤄져있는 자료구조이다. 여기서 키는 고유한 값을 가지기만 하면 되므로, 다양한 자료형으로 키를 지정할 수 있으며 인덱스를 대체하여 값을 조회할 수 있다.
하나의 해시 테이블에서 여러 자료형의 키를 가지는 것은 아니다.
해시 테이블은 주로 문자열을 키로 가진다. 예를 들어, name 이라는 키에 koesnam를 저장하면, name 이라는 키를 통해 koesnam이란 정보를 조회할 수 있는 것이다. 키를 해시 함수에 적용시켜 저장된 위치를 계산하기에 조회 성능 또한 O(1)로 우수하다. 또한 키를 통해 값을 수정하고 삭제가 가능한데, 이 또한 O(1)으로 배열과 연결 리스트의 장점을 모두 가진 자료구조라고 볼 수 있다.
Swift, Python에서는 Dictionary로 Java에서는 Map으로 정의되며 HashMap, TreeMap 등 다양한 구현체가 있다.
배열에서는 직접 접근을 통해서 빠른 조회가 가능했다. 하지만 해시 테이블은 어떻게 가능할까. 결론부터 말하자면, 해시 테이블 또한 버킷에 대한 직접 접근을 하기 때문이다. 해시 테이블에 값을 삽입하면, 해당 키 값이 해시 함수를 거치게 되고, 그에 대한 결과값이 버킷의 인덱스가 되어 값을 저장시킨다.
버킷은 값들이 담긴 배열을 가리킨다.
출처 : tutorialspoint
해시 함수에는 여러가지가 있지만 그 중 간단한 나눗셈 해시 함수, 문자열 해시 함수를 살펴보자. 나눗셈 해쉬 함수는 키 값을 테이블 크기로 모듈러 연산을 하는 함수이다. 문자열 해시 함수는 키 값이 문자열 일 때, 각 문자열에 가중치를 부여하여 곱한 뒤 다 더하는 연산을 하는 함수이다.
나눗셈 해쉬 함수
문자열 해시 함수
여기서 문제는 해시 함수를 거친 값이 동일할 경우이다. 이러한 경우를 해시 충돌이라고 하는데, 이렇게 해시값이 충돌되면 결국 기존 값을 업데이트 시키기 때문에 해시 테이블이 제 역할을 할 수 없게 된다. 하지만 해시 충돌은 자료구조의 크기가 유한하므로 발생할 수밖에 없는 문제이다. 따라서 해시 충돌을 다루기 위한 방법으로, 오픈 어드레싱(Open Addressing) 방법과, 체이닝(Separate Chainning) 기법이 있다. 이 둘의 차이점은 기존의 버킷을 재활용하느냐, 아니면 새로운 자료구조를 생성하느냐에 있다.
오픈 어드레싱 방법에는 세가지가 있는데, 그 중 하나는 선형 탐사(linear probing)이다. 해쉬 충돌 발생시 버킷의 다음 데이터로 넘어가고, 해당 값이 비어있으면 그곳에 충돌난 데이터를 삽입하게 된다. 따라서 이 때부터 성능은 O(1)이 아닌 충돌난 횟수에 의존하게 된다.
체이닝 기법은 충돌난 곳에 연결 리스트를 생성하여 연결한다. 충돌 발생시 키 값을 통해 연결 리스트를 조회하게 될 것이고, 연결 리스트에서 순회하여 값을 조회하게 된다. 이로써 성능 또한 연결 리스트의 성능을 가지게 된다.
Python에서는 오픈 어드레싱 방식을 채택하여 Dictionary가 구현된 것이고, Java에서는 체이닝 기법을 통해 구현되어 있다. 특히나 Java에서는 체이닝 기법을 채택하면서, 그 내부적으로는 충돌 갯수에 따라 자료구조를 연결 리스트와 RB트리로 변경시켜가며 사용하고 있다.
버킷에 데이터가 들어있는 비율을 부하 계수(Load Factor)라고 정의하는데, 이 부하 계수가 체이닝 기법에서는 선형적으로 증가하나, 오픈 어드레싱 기법에서는 1에 가까울수록 엄청나게 성능이 나빠진다. 따라서 부하 계수가 0.6 ~ 0.75를 유지할 수 있게끔 버킷의 리사이징이 필요하다. 이로 인해, 파이썬에서는 부하 계수가 0.6이 넘어가면 리사이징을 2배 또는 4배로 진행한다.
출처 : https://en.wikipedia.org/wiki/Hash_table
마무리
이 글에서는 자료구조의 기본이 되는 배열, 연결 리스트를 다뤘다. 추가적으로, 메모리 운용 방식이 추가된 자료형인 문자열과 독특한 키-밸류 구조의 해시 테이블도 살펴보았다. 배열은 순서가 있는 데이터를 빠르게 조회할 수 있었지만, 삽입과 삭제에서 성능이 저하되는 반면, 연결 리스트는 삽입과 삭제가 빠르지만 조회 성능이 떨어지는 특성이 있었다.
문자열은 불변성을 통해 메모리 사용을 최적화하고 쓰레드 안전성을 제공하며, 해시 테이블은 키를 이용해 빠른 데이터 조회가 가능하지만 해시 충돌 문제를 해결하기 위해 오픈 어드레싱이나 체이닝 기법을 사용했다. 각각의 자료구조는 고유의 장단점을 가지고 있었으며, 그 특성을 이해하고 문제 상황에 맞게 선택하는 것이 중요할 것이다.