다섯 살도 알 수 있게 · 시스템SW
해시 알고리즘이 뭐예요?
해시 알고리즘을, 공구함에서 번호를 계산해 바로 알맞은 칸을 짚어 찾는 이야기로 풀어봤어요.
공구가 너무 많아서 하나 찾는 데 한참 걸려요.하나씩 뒤지면 공구함 바닥까지 다 봐야 할 수도 있어요.
처음부터 하나씩 뒤지면 너무 느려요.번호만 보고 바로 칸을 짚을 규칙이 있으면 좋겠어요.
해시 알고리즘은 번호를 계산해 바로 칸을 짚는 규칙이에요.뒤질 필요 없이 계산 한 번으로 칸을 알아요.
해시 함수로 계산공구 번호를 규칙대로 계산해요
칸을 바로 짚기계산값이 곧 칸 번호예요
가끔 겹침(충돌)두 공구가 같은 칸을 가리킬 수 있어요
겹치면 줄줄이 매달기같은 칸에 여러 개를 매달아요
두 공구가 같은 칸을 가리킬 수 있어요(충돌).겹친 공구를 같은 칸에 줄줄이 매달거나(체이닝), 옆 빈 칸을 찾아 넣어요.
칸이 꽉 차면 공구 찾기가 다시 느려져요.빨리 찾으려면 칸 수를 공구 수보다 넉넉히 둬야 해요.
한 줄로
해시 알고리즘은 데이터로 번호를 계산해 저장할 칸(버킷)을 바로 짚는 규칙으로, 거의 계산 한 번에 찾고 저장할 수 있게 해줘요.
해시 알고리즘은 키 값을 해시 함수에 넣어 배열 인덱스(버킷 번호)로 변환하는 방법이에요. 이를 이용한 해시 테이블은 평균적으로 O(1)에 가까운 시간에 탐색·삽입이 가능해 처음부터 끝까지 훑는 선형 탐색(O(n))보다 훨씬 빨라요. 서로 다른 키가 같은 버킷으로 계산되는 충돌이 생기면 체이닝(같은 칸에 연결 리스트로 매달기)이나 오픈 어드레싱(다음 빈 칸을 찾아 넣기)으로 해결해요. 버킷 수 대비 데이터가 너무 많아지면(적재율이 높아지면) 충돌이 늘어 성능이 떨어져요. 이는 메시지 무결성을 확인하는 암호학적 해시 함수와는 다른, 자료구조·알고리즘 관점의 해시예요.
어른들은 이렇게 불러요
- 해시 함수
Hash Function - 번호를 계산해주는 규칙. 같은 입력엔 항상 같은 칸을 줘요.
- 해시 테이블
Hash Table - 칸마다 공구를 넣어둔 공구함. 평균 O(1)로 찾고 넣을 수 있어요.
- 버킷(슬롯)
Bucket (Slot) - 계산된 번호가 가리키는 칸. 해시값이 바로 칸 번호가 돼요.
- 충돌
Collision - 서로 다른 공구가 같은 칸을 가리키는 것. 체이닝이나 오픈 어드레싱으로 풀어요.
- 체이닝
Chaining - 같은 칸에 줄줄이 매달아 두는 방식. 충돌한 공구를 리스트로 연결해요.
- 오픈 어드레싱
Open Addressing - 옆 빈 칸을 찾아 넣는 방식. 칸이 꽉 찰수록 빈 칸 찾기가 어려워져요.
- 적재율
Load Factor - 칸 수 대비 들어있는 공구 비율. 너무 높아지면 충돌이 늘어요.
- 선형 탐색
Linear Search - 처음부터 하나씩 다 뒤지는 방식. 해시 테이블보다 훨씬 느려요(O(n)).
다음 이야기
지우지 않고 바로바로 바꿔 쓰는 새 창고들 →