[자료 구조] Python으로 알아보기 : Collection Framework

Collection Framework란?

다수의 데이터를 쉽고 효과적으로 처리할 수 있도록 표준화된 방법을 제공하는 클래스의 집합이다.

파이썬에서는 Data Types 또는 Collection Data Type이라고 부름

• 인터페이스 구조
  
  •  
  • List (리스트)
    • 데이터가 들어온 순서를 기억함
    • 같은 값을 여러 번 넣을 수 있음
    • 인덱스 접근이 가능하고 빠르게 접근이 가능함
  • Set (집합)
    
    • 중복을 허용하지 않는다. (고유한 값만 유지)
    • 데이터 넣는 순서를 보장하지 않아 인덱스로 접근이 불가능함
  • Map(맵)
    • 데이터를 Key - Value의 쌍으로 저장 (Key = 이름, Value = 값)
    • Key는 중복될 수 없으며, 중복되면 기존의 Value를 새로운 Value로 덮어쓰게 됨

---

1. List-based Collection Framework

일종의 순서가 있는 데이터의 집합으로 중복을 허용하는 선형적인 자료구조를 뜻함

인덱스로 요소에 접근가능하며, 데이터의 순서를 가지고 있음

• 리스트의 종류
  • ArrayList
    • 내부적으로 배열을 사용하여 인덱스 조회가 매우 빠름
  • LinkedList
    • 요소들이 포인터로 연결됨
    • 삽입/삭제가 빠르지만 인덱스 접근이 느림
  • Vector
    • ArrayList와 비슷하나 멀티스레드 환경에서 안전함 (동기화)

파이썬에서의 List

• 파이썬은 C/Java의 '정적 배열(Static Array)'개념을 별도로 구분해서 사용하지 않고, 이를 확장한 리스트를 기본 자료형으로 채택하고 있다. 따라서 배열의 빠른 접근성과 리스트의 유연한 크기 조절을 동시에 누릴 수 있음.
• 하나의 리스트에 int, char, String, List등 서로의 다른 타입을 섞어서 담을 수 있는 유연함을 가지고 있음. 

ArrayList 

기본적으로 사용하는 배열을 사용해서 구현 가능

arr_list = []
#데이터 추가
arr_list.append(1)
arr_list.append(2)
arr_list.append(3)
#데이터 삭제
arr_list.pop()
arr_list.pop(0) #인덱스 접근하여 pop이 가능
#데이터 찾기
arr_list.index(2) # O(n)의 시간 복잡도를 가짐
flag = 2 in arr_list # 2라는 인덱스가 있는 없는지 확인 O(n)의 시간복잡도

LinkedList

삽입과 삭제가 빠른 이유는 내부를 형태를 통해 알수 있게 되는데 객체는 다음의 정보를 가지고 있음

• 노드
  • 값
  • 이전노드
  • 다음노드

노드는 해당 노드의 값과 이전 노드와 다음 노드를 가지고 있는데 아래 그림과 같은 형태임

각 노드들이 포인터로 연결됨을 설명한 것으로 이전 노드와 다음 노드가 가지는 값은 포인터(주소값)을 가지게 된다.

더블 링크드 리스트

 

삭제는 아래 그림과 같은 형태로 이루어지며 삭제할 노드의 연결을 끊고 1번노드와 3번노드를 연결한다

링크드 리스트 삭제

삽입은 아래 그림과 같은 형태로 이루어지며 각 사이의 노드의 연결을 끊고 새로운 노드와 연결하는 방식

링크드 리스트 삽입

빠른 삽입/삭제를 원해 LinkedList를 원한다면 deque를 사용하여 구현

 

Vector

ArrayList와 크게 다르지 않으며 내부의 공간이 없으면 자동으로 확장 해줌

• 인덱스를 통한 접근은 시간 복잡도 O(1), 중간 삽입 & 삭제 O(n)
• ArrayList와의 차이점 모든 메소드가 동기화 되어있음
  • 동기화란 쓰레드의 접근을 한번에 하나만 제한하는 것
