[Python] Hash 간단 정리

Hash! Hash란?

• **Hash(해시)**는 데이터를 효율적으로 저장하고 검색하기 위해 사용되는 데이터 구조 또는 알고리즘
• 특정 입력값을 고정된 크기의 값(해시값)으로 매핑하는 과정이라고 하며 이 과정을 수행하는 함수는 해시 함수(Hash Function)라고 하며, 해시 값을 저장하는 자료구조를 해시 테이블(Hash Table)이라고 합니다.

Hash의 특징

1. 고속 데이터 접근:
   • 데이터가 해시값으로 변환되어 키(key)를 기반으로 빠르게 검색 가능.
2. 고정된 크기:
   • 해시 함수는 입력 데이터 크기와 상관없이 고정된 크기의 해시값을 반환.
3. 충돌 가능성:
   • 서로 다른 입력값이 같은 해시값을 가질 수 있는 경우가 있으며, 이를 충돌(Collision) 이라고 함.

Hash의 주요 사용 사례

1. 키-값 저장소 (Dictionary, HashMap):
   • 데이터를 키(key)와 값(value) 형태로 저장하고 빠르게 검색.
   • 예: Python의 dict, Java의 HashMap.
2. 데이터 검색:
   • 대용량 데이터에서 특정 값을 빠르게 찾기 위해 사용.
3. 데이터 무결성 검증:
   • 파일이나 메시지가 변경되지 않았는지 확인.
   • 예: SHA-256, MD5 해시 함수.
4. 암호화와 보안:
   • 비밀번호 저장, 디지털 서명, 블록체인 등에서 사용.
5. 캐싱:
   • 동일한 데이터를 효율적으로 저장하고 재사용하기 위해 키를 기반으로 캐싱.

Hash TMI

Hash collision 시 보안기법들

1. Chaining

• 충돌이 발생하면, 동일한 해시값의 데이터를 연결 리스트 형태로 저장.
• 장점: 동적 메모리 사용 가능, 충돌 해결에 적합.
• 단점: 연결 리스트 관리로 인해 메모리 추가 소모.

2. Open Addressing

• 충돌이 발생하면, 빈 슬롯을 찾을 때까지 탐색.
• 예: 선형 탐사, 이차 탐사, 이중 해싱.
• 장점: 모든 데이터가 테이블 안에 저장.
• 단점: 테이블이 꽉 차면 성능 저하.