Python, C, C++로 해싱 알고리즘(Hashing) 쉽게 배우기

6. 해싱 (Hashing)

해시 함수로 키를 배열 인덱스로 변환해 평균 O(1)에 탐색·삽입·삭제가 가능하다. 충돌은 체이닝·개방 주소법으로 해결한다. 딕셔너리/맵, 캐시, 데이터베이스 인덱스 등 수많은 시스템의 기본 설계 요소다. 위키백과

 

해싱은 긴 글이나 숫자를 마법 계산기에 넣어서 항상 같은 짧은 ‘비밀 번호’를 만드는 거야. geeksforgeeks.org techtarget.com kids.kiddle.co 이 번호 덕분에 컴퓨터는 도서관에서 책 제목을 쪽수로 바로 찾듯 자료를 번개처럼 찾아내고, 파일이 중간에 바뀌지 않았는지도 순식간에 검사해. en.wikipedia.orglearn.microsoft.comsupport.wholechain.com 그리고 거꾸로 원본을 되돌리기 거의 불가능해서 비밀번호 숨기기나 비트코인 같은 블록체인 보안에도 쓰여! crowdstrike.comchainbulletin.comtechtarget.com

 

1. djb2 (비암호화 문자열 해시)

Python

def djb2(s: str) -> int:
    h = 5381
    for c in s.encode():        # 바이트 단위 순회
        h = ((h << 5) + h) + c  # h * 33 + c
    return h & 0xFFFFFFFF       # 32-bit 마스킹

C

#include <stdint.h>

uint32_t djb2(const unsigned char *str)
{
    uint32_t hash = 5381;
    int c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash*33 + c */
    return hash;
}

 

C++

#include <cstdint>
#include <string>

uint32_t djb2(const std::string& str)
{
    uint32_t hash = 5381;
    for (unsigned char c : str)
        hash = ((hash << 5) + hash) + c;
    return hash;
}

 

2. FNV-1a (비암호화 범용 해시)

Python

def fnv1a(data: bytes, seed: int = 0x811c9dc5) -> int:
    prime = 0x01000193
    h = seed
    for b in data:
        h ^= b
        h = (h * prime) & 0xFFFFFFFF
    return h

C

#include <stdint.h>

uint32_t fnv1a(const void *key, uint32_t len)
{
    const uint8_t *data = (const uint8_t*)key;
    uint32_t prime = 0x01000193;
    uint32_t hash  = 0x811c9dc5;

    for (uint32_t i = 0; i < len; ++i) {
        hash ^= data[i];
        hash *= prime;
    }
    return hash;
}

 

C++

#include <cstdint>
#include <cstring>

uint32_t fnv1a(const void* key, std::size_t len)
{
    const uint8_t* data = static_cast<const uint8_t*>(key);
    uint32_t hash = 0x811c9dc5;
    const uint32_t prime = 0x01000193;

    while (len--) {
        hash ^= *data++;
        hash *= prime;
    }
    return hash;
}

 

3. SHA-256 (암호화 해시)

Python — hashlib

 

import hashlib
msg = b"hello world"
digest = hashlib.sha256(msg).hexdigest()
print(digest)  # b94d27b9934d3e08...

 

C — OpenSSL (리눅스: -lcrypto 링크)

#include <openssl/sha.h>
#include <stdio.h>
#include <string.h>

int main() {
    const char *msg = "hello world";
    unsigned char md[SHA256_DIGEST_LENGTH];
    SHA256((const unsigned char*)msg, strlen(msg), md);

    for (int i = 0; i < SHA256_DIGEST_LENGTH; ++i)
        printf("%02x", md[i]);
    printf("\n");
    return 0;
}

---

1. 초고속 키–값 검색: 해시 테이블·딕셔너리

• 대부분의 언어가 내부 맵 자료구조 키 → 인덱스 매핑에 djb2, FNV, Murmur 계열처럼 연산량이 적은 해시를 활용합니다. 이러한 해시는 “O(1) 평균 시간” 조회를 보장하면서도 충돌 분포가 양호해 컴파일러 심볼 테이블, 언어 런타임 딕셔너리, 라우터 룰 캐시 등에 채택됩니다. reddit.comtheartincode.stanis.megeeksforgeeks.org
• 온라인 게임·실시간 렌더러도 동일한 특성 때문에 문자열→리소스 핸들 매핑에 djb2/FNV-1a를 단순 구현으로 삽입합니다. geeksforgeeks.org

2. 확률적 자료구조: Bloom Filter · Count-Min Sketch