• 멀티쓰레드 환경에서 안정성이 높은 특징을 가지는 구식 클래스
• 단일 동기화에서도 락을 얻고 처리하는 방식이기에 ArrayList보다 느림.
• 하지만 접근하는 메소드 단위의 자동 동기화는 의도치 않은 결과를 낼 수 있기 때문에 ArrayList를 사용하고 외부쓰레드 동기화처리하는 것이 더욱 안전하며 빠름의도치 않은 결과의 예시 (size()작동 후 마지막요소 가져오기)두 기능사이에는 동기화되어있더라도 그 사이에 다른 작업이 일어날 가능성 또한 존재

List 구현체 요약

• ArrayList : 가장 많이 사용되는 구현체인덱스 기반 접근 O(n)
  
  • 메모리를 연속적으로 배치해서 캐시 효율 좋음
  • 끝에서의 추가 & 삭제 O(1)
• ListedList  : 많은 양의 추가 & 삭제노드의 위치를 직접 알고 있을 때 한정 삽입 & 삭제 O(1)
  
  • Queue나 DeQueue에 사용됨
  • Vector멀티 쓰레드 환경에서 안정성 높은 특징을 가진 구식 클래스
  • ArrayList가 더 빠르거나 동일한 성능을 가질 수 있어 ArrayList를 사용하는 것이 좋다.
• 적합한 문제 유형 : 동적 배열 구현, 배열 회전, 리스트 정렬, 두 리스트 병합, 중복 제거

---

2. Set-based Collection Framework

중복을 허용하지 않는 데이터의 집합으로 빠른 검색과 중복을 제거하는 특징이 있음

특정한 값이 존재하는지 확인하는 작업이 리스트보다 빠름

기본적으로 내부적으로 hash table 사용하여 값을 hash함수로 변환해서 임의의 위치에 저장하기 때문에 삽입 순서를 보장하지 않음

 

Set의 종류

• HashSet
  • 가장 기본이 되는 Set
  • 삽입 순서 보장 안됨
  • 성능이 가장 빠름 O(1)
• LinkedHashSet
  
  • 삽입 순서 보장 해줌
  • HashSet보다 약간 느림
• TreeSet
  • 값을 넣으면 자동으로 오름차순 정렬을 해줌
  • 이진 탐색 트리 구조 O(log N)

HashSet

삽입, 삭제, 검색 모두 평균적으로 O(1)

충돌이 잦아질 땐 O(n)까지의 성능 저하 가능성 있음

• hash(값) % tableSize 와 관련이 있음 단순하게 % 연산만 이러나지 않
  • 삽입 : hash(값) % tableSize의 값이 나오는 곳에 저장 따라서 중복 값은 걸러질 수 있음
  • 삭제 : hash(값) % tableSize의 값이 나오는 곳이 가진 값 삭제
  • 검색 : hash(값) % tableSize의 값이 나오는 곳의 값을 반환
• 해쉬 충돌
  • ex) 10 % 8 과 18 % 8은 동일한 2을 가짐 따라서 같은 곳에 다른 값을 넣는 충돌이 발생함
  • 충돌 해결 방법
    • 체이닝 : 해당 칸에 LinkedList를 사용해 한곳에 여러 값이 들어갈 수 있도록 관리
    • 개방 주소법 : 충돌시 옆의 빈 칸으로 할당하는 방
• 메모리 관리 측면
  • 실제 데이터보다 더 많은 공간을 필요로 함
  • hash table은 충돌을 줄이기 위해 배열에 일부 빈 공간을 유지함
  • 유지 할땐 로트팩터라는 개념으로 0.75정도 유지 하도록 함(Capacity와 같은 원리)
  • 즉, 배열의 75%정도가 차면 크기 2배로 늘림(늘리는 과정을 Rehashing)
  • 또한 충돌 처리를 위한 추가적인 구조가 필요
