Python 딕셔너리의 메모리 관리 구조(a.k.a hash table)

 

1. 딕셔너리 생성 후 해시 테이블 기본 형태

인덱스	해시 값	키	값
0	None	None	None
1	None	None	None
2	None	None	None
3	None	None	None
4	None	None	None
5	None	None	None
6	None	None	None
7	None	None	None

 

(처음 딕셔너리가 만들어지면 이런 식으로 인덱스만 결정된 채 나머지 데이터는 비어있는 상태의 8행의 테이블이 만들어진다고 한다.)

 

2. 값이 입력 되었을 때 해시 테이블의 형태

인덱스	해시 값	키	값
0	34891759823412	'Alice'	'010-1234-5678'
1	45981769173452	'Bob'	'010-2345-6789'
2	58917234123412	'Carol'	'010-3456-7890'
3	None	None	None
4	None	None	None
5	None	None	None
6	None	None	None
7	None	None	None

(편의에 의해 인덱스 순서대로 입력하였지만, 꼭 순서대로 입력되진 않는다고 한다.)

 

 

하나의 행을 '슬롯'이라고 한다.

 

저기서 만약 'Alice'를 찾으면 

 

'Alice' -> Hash Function(명시되어 있진 않고 내부적으로 구현되어 있음) -> 계산된 해시 값을 바탕으로 인덱스를 도출하는 함수로 인덱스 매칭 -> 키 값인 'Alice'가 일치하는지 확인 후 값 반환

 

이 절차를 통해 값을 찾게 된다.

 

 

 

 

< 특징 >

 

1. 빠른 검색 (O(1)...!!)

 

해시 함수를 통해 직접 인덱스를 계산. 따라서 순차 탐색 속도인 O(n) 보다 훨씬 빠르다. 

 

2. 충돌 관리

 

해시 값과 키를 함께 저장해 충돌 시 키 검증 가능

 

3. 빈 슬롯 재활용

 

삭제된 슬롯이 있으면 해당 슬롯까지 삭제하진 않고 후에 자동으로 재사용된다. 따라서 메모리 낭비를 최소화할 수 있다.

 

4. 슬롯 수 확장

 

데이터가 많아질 수록 슬롯 수가 자동으로 확장된다. 

 

슬롯 수가 확장되면(행의 개수가 증가하면)  인덱스도 다시 결정된다.

 

 

cf) 해시 충돌

해시 충돌이란 키가 다른데 인덱스가 같은 경우를 말한다.

 

해시 값이 다른데도 불구하고 인덱스 연산 구조에 따라 같은 값이 나올 수도 있다고 한다.

 

 

cf) 해시 충돌 해결

(1) 체이닝(Chaining)

 

같은 인덱스에 리스트를 저장

충돌이 발생하면 리스트를 만들어 충돌 대상의 키, 값을 모두 추가. 검색 시 리스트 내부에서 모든 키를 비교

 

index_4 = [('Alice', '010-1234-5678'), ('Bob', '010-2345-6789')]

(이런 식으로)

 

 

(2) 오픈 어드레싱(Open Addressing)

 

충돌 시 충돌하는 대상의 테이블 내 데이터를 빈 슬롯에 이동.

 

 

(3) 고품질의 해시 함수 사용

 

해시 값이 인덱스 계산에 영향을 미치니(즉, 함수의 input이 output에 영향을 주니)

 

해시 값을 만들어내는 해시 함수를 고품질로 사용하는 방법을 생각할 수 있다. 

 

파이썬은 SipHash라는 강력한 해시 함수를 사용한다고 한다.

 

강력한 해시 함수란, 해시 충돌을 최대한 줄이고 보안성을 높인 해시 함수라고 보면 된다.

 

 

cf) 인덱스와 메모리 주소

인덱스는 해시 테이블 내부의 논리적 위치를 말한다. 물리적 메모리 주소와는 다름.

 

인덱스 = 사물함 번호

메모리 주소 = 사물함의 실제 위치(공간좌표)