• Bloom Filter는 “여러 개의 독립 해시”로 비트벡터를 설정해 0.0X % 오차로 멤버십을 판단할 때 FNV-1a·MurmurHash3를 즐겨 씁니다. mojoauth.commedium.comstackoverflow.commedium.com
• 대용량 웹크롤러·CDN이 중복 URL·컨텐츠 체크에, 클라우드 RDB·키밸류 스토어가 디스크 조회를 줄이는 캐싱 힌트로 Bloom Filter를 배치합니다. medium.com

3. 파일 무결성·데이터 검증

• 다운로드 센터나 패키지 매니저가 게시하는 sha256sum 값은 사용자가 받은 파일을 동일 해시로 계산해 전송 중 변조 여부를 즉시 검증하도록 돕습니다. stackoverflow.com
• 클라우드 백업·분산 스토리지(Ceph, Veeam 등)는 블록마다 SHA-1/256을 붙여 중복 블록 제거(deduplication) 와 컨텐츠 주소화(CAS) 를 수행합니다. 변경이 1바이트라도 해시 값이 완전히 달라지므로 중복 감지가 쉽습니다. sciencedirect.comlab.abilian.comovercast.blog
• 컨테이너 이미지 레지스트리 및 일부 패키징 포맷(OCI, AppImage)도 “내용 기반 경로” 전략으로 BLAKE3·SHA-256 해시를 경로 자체로 삼아 버전 충돌을 제거합니다. lab.abilian.commojoauth.com

4. 패스워드 저장과 인증

• 웹 서비스는 평문 암호를 저장하지 않고, 소금(salt)+강화된 해시(bcrypt·Argon2 등) 로 변환해 DB에 보관합니다. 유출 시에도 역추적이 어려워 보안이 대폭 향상됩니다. wired.comlifewire.com
• SHA-1 같은 약한 해시로만 저장했던 사례(예: 2012 LinkedIn 유출)는 GPU 무차별 대입 공격으로 빠르게 깨졌다는 교훈이 남습니다. wired.com

5. 버전 관리 시스템 (Git)

• Git은 모든 객체(커밋·트리·블롭) 를 내용+헤더에 대한 SHA-1 해시(40 hex)를 파일명으로 삼아 저장합니다. 내용이 같으면 전 세계 어디서나 동일 해시가 나오므로 분산 저장 동기화가 단순해집니다. git-scm.comvjeko.com
• 최근 보안 강화를 위해 Git 2.43+는 SHA-256 모드도 지원하며, 해시 길이를 늘려 충돌 공격에 대비합니다. git-scm.com

6. 블록체인·분산 원장

• 비트코인은 블록 헤더를 두 번 SHA-256 해싱한 값이 난이도 목표 미만이 되도록 ‘채굴’합니다. Proof-of-Work 난스 퍼즐이 해시 함수의 예측 불가능성을 근간으로 삼는 셈입니다. komodoplatform.comscryptplatform.medium.cominvestopedia.com
• 각 블록은 머클 트리 루트 해시를 저장해 수천 건의 트랜잭션 전체 무결성을 단 한 줄의 해시로 증명합니다. 검증자가 특정 거래 포함 여부를 O(log N) 해시만으로 확인할 수 있습니다. bsvblockchain.orggeeksforgeeks.org
• 채굴 연산이 에너지 집약적이라는 점 역시 SHA-256 사용량과 직결돼 ‘탄소 발자국’ 논쟁을 일으킵니다. wired.com

7. 분산 시스템과 로드 밸런싱

• 캐시 클러스터·NoSQL 샤딩은 일관 해싱(consistent hashing) 으로 키를 여러 노드에 고르게 분배합니다. 이때 충돌률이 낮고 속도가 빠른 FNV나 Murmur 계열을 주로 사용합니다. geeksforgeeks.org
• CDN은 URL 해시→에지 노드 매핑으로 “캐시 파편화” 없이 트래픽을 분산하고, 대규모 메타데이터 저장 시스템(LinkedIn Voldemort, Amazon Dynamo)도 같은 원리를 택합니다. geeksforgeeks.org

8. 최신 암호화 해시: BLAKE3 및 이후 세대

• BLAKE3는 병렬·SIMD 최적화 설계로 SHA-256 대비 2–3 배 빠르면서도 현대 공격 모델에 안전해, 대용량 파일 지문 생성·라이브 코드 핫리로드 무결성 체크 등에 각광받고 있습니다. mojoauth.com
• Rust cargo와 일부 게임 빌드 시스템은 이미 기본 해시로 BLAKE3를 채택해 빌드 캐시 속도를 끌어올렸습니다. mojoauth.com