• 사용 케이스
  • 순서가 중요하지 않지만, 빠른 중복 제거와 검색이 필요한 경우

Set 예시

#hashSet 선언
s1 = set()
s2 = set([1,2,3,1,2,5])
s3 = {1,2,3} # {}빈괄호일 땐 딕셔너리(Map)로 인식됨
#값 추가
s1.add(1)
s1.add(2)
s1.add(3)
s1.add(1) # 중복허용 안됨
s1.add(4)
#검색
flag = 2 in s1
for i in s1:
    print(i)
#삭제
s1.remove(2) #없는 값을 삭제하면 error 발생
s1.discard(6) # 없는 값을 삭제해도 error 발생 안함
s1.pop() # 순서가 없기에 임의의 값 삭제

 

LinkedHashSet

기본적으로 HasSet + 삽입 순서 유지

이중 테이블 + 이중 연결 리스트 사용

원리

• 각 요소는 해시테이블에 저장되면서 동시에 연결 리스트의 노드로도 연결
• 새 요소를 추가하면, 해시테이블의 적절한 위치에 저장을 하고 동시에 연결 리스트의 끝에 추가
• 해시 테이블을 통한 검색  O(1)
• 연결리스트로 순서 유지 따라서 순회는 O(n)
• 메모리 관리 측면
  • 프리브, 넥스트 포인트를 제공해야하기 때문에 HashSet보다 더 많은 메모리를 사용

파이썬에선 크게 3가지의 방법으로 구현함

• 외부라이브러리 사용 (from collections import OrderedDict)
• 직접 체크하며 추가 (set과 리스트 두가지를 사용)
• dict 활용 ( 파이썬 3.7부터는 딕셔너리가 순서를 보장해줌)

#LinkedhashSet 직접체크하면서 추가
seen = set()
ordered_list = []

def add_element(val):
    if val not in seen:
        seen.add(val)
        ordered_list.append(val)

#LinkedhashSet2 딕셔너리 활용
ordered_set_dict = {}

ordered_set_dict[3] = None
ordered_set_dict[1] = None
ordered_set_dict[2] = None
ordered_set_dict[3] = None

print(list(ordered_set_dict.keys()))

 

TreeSet

이진 탐색 트리 기반의 구조로 내부적으로 레드 블랙 트리라는 자가 균형 이진 탐색 트리 사용

• 트리구조로 자동 정렬 구조 제공
• 요소 추가시에 내부적으로 올바른 위치에 삽입
• 왼쪽 트리에는 현재 노드보다 작은 값 오른쪽 트리에는 현재 노드 보다 큰 값으로 중위 순회를 통한 오름차순
• 삽입, 삭제, 검색 모두 O(log n)
  • 트리구조에 따라 내려가면서 적절한 위치를 찾고 트리 높이는 log n이기 때문에 최대 log n의 비교로 위치 선정
• 범위 검색이 가능하다는 점이 장점
• 메모리 측면
  • 각 요소마다 트리노드를 저장해야함 (왼쪽 자식, 오른쪽 자식, 부모 노드 참조 저장)
  • 따라서 hashSet보다 메모리를 더 많이 사용
• 저장하는 값 자체가 정렬과 범위 검색이 필요할때 사용
• Compatible 인터페이스를 구현한 개체만 저장가능
  • 요소들을 비교하여 정렬하기 때문에 비교 방법 정의가 필요

파이썬의 TreeSet

• 외부라이브러리 (SortSet)
• bisect를 이용한 구현

기본적인 예시

import bisect

class TreeSet:
    def __init__(self, iterable=None):
        self._data = sorted(set(iterable)) if iterable else []
        self._set = set(self._data)

    def add(self, value):
        if value not in self._set:
            self._set.add(value)
            index = bisect.bisect_left(self._data, value) # O(log n)
            self._data.insert(index, value)              # O(n)

    def __repr__(self):
        return str(self._data)

