파이썬 List는 과연 무엇인가?

파이썬의 리스트는 무엇이고, 다른 언어와 무엇이 다를까?

파이썬에서 list는 가장 자주 쓰이는 자료구조 중 하나로, 가변적이고 다양한 자료형을 저장할 수 있는 배열 형태입니다.

언어	배열/리스트의 특징
Python (list)	가변(mutable) 다양한 타입 섞어서 저장 가능 내부적으로는 포인터 배열 (값 참조)
C / Java / C++	고정 타입의 배열 크기 지정 필요 (ex: int[10]) 메모리 효율적이지만 유연성은 낮음
JavaScript (Array)	유연한 배열 구조 다양한 타입 가능하지만 성능은 엔진에 따라 다름

즉, 파이썬의 리스트는 “배열처럼 쓰이는 동적 구조체”라고 볼 수 있으며,
메모리 구조와 캐시 활용 측면에서는 C나 Java의 array 와 다르게 동작합니다.

이러한 리스트가 파이썬 내부에서 어떻게 해시 테이블처럼 활용되는지도 이 글에서 이어서 설명합니다.

 

 

파이썬 딕셔너리와 해시 테이블 내부 구조

파이썬에서 dict나 set은 내부적으로 해시 테이블(Hash Table)을 사용합니다.
키를 빠르게 찾기 위해서는 먼저 hash() 함수를 통해 해시값을 계산한 뒤, 배열의 인덱스로 매핑하여 접근합니다.

📌 컬리전(Collision) 이란?

hash("abc") = 123
hash("xyz") = 123

서로 다른 키가 같은 해시값을 가지면 충돌(Collision)이 발생합니다.
파이썬은 이를 오픈 어드레싱(open addressing) 방식으로 해결합니다.

오픈 어드레싱	충돌 해결 방식
선형 탐사	한 칸씩 이동 (+1, +1, …)
이중 해싱	일정 간격으로 이동 (+f(k), +f(k), …)
파이썬 방식	변형된 오픈 어드레싱 + 이중 해싱 조합

방식	설명
체이닝	같은 해시값에 연결 리스트로 값들을 저장
오픈 어드레싱	빈 슬롯을 찾아 다른 위치에 저장 (파이썬 사용)

✅ 해시 키 조건

• 불변(immutable)해야 함
• __hash__() 메서드를 가지고 있어야 함

예: 해시 키로 가능한 타입들

타입	가능 여부	이유
int	✅	불변이고 해시 가능
str	✅	불변이고 해시 가능
tuple	✅	불변일 경우
list	❌	가변이라 해시 불가
dict	❌	가변이라 해시 불가

✅ 딕셔너리와 튜플

딕셔너리는 key-value 형태로 데이터를 저장합니다.
자바스크립트의 객체, 자바의 맵과 유사한 구조입니다.

student = {
  "name": "Alice",
  "age": 20,
  "major": "Computer Science"
}

튜플은 변경 불가능한 자료형이기 때문에 딕셔너리의 키로 사용할 수 있습니다.

position_data = {
  (0, 0): "snake_head",
  (2, 3): "apple",
  (5, 1): "obstacle"
}

print(position_data[(2, 3)])  # 출력: "apple"

✅ list vs array 차이

list	array (array 모듈)
다양한 타입 저장 가능	동일한 타입만 저장 가능
속도는 느릴 수 있음	숫자 계산에 빠르고 메모리 효율적
포인터 배열 (값의 참조)	타입 코드 지정 (ex: 'i', 'f')

✅ 해시 테이블 구조

파이썬의 dict는 실제로는 배열 기반의 구조입니다.
해시값을 인덱스로 매핑하여 데이터를 저장합니다.

[ (key1, value1), (key2, value2), None, (key3, value3), ... ]

✅ 해시 사이즈가 작을 때

• 충돌이 증가
• 탐색/삽입 속도 저하
• 리사이징 발생 → 성능 개선

로드 팩터 (Load Factor)

테이블이 얼마나 차있는지를 나타내는 비율

Load Factor = 저장된 원소 수 / 전체 슬롯 수

언어별 로드 팩터 예시

언어	로드 팩터 한계	설명
Python	0.66	초과 시 자동 리사이징
Java	0.75	기본값 기준 리사이징
C++	0.5~1.0	수동 조정 가능

✅ 오픈 어드레싱의 장점

• 메모리 구조 단순화
• 작은 dict에 최적화
• 캐시 지역성 우수
• 삭제 및 탐색 효율적

✅ 캐시 지역성 (Cache Locality)

CPU는 자주 사용하는 데이터를 RAM 대신 빠른 캐시에 저장합니다.

지역성(Locality) 종류

종류	설명	예시
시간 지역성	같은 데이터를 반복 접근	루프에서 동일 변수 반복
공간 지역성	인접 데이터 접근	리스트 순회

오픈 어드레싱은 배열 기반이기 때문에 캐시 적중률이 높고 성능이 좋습니다.
체이닝은 포인터 따라가야 하므로 캐시 미스가 자주 발생합니다.

✅ range() vs 리스트 순회

비교 항목	리스트	range()
메모리 사용	모든 값 저장	필요할 때 생성
속도	약간 빠름	거의 동일
대량 데이터	비효율적	매우 효율적

단순 반복 목적이라면 range()가 메모리적으로 더 효율적입니다.