해시 (Hash)
- 키 (key)와 값 (value)를 매핑하여 데이터를 저장하는 자료구조
(python에서는 기본으로 제공되는 딕셔너리 자료형이 해시 테이블의 구조) - 해시 테이블은 해시 함수를 사용해 색인 (index)을 버킷 (bucket)이나 슬롯 (slot)의 배열로 계산
- 데이터를 다루는 기법 중 하나로 데이터 검색과 저장이 빠르게 진행
- 용어
- 키 (key) - 고유의 값으로 해시 함수의 input이고, 다양한 길이를 가짐
- 해시 테이블 (Hash table) 또는 해시 맵 (Hash map) - key 와 value를 매핑하여 데이터를 저장하는 자료구조
- 해시 함수 (Hash function) - 임의의 값을 고정된 길이의 데이터로 변환하는 함수.
다양한 길이의 키를 고정된 길이의 해시로 변환하여 저장소에 저장 - 해시 (Hash) - 해시 함수의 output으로 해시 값과 매칭되어 버킷에 저장
- 해시 값 (Hash value) or 해시 주소 (Hash address) - 키에 해시 함수를 적용하여 얻는 해시 값
- 버킷 (Bucket) 한 개의 데이터를 저장할 수 있는 공간
Keys | Hash function | Hash value | Bucket |
John | 01 | 123-4567 | |
Smith | 03 | 123-7896 | |
Joanah | 17 | 123-2103 |
위의 표에서 보면 다양한 길이를 갖는 Key 값에 Hash function을 적용해 고정된 길이의 데이터(01, 03, 17)로 변환
이렇게 변환된 데이터가 해시 값 (Hash value)이고 버킷에는 키와 매핑된 원래 데이터가 저장
결론 - 변환된 키 값과 버킷에 매핑되어 있는 데이터를 해시라 하고 이러한 자료 구조를 해시 테이블이라고 한다
- 특징
- 시간복잡도가 O(1)로 데이터 저장 및 읽기 처리 속도가 매우 빠름
(배열의 인덱스처럼 해시 함수를 통해 얻은 키 값으로 위치 탐색) - 하지만, 무조건 O(1)의 복잡도를 갖는 것은 아님
- 최악의 경우 O(n)의 복잡도를 갖는데, 이유는 충돌 (collision) 때문
- 시간복잡도가 O(1)로 데이터 저장 및 읽기 처리 속도가 매우 빠름
- 충돌 (collision)
- 여러 개의 키 값이 해시 함수를 통해 같은 해시 값을 갖는 경우
- 해결 방법
- Chaining - 충돌 발생 시 버킷에 연결리스트 자료 구조를 통해 데이터를 연결하여 해결
- Open Addressing - 충돌 발생 시 빈 버킷을 찾아 데이터를 저장
- 선형 탐색 (Linear Probing) - 충돌 발생 시 해당 위치부터 순차적으로 버킷을 하나씩 탐색
(02번에서 충돌이 발생하면 순차적으로 03, 04... 로 버킷을 옮겨 빈 버킷에 데이터 저장) - 제곱 탐색 (Quadratic Probing) - 충돌 발생 시 해당 위치부터 제곱만큼 떨어진 다음 버킷 탐색
(1, 4, 9, 16, 25....) - 이중 해시 (Double Hashing) - 충돌 발생 시 다른 해시 함수를 한 번 더 적용
- 선형 탐색 (Linear Probing) - 충돌 발생 시 해당 위치부터 순차적으로 버킷을 하나씩 탐색
람다 (Lambda)
- def를 사용해 필요한 함수를 생성하지 않고, 간단하게(?) 사용하기 위해 만들어진 함수
- 선언방법
lambda 매개변수(x) : 표현식
- Ex _ 두 수를 더하는 함수
def plus(x, y):
return x + y
plus(10, 15)
#===================
30
# Lambda 형식 표현
(lambda x, y : x + y)(10, 20)
#===================
30
- map()
- map(함수, 리스트) 의 형태- map은 함수와 리스트를 인자로 받는 함수
- 리스트로부터 원소를 하나씩 꺼내어 함수를 적용한 후, 결과를 새로운 리스트에 담아줌
# 0 ~ 4까지 제곱
map(lambda x : x ** 2, range(5))
# [0, 1, 4, 9, 16]
list(map(lambda x : x ** 2, range(5)))
# [0, 1, 4, 9, 16]
- filter()
- filter(함수, 리스트)- 리스트에 들어있는 원소들을 함수에 적용시켜 결과가 참인 값들로 새로운 리스트를 만들어줌
(0부터 9까지 리스트에서 숫자를 하나씩 꺼낸 후, x < 5가 참이면 새로운 리스트에 넣어 반환)
- 리스트에 들어있는 원소들을 함수에 적용시켜 결과가 참인 값들로 새로운 리스트를 만들어줌
# 0 ~ 9까지 리스트 중 5보다 작은 것만 return
filter(lambda x : x < 5, range(10))
# [0, 1, 2, 3, 4]
list(filter(lambda x : x < 5, range(10)))
# [0, 1, 2, 3, 4]
# 홀수 반환 필터
filter(lambda x : x % 2, range(10))
# [1, 3, 5, 7, 9]
list(filter(lambda x : x % 2, range(10)))
# [1, 3, 5, 7, 9]
728x90
'ssung_데이터 엔지니어링 > 1주차_자료구조, 알고리즘' 카테고리의 다른 글
DFS/BFS (Depth-First Search / Breadth-Frist Search) (1) | 2023.10.20 |
---|---|
큐 (Queue)와 트리 (Trees), 힙 (Heaps) (1) | 2023.10.18 |
연결 리스트(Linked list)와 스택(Stack) (0) | 2023.10.17 |
탐색(Search)와 재귀 알고리즘(Reculsive algorithms) (0) | 2023.10.16 |