🤖 옌지니어의 IT 기록 🤖

해시란?
해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

해시의 특징

• 단방향 동작 (키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾기 불가능)
• 키 자체가 인덱스이므로 값을 찾기 위한 탐색 불필요
• 값을 인덱스로 활용하기 위해 적절한 변환과정 필요

해시의 동작방식

해시 테이블(hash table) : 키와 대응한 값이 저장되어 있는 공간

버킷(bucket) : 해시 테이블의 각 데이터

해시의 특성을 활용하는 분야

단방향으로만 검색이 가능한 대신 빠르게 원하는 값 검색 (데이터를 저장하고 검색하는 경우 / 보안이 필요한 경우에 활용)

• 비밀번호 관리 : 비밀번호를 그대로 노출해 저장하는 것은 위험하므로 해싱한 비밀번호 저장
• 데이터베이스 인덱싱 : 데이터베이스에 저장된 데이터를 효율적으로 검색
• 블록체인 : 각 블록은 이전 블록의 해시값을 포함하며 이를 통해 데이터 무결성 확인

해시함수를 구현할 때 고려할 내용

• 해시 함수가 변환한 값은 인덱스로 활용해야하므로 해시 테이블의 크기를 넘으면 안된다.
• 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.
  (충돌 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미)

자주 사용하는 해시함수

1) 나눗셈법 (division method)

• x = 키 / m = 소수 
• 키를 소수로 나눈 나머지를 인덱스로 사용 (충돌을 줄이기 위해 소수 사용)
• 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자로 % 사용
• m을 모듈러 연산했을 때 나올 수 있는 값은 0~(m-1)이므로 해시 테이블의 크기는 m (큰 소수를 찾기 어려운 문제)

2) 곱셈법 (multiplication method)

• m = 최대 버킷의 개수 / A = 황금비 (수학적으로 임의의 길이를 나누었을 때 전체:긴 부분 = 긴 부분:짧은 부분인 비율)
• 곱셈법을 계산하는 방식
  • 키에 황금비 곱하기
  • 위에서 구한 값의 모듈러 1 취하기 (정수 부분을 버리고 소수 부분 취하기)
  • 위에서 구한 값을 가지고 실제 해시 테이블에 매핑

문자열 해싱

• 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱
• 해시 함수를 적용한 값이 해시 테이블 크기에 비해 너무 클 경우 수정 작업 필요
  → 덧셈을 전부 한 다음 모듈러 연산을 하는 대신 중간중간 모듈러 연산을 해 더한값을 모듈러 연산

충돌 처리

충돌(collision) : 서로 다른 키에 대해 해시 함수의 결과값이 같은 것 (하나의 버킷에 2개의 값을 넣dj 충돌 처리가 필요)

1) 체이닝으로 처리하기

체이닝 : 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터 연결

• 해시 테이블 공간 활용성이 떨어진다. (충돌이 많아지면 링크드리스트의 길이가 길어져 해시 테이블 공간 사용도↓)
• 검색 성능이 떨어진다. (충돌이 많으면 링크드리스트 자체의 한계로 검색 성능 저하)

2) 개방 주소법으로 처리하기

개방 주소법(open addressing) : 빈 버킷을 찾아 충돌값을 삽입 → 해시 테이블을 최대한 활용하므로 효율적 메모리 사용

• 선형 탐사 방식 (linear probing) 
  • 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동
  • 해시 충돌이 발생한 값끼리 모이는 영역이 생겨 클러스터 형성 (이러한 군집이 생기면 해시값이 겹칠 확률 증가)
• 이중 해싱 방식
  • 해시 함수를 2개 사용
  • 두 번째 해시함수는 첫 번째 해시함수로 충돌이 발생하면 해당 위치 기준 어떻게 위치를 정할지 결정하는 역할
  • 선형 탐사와 비슷하게 더하는 방식이지만 주어지는 키마다 점프하는 위치를 다르게 해서 클러스터 형성 감소

해시 문제의 핵심은 키와 값을 매핑하는 과정 !!

※ 참고 자료 ※

https://wikidocs.net/221191