파이썬엔 따로 TreeSet이 없어도 될 만큼 리스트와 힙이 너무 빠르고 파이썬은 이미 객체가 무거운 편이라 트리구조까지 표준으로 강제하면 메모리 오버헤드가 너무 커짐

따라서 직접 구현해야하지만 TreeSet보다 느림

---

3. Map-based Collection Framework

Key-Value로 저장되는 자료구조로 Key는 고유한 값을 가진다. 따라서 Key는 Set와 의존 관계임

주요 용도는 연관관계를 표현하는데 있음

빠른 검색에도 유용

 

Map의 종류

• HashMap
  
  • 가장 빠르고 순서 보장 안함
• LinkedHashMap
  • 삽입 순서를 유지
• TreeMap
  
  • Key를 기준으로 자동 정렬
• HashTable
  • HashMap과 거의 동일하며 Thread-safe (동기화) 지원
  • 요즘 잘 사용 안

HashMap

해시 테이블을 기반으로 구현된 Map

• hash("name") %  size
• 해쉬 충돌도 set과 동일

파이썬에선 딕셔너리 (dict)로 사용

#딕셔너리 선언
dic = {}
dic1 = {"banana" : "바나나", "apple" : "사과"}
#값 추가
dic["banana"] = "바나나"
dic["apple"] = "사과"
dic["banana"] = "버네너" #중복된 키로 접근하면 값을 덮어씀
#삭제
del dic["apple"]
dic1.pop("apple")
#접근
print(dic["banana"])
flag = "apple" in dic #False를 반환
#배열로 꺼내기
keyArr = list(dic.keys())
valueArr = list(dic.values())
for i in dic:
    print(i) #key값

 

LinkedHashMap

삽입 순서를 유지하는 Map

파이썬 3.7부턴 dict에 순서를 보장함

LRU ( Least Recently Used ) Cache에 사용됨

가장오랫동안 사용되지 않은 데이터를 제거하는 캐시알고리즘

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}

    def get(self, key):
        if key not in self.cache: return None #키가 없다면 반환

        value = self.cache.pop(key)
        self.cache[key] = value #최근사용으로 갱신
        return value

    def put(self, key, value):
        if key in self.cache:
            self.cache.pop(key)

        self.cache[key] = value
        #용량 초과시
        if len(self.cache) > self.capacity:
            firstKey = next(iter(self.cache))
            del self.cache[firstKey]

 

TreeMap

TreeSet과 동일하게 key값의 순서를 정렬 유지하는 Map

이진 탐색 트리 기반으로 구현

파이썬에선 없기에 sort를 활용하는 거나 bisect를 사용해도됨

---

번외. 해쉬함수

해쉬 함수란 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수

h(key)→index

 

해시 데이블에서의 역할

key를 해쉬함수를 통해 해쉬테이블 인덱스로 넣는 작업을 진행해줌

 

해시 함수의 핵심 성질

• 결정성
  • 같은 입력이 들어온다면 항상 같은 출력
• 고정 출력
  • 입력 크기와 무관하게 출력 크기 일정
• 빠른 계산
  • O(1)에 가까운 연산 속도
• 균등 분포
  • 해시값이 테이블 전체에 고르게 퍼져야함

해시 함수는 다음과 같은 방법이 존재

• 나눗셈
• 곱셈법

해시 함수의 나눗셈법 (Division Method)

해시 함수를 만드는 가장 간단한 방법 중 하나

h(k) = k mod m

이때 다음과 같이 충돌을 방지하기 위한 주의 사항이 있음

• m은 2의 거듭제곱을 피해야 한다
• m은 10의 거듭제곱을 피해야 한다
• m은 소수(Prime)이 좋다

2의 거듭제곱을 피해야하는 이유

m이 2의 거듭제곱이면, k mod m은 k의 하위 비트 p비트만 사용하게 됨

예시: m = 8 (= 2^3)

