| English | 의미 |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | 해시 함수 |
| key/kiː/ | 키 |
| address/əˈdres/ | 주소 |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | 결정론적 |
| collision/kəˈlɪʒn/ | 충돌 |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | 선형 탐색 |
| chaining/ˈtʃeɪnɪŋ/ | 체인링 |
| load factor/ləʊd ˈfæktə/ | 충전 계수 |
Million 줄 중 한 줄 찾기 (검색하지 않고도)
- Supermarket till scans a barcode and the price appears before your hand leaves the item. The product file holds fifty million lines.
- Nothing searched them. The barcode number went through a short calculation that produced a position, and the computer read that position: one read, no comparisons, the same time whether the file holds fifty rows or fifty million.
- 이 계산은 해시 함수(hash function) 이며, 전체 아이디어는 여기에 기반합니다: 데이터가 들어갈 곳에 저장하지 말고, 자신의 키가 말하는 대로 들어갈 곳에 저장하십시오.
- 이 교훈은 해시 알고리즘이며, 두 개의 키가 같은 슬롯을 원할 때 발생하는 일, 그리고 검색 및 삽입 방법을 다룹니다.
해시 함수
- 해시 함수(hash function), 또는 해시 알고리즘은 레코드의 키(key) 를 받아 레코드가 저장되는 주소(address) 를 생성합니다.
- 좋은 해시 함수는 빠름(fast), 결정론적(deterministic)(동일한 키는 항상 같은 주소를 제공), 그리고 키를 사용 가능한 슬롯 전반에 고르게(evenly) 분산시킵니다.
- $N$ 슬롯을 위해 교재에서 요구하는 세 가지 방법: 모듈로,
address ← key MOD N; 폴딩, 키를 여러 부분으로 나누어 더한 후 MOD $N$; 문자열 해시, 문자 코드들을 더한 후 MOD $N$.
해시 함수(hash function)는:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
해시 함수는 키를 주소로 매핑하여 거의 즉시 direct lookup을 가능하게 함.
해시 함수가 좋은 것은 무엇인가? 모두 선택하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
빠르고, 결정론적이며 고르게 분포됨. 모든 현실적인 해시 함수는 충돌을 완전히 피할 수 없으므로, 모든 설계에는 충돌 해결 전략이 포함됩니다.
worked example: 각 알고리즘 적용하기
- 파일에는 10개의 슬롯이 있으며, 번호는 0부터 9까지입니다. 키 4517은 어디에 들어갈까요?
- 모듈로: $4517 \bmod 10 = 7$, 따라서 슬롯 7.
- 폴딩(쌍 단위로): $45 + 17 = 62$, 이후 $62 \bmod 10 = 2$, 따라서 슬롯 2.
- 그리고 문자열 해시를 통해 키 "CAB"를? $67 + 65 + 66 = 198$, 이후 $198 \bmod 10 = 8$, 따라서 슬롯 8.
- 산술 과정을 보여주세요. 점수는 슬롯 번호 자체보다는 계산 과정에 부여됩니다.
key = 27이고 N = 10일 때, modulo 해시 address ← key MOD N를 사용하면 어떤 주소가 생성됩니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
27 MOD 10 = 7 (27을 10으로 나눈 나머지).
테이블에 슬롯이 10개 있습니다. 키 4517에 대해 쌍별 접기(folding in pairs)를 사용(45와 17을 더한 후 MOD 10)하면 어느 슬롯에 들어갑니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
45 + 17 = 62, 그리고 62 MOD 10 = 2입니다. 같은 키가 modulo 해시를 사용할 경우 슬롯 7로 갈 것입니다.
충돌
- 충돌은 서로 다른 두 키가 동일한 주소로 해시될 때 발생합니다. 어떤 해시 함수와 현실적인 파일에서도 충돌은 필연적이므로, 이를 처리할 전략은 설계의 일부여야 하며 부수적 고려사항이 아닙니다.
- 선형探求(Linear probing) 은 레코드를 다음 빈 슬롯에 배치하며, 테이블 끝에서 시작점으로 다시 돌아옵니다. 간단하지만 레코드가 집단(Cluster) 을 형성하여,已满된 영역이 커지고 그 안에 들어오는 모든 키에 대한 접근 시간이 길어집니다.
- 체인링(Chaining) 은 각 슬롯을 해당 슬롯으로 해시된 모든 레코드의 연결 리스트(linked list) 의 헤드로 만듭니다. 집단 현상이 없으나, 포인터에 대한 추가 메모리 사용과 리스트를 따라 이동하는 데 걸리는 시간이 필요합니다.
- 리해싱(Rehashing) 은 다른 슬롯을 찾기 위해 두 번째 해시 함수를 적용하여 키를 더 잘 분산시키지만, 더 많은 연산 비용을 수반합니다.
충돌(collision)이 발생하는 상황은:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
두 개의 키가 동일한 슬롯에 매핑되는 것은 충돌이며, 프로빙(probing), 체인칭(chaining) 또는 재해싱(rehashing)을 통해 해결해야 합니다.
각 충돌 처리 방법을 그 기능과 연결하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
충돌은 체인칭이나 프로빙으로 해결하며, 부하 인자를 낮게 유지하면 검색 속도가 O(1)에 가까워집니다.
검색 및 삽입
- 삽입: 키를 해시합니다. 슬롯이 비어 있다면 레코드를那里に写入。如果不行，则遵循解决策略，线性探测时前往下一个空闲槽位，或链式法时前往该槽位列表的头部。
- 검색: 키를 해시하고 해당 슬롯을 읽습니다. 저장된 키가 일치하면 레코드를 찾았습니다. 그렇지 않으면 동일한 전략을 따르며,either 키가 일치하거나 빈 슬롯이 발견되어 레코드가 파일에 없음을 증명할 때까지 계속합니다.
- 두 작업 모두 동일한 전략을 사용합니다. 첫 번째 불일치에서 멈추는 검색은 충돌로 인해 이전에 이동되었던 모든 레코드를 놓칠 것입니다.
worked example: 충돌 추적하기
- 10 슬롯 표는 선형探针与
key MOD 10使用。按顺序插入23、33、43，然后搜索43。 - 23은 3로 해시됩니다; 슬롯 3이 비어 있으므로 해당 슬롯에 저장됩니다. 33은 3로 해시되지만 슬롯 3에는 이미 23이 저장되어 있으므로 선형探路法(linar probing)에 의해 슬롯 4에 배치됩니다. 43은 3로 해시되지만 슬롯 3과 4이 모두 사용 중이므로 슬롯 5에 저장됩니다.
- 43 검색: 슬롯 3로 해시하여 슬롯 3을 읽으면 키가 23으로 일치하지 않으므로 다음 슬롯으로探路法(linar probing); 슬롯 4에 저장된 값이 33로 일치하지 않음; 슬롯 5에 저장된 값이 43로 찾았으므로, 총 3번의 읽기 후 성공함.
- 이 연속된 3개의 슬롯은 선형探路法(linar probing)이 유발하는 클러스터링(clustering) 현상입니다.
각 키를 바로 버킷에 해시함
해시 함수는 키를 버킷 번호로 변환하여, 검색하지 않고 바로 레코드로 점프하게 함. 두 키가 같은 버킷에 착륙하면 충돌이며, 해당 버킷 내에서 함께 연결됨(chaining).
해시 테이블에서 검색할 때, 읽은 첫 번째 슬롯에 다른 키가 포함되어 있는 즉시 해당 레코드는 파일에 존재하지 않습니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
해당 레코드는 충돌로 인해 위치가 변경되었을 수 있습니다. 검색은 일치하는 레코드나 빈 슬롯을 찾을 때까지 동일한 해결 전략을 따릅니다.
부하 계수(load factor)
- 부하 계수란 레코드 수를 슬롯 수로 나눈 값입니다. 이는 테이블 성능 예측을 위한 단일 지표입니다.
- 약 70% 이하일 때 평균 검색 속도는 읽기 한 번에 가깝습니다. 이 값을 초과하면探路法(linar probing) 시퀀스가 급격히 길어지고 성능이 선형 탐색 수준으로 저하됩니다.
- 해결책은 테이블 크기를 늘리고 모든 레코드를 다시 해시하여 재배치하는 것입니다. 따라서 해시 테이블은 현재 저장된 데이터가 아닌, 향후 수용할 데이터를 기준으로 크기가 설정되어야 합니다.
슬롯이 10개인 테이블에서 key MOD 10와 선형 프로빙을 사용합니다. 23, 33, 43을 순서대로 삽입한 후 43이 들어가는 슬롯은 어디입니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
세 키 모두 3으로 해시됩니다. 23이 슬롯 3을 차지하고, 33은 슬롯 4로 프로빙되며, 43은 슬롯 5로 갑니다. 연속된 세 키는 선형 프로빙이 유발하는 클러스터링(clustering)의 정확한 예입니다.
놓칠 수 있는 점
- 충돌(collision)은 두 개의 키가 하나의 주소로 매핑되는 것입니다. 오류이거나 기록 손실도 아니며, 전략적으로 처리해야 하는 정상적인 상황입니다.
- 검색은 삽입과 동일한 처리 전략을 따르며, 키가 일치하거나 빈 슬롯(empty slot) 을 만날 때까지 계속됩니다.
- 선형探路法(linar probing)은 클러스터링을 유발하며, 체인(chaining)은 메모리 비용이 발생합니다. 단순한 메커니즘이 아닌 장단점을 고려해야 합니다.
- 부하 계수는 슬롯 수로 레코드 수를 나눈 값이며, 임계값은 약 70%이지 100%가 아닙니다.
해시 검색 속도를 빠르게 유지하려면 부하 인자(레코드 ÷ 슬롯)를 다음 중 하나로 두어야 합니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
낮은 부하 인자는 충돌을 줄여 검색 속도를 O(1)에 가깝게 유지합니다.
이해했습니다
- 해시 함수(hash function) 는 키(key) 를 주소(address) 로 변환하여, 빠르고 결정적이며 고르게 분포되게 합니다. 모듈로 연산(modulo), 접기(folding), 문자열 해시는 반드시 알아야 할 세 가지 방법입니다.
- 충돌(collision) 은 두 개의 키가 하나의 주소로 해시될 때 발생하며, 선형探路法(linar probing) (다음 빈 슬롯, 클러스터링), 체인(chaining) (슬롯당 링크드 리스트, 메모리 증가), 또는 **재해시(rehashing)**的方法来解决。
- 삽입과 검색은 동일한 전략을 따르며, 검색은 키 일치 또는 빈 슬롯 도달 시 종료됩니다.
- 근사 한 번 읽기 검색을 위해 부하 계수(레코드 수 ÷ 슬롯 수)를 약 70% 이하로 유지해야 합니다.