추상자료형이란?
-기능 구현 방법에 대해 명시하지 않고 순수한 데이터(자료)의 구조와 연산에 대한 명세이다.
구현 방법은 명시하지 않는다는 점에서 자료구조와 다르다.
✏️ 데이터 구조 기본 재료 : 배열 & 연결리스트
- 배열
구성 : 베이스 + 오프셋- 연결리스트
구성 : 명(시작 위치) + 크기(노드 수)
연결 리스트는 동적 메모리 할당
연결 리스트 종류 : 단일, 이중, 원형 등
해시 함수란?
-임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.
해싱
-해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다.
-해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법
-해싱이 어디에 쓰이는가? 최적의 검색이 필요한 분야, 심볼테이블등의 자료구조를 구현하기에도 적합
-해싱에는 다양한 알고리즘이 있으며, 최상의 분포를 제공하는 방법은 데이터에 따라 제각각이다.
성능이 좋은 해시 함수란?
-충돌이(해싱값이 동일하게 나오는것) 최소화
-쉽고 빠른연산
-해시 테이블 전체에 해시 값이 균일하게 분포
-사용할 키의 모든 정보를 이용하여 해싱
-해시 테이블 사용 효율이 높을 것
해시 함수에서 충돌이 그렇게 빈번하게 나올 수 있는가?
-ex) 생일 문제
생일의 가짓수는 365개 이므로, 여러 사람이 모였을 때 생일이 같은 2명이 존재할 확률을 얼핏 생각해보면, 366명 이상이 모여야 일어나는 일 같다.
하지만 실제로는 23명만 모여도 50%를 넘고, 57명이 모이면 그때부터 99%를 넘어선다.
```
def test_birthday_problem():
import random
TRIALS = 100000
same_birthdays = 0
for _ in range(TRIALS):
birthdays = []
for i in range(23):
birthday = random.randint(1, 365)
if birthday in birthdays:
same_birthdays += 1
break
birthdays.append(birthday)
print(f"{same_birthdays / TRIALS * 100}%")
if __name__ == "__main__":
test_birthday_problem()
test_hashtable()
```로드 팩터 : 해시테이블에 저장된 데이터 개수(n)을 버킷의 개수로나눈 것이다.
load factor = n/k
로드 팩터가 증가할 수록 해시테이블 성능은 점점 감소하게 된다.
자바10의 경우, 0.75를 넘어설 경우, 해시 테이블의 공간을 재할당 한다
정수형 해싱 기법- 모듈러 연산을 이용한 나눗셈 방식
h(x)= x mod m
- m은 해시 테이블의 크기로, 일반적으로 2의 멱수(2의 제곱수)에 가깝지 않은 소수를 택하는 것이 좋다
1. 해시테이블의 구현 방법
-충돌에 대처하는 방식에 따라 2가지 종류로 나뉜다
1)개별 체이닝
: 충돌시, 동일한 해시값에 연결리스트 방식으로 저장해준다.
개별 체이닝의 원리
- 키의 해시 값을 계산한다
- 해시 값을 이용해 배열의 인덱스를 구한다
- 같은 인덱스가 있다면 연결 리스트로 연결한다.
**잘 구현한다면 대부분의 탐색은 O(1)이지만, 최악의 경우, 즉 모든 해시 충돌이 발생했다고 가정할 경우에는 O(n)이 된다.
2) 오픈 어드레싱
: 충돌시, 탐사를 통해 빈 공간을 찾아서 선형 탐사를 진행한다.
-해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다.
-버킷 사이즈보다 큰 경우에는 삽입할 수 없으므로 오류가 난다.
** 해시 테이블로 구성된 파이썬의 자료형은 : 딕셔너리 !
딕셔너리는 오픈 어드레싱 방식으로 구현되어 있다.
2. 해시 테이블의 시간 복잡도
- insertion
- deletion
- search
->모두 O(1) 의 값을 갖는다.