k = 1000  → 이진수: ...1111101000  → 하위 3비트: 000  → h(k) = 0
k = 1008  → 이진수: ...1111110000  → 하위 3비트: 000  → h(k) = 0  💥충돌
k = 1016  → 이진수: ...1111111000  → 하위 3비트: 000  → h(k) = 0  💥충돌

 

예시처럼 키값이 m과 같은 8의 배수거나 하위 비트 3비트가 동일한 패턴이면 모두 같은 버킷으로 몰림

따라서 상위 비트의 정보를 완전히 무시하는 현상이 생김

실제로 메모리 주소, 구조체 크기,  배열 인덱스 등은 정렬때문에 8이나 16의 배수인 경우가 많음

 

10의 거듭제곱을 피해야하는 이유

m이 10의 거듭제곱이면, k mod m은 k의 하위 p자리 십진수만 사용하게 됨

예시: m = 100 (= 10^2)

k = 1234  → h(k) = 34
k = 5634  → h(k) = 34  💥충돌
k = 9934  → h(k) = 34  💥충돌

위와 같이 십진수 상위 자리 정보를 완전히 버리게 되는데 사람이 입력하는 숫자 데이터(전화번호, 학번, 우편번호 등)끝자리가 비슷한 패턴을 가지기 쉬움

 

Prime을 사용하는 이유

소수는 약수가 1과 자기 자신뿐이라는 성질 덕분에, 키의 특정 패턴이 해시값에 미치는 영향을 분산시킴

예시: 키 = {0, 6, 12, 18, 24, 30} (공차 d=6)

m = 12 (비소수, gcd(6,12)=6):
  → 나머지: 0, 6, 0, 6, 0, 6  ← 버킷 2개에만 몰림! 💥

m = 11 (소수, gcd(6,11)=1):
  → 나머지: 0, 6, 1, 7, 2, 8  ← 6개 버킷에 분산 ✅

m과 d가 공약수를 가지면 해시값도 주기적인 패턴이 발생함에 따라 특정 버킷에 집중된다

하지만 m이 소수라면 d가 m의 배수가 아닌 이상 공약수는 1밖에 없음 따라서 해시값이 m개 버킷에 고르게 분포 가능

 

해시 함수의 곱셈법 (Multiplication Method)

나눗셈법에 비해 해시 테이블의 크기 m의 선택에 덜 민감하다는 장점이 존재

m의 선택에 덜 민감한 이유는 A가 분산을 담당하고, m은 단순 스케일링만 하기 때

무리수의 등분포 성질을 이용한 것

h(k)=⌊m×(kAmod1)⌋

이론적 한계와 주의점

• A의 민감성이 존재
• 곱셈법의 품질은 A값에 따라 달라짐
• 좋은 A의 조건
  • 무리수여야함 (주기적 패턴 방지)
  • 유리수 근사가 어려워야 함
  • 계산하기 쉬운 비트 패턴 (구현 효율에 영향줌)
  • 추전 값은 A = (√5 - 1) / 2 ≈ 0.6180339887

 

단계별 계산 과정

예시 : k = 123, A = 0.6180339887, m = 100

• kA 계산
  • kA=123×0.6180339887=76.01818
• 소수부분만 추출 (kA mod 1)
  • kA mod 1=76.01818−76=0.01818...
• m을 곱하고 floor
  • h(k)=⌊100×0.01818⌋=⌊1.818⌋=1

	나눗셈법	곱셈법
분산 이론	정수론 (공약수)	해석학 (등분포 정리)
취약점 원인	m과 키의 대수적인 관계	A가 나쁜 유리수에 가까울 때
최악의 입력	m의 배수 패턴 키	A의 배수 패턴 키 (거의 없음)
이론적 보장	m이 소수면 보장	A가 무리수면 접근적 보장
실제 구현	mod 연산 (느림)	곱셈 + shift(2의 거듭제곱 사용시 빠름)