해시법

devkty 2025. 3. 29. 21:49

728x90

글에 들어가기 앞서 설현아님 벨로그를 참조해서 작성하였습니다. 디테일한 내용(코드)은 해당 벨로그를 참조해주세요!(내용 공유해주심에 감사드립니다) https://velog.io/@sha0209/%ED%95%B4%EC%8B%9C%EB%B2%95hashing%EA%B3%BC-%EC%B6%A9%EB%8F%8C-%EB%8C%80%EC%B2%98-%EB%B0%A9%EB%B2%95

해시법

해시법을 사용하면 문지열, 리스트, 클래스형 등 정수가 아닌 값을 저장할 때에도 결국에는 정수 형태로 변환(해시값)되어 저장된다. 키(key)와 값(value)의 쌍으로 데이터를 저장하며, 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구할 수 있다.

→ 기대할 수 있는 효과

추가와 삭제를 효율적으로 수행 가능
충돌이 없다면 O(1) 시간으로 연산 가능

대표적인 해시 알고리즘 중에 SHA256 알고리즘이 있다. 보통 비밀번호 암호화를 위해 자주 쓴다.

→ SHA(Secure Hash Algorithm)256 알고리즘이란?
hashlib 모듈에서 제공하는 sha256은 RSA의 FIPS 알고리즘을 바탕으로 하며, 주어진 바이트 문자열의 해시값을 구하는 해시 알고리즘의 생성자이다. 변환을 원하는 문자들을 256bit 길이의 key로 변환한다. 해시 충돌 사례가 아직까지 없으며 블록체인, 비트코인 네트워크 등 암호화가 중요한 곳에서 세계적으로 사용된다.

작동 방식

원소의 값을 원소의 개수로 나눈 나머지를 해시값으로 둡니다.
(해시값으로 변환하는 과정은 일반적으로 나머지 연산을 응용하여 사용!)
해시값을 인덱스로 하여 원소를 새로 저장한 배열을 만든다 → 해시테이블

용어

해시값(hash value): 추가/탐색/삭제하고자 하는 원소를 저장할 때의 인덱스
해시 테이블(hash table): 해시값을 인덱스로 원소를 저장한 새로운 배열
해시 함수(hash function): 키(원소의 값)를 해시값(인덱스)으로 변환하는 과정
버킷(bucket): 해시 테이블에서 만들어진 원소

해시법의 트레이드 오프
해시 테이블을 충분히 크게 만들면 아래에서 다룰 충돌 발생을 막을 수 있다.
하지만 이 방법은 메모리를 낭비한다.(시간과 공간의 상충관계 문제가 발생)
충돌을 피하려면 해시 함수가 해시 테이블 크기 보다 작거나 같은 정수를 고르게 생성해야 한다.
따라서 해시 테이블 크기는 소수를 선호한다.(나누어 떨어지는 수는 한 쪽으로 치우치게 된다)

해시 충돌시
당연하게도 나눈 값이 같아서 버킷이 겹칠 수 있다.
그걸 방지하기 위해서는 해시 테이블에서는 체이닝과 오픈 주소법을 사용하여 해결할 수 있다. 그러나 보통 체이닝 기법을 많이 사용한다. 이유는 이어서 알아보면 왜 그런지 알 수 있을 것이다.

체이닝 기법
말그대로 해시값이 같은 원소를 ‘체인 형식으로 연결한다’ 해서 체이닝 기법이다.
위에서 살펴본 해시 테이블과는 달리, 각 버킷에는 해시값이 같은 노드를 연결한 리스트의 앞쪽 노드를 참조한다.
이 구조는 연결 리스트 구조를 사용한다. 겹치는 버킷에 밑에 숫자를 연결해서 놓는다. 그런데 마지막에는 None이 있어 해당값이 있는지 없는지 알 수 있다.

이와 같이 겹치는 건 밑으로 링크드 리스트처럼 연결한다. 밑의 코드를 활용하면 된다. 더 자세한 코드를 알아보고 싶으면 위의 블로그를 참조해보자.
추가할 때, 값이 겹치면 중복값을 저장하지 않고 종료한다.

class Node:
  def __init__(self, key, value, next):
    # 초기화
    self.key = key # 키(해시값)
    self.value = value # 원소값
    self.next = next # 뒤쪽 노드

만약, 삭제를 한다면 삭제 대상의 노드를 이전 노드에 참조할 수 있도록 바꾸고 삭제를 한다. 그렇게 하면 삭제 값이 빠져도 원활하게 값을 검색할 수 있다.

오픈 주소법
또 다른 방법으론 오픈 주소법이 있는데, 해당방식은 상당히 안좋은 것 같다.
충돌이 발생하면 저장할 대상에 특정 값(예시로 +1)을 더하여 빈 버킷을 찾을 때까지 반복한다. 빈 버킷이 나올때까지 재해시를 반복하기 때문에 선형 탐사법이라고도 부른다.
반대로 찾을 때도 입력할 때와 같이 특정값을 더하여 찾을 대상이 나올 때까지 재해시한다. 체이닝 기법처럼 None을 만나면 원소가 해시 테이블에 존재하지 않는다는 것이다.
재해시를 수행할 확률이 높아질 수 있으니 시간복잡도가 높아질 수 있는 확률이 있어 자주 사용하지 않는다.

파이썬에서 해시를 사용하려면 set, dictionary 함수를 사용해 쉽게 구현가능하다. 둘다 mutable형식으로 수정가능한 함수임을 참고하자.

WEEK 02 공부 종료. 3월 28일 12:30.

728x90