🔑해싱(Hashing)이란?
key값을 해시함수를 이용해 새로운 특정 해시 값으로 변환하는것
🙋♂️ 해시 함수란?
해시 함수는 임의의 길이를 갖는 입력값을 받아서 일정한 길이의 해시값을 반환하는 함수이다. 해시 테이블에서는 이 해시값을 주소로 사용하여 해당 항목을 저장할 위치를 결정한다.
파이썬에서는 해시 함수로 내장된 hash() 함수를 사용하며, 이 함수는 입력값을 받아 해시값을 반환한다
🙋♂️ 좋은 해시 함수란?
좋은 해시 함수는 입력값이 서로 다른 경우에 대해 해시값이 충돌하지 않도록 해야 한다
가능한 모든 입력값에 대해 해시값이 고르게 분포되어야 하고, 이를 해시 함수의 균등성이라고 한다.
해쉬함수의 종류
어떤 방식의 해시함수가 있는지 정도만 알아두면 좋다.
1. Division Method
데이터를 임의의 소수로 나누어 그 나머지를 해시코드로 사용하는 방법이다.
예를 들어, 데이터를 17로 나누어서 나머지를 해시코드로 사용할 수 있다.
2. Multiplication Method
고정된 상수 A와 데이터를 곱한 다음, 소수로 나눈 나머지를 해시코드로 사용하는 방법이다다.
예를 들어, A=0.6180339887(골든 레이트)이라고 할 때, 데이터를 A와 곱한 후, 소수 2^k를 곱한 후 정수부분을 취하는 방식으로 해시코드를 구할 수 있다.
3. Folding Method
데이터를 여러 부분으로 나누어서, 각 부분을 더하거나 곱한 결과를 해시코드로 사용하는 방법이다.
예를 들어, 데이터를 12345678이라고 할 때, 12+34+56+78을 더한 값을 해시코드로 사용할 수 있다.
4. Polynomial Rolling Hash
데이터를 문자열로 간주하고, 문자열의 각 문자를 알파벳 인덱스로 변환한 다음, 다항식을 이용하여 계산한 값을 해시코드로 사용하는 방법이다.
예를 들어, 문자열 "abcde"라고 할 때, 다항식 x^4 + 2x^3 + 3x^2 + 4x + 5를 이용하여 해시코드를 계산할 수 있다.
해시 테이블(Hash Table)
해시 테이블은 키(key)와 값(value)의 쌍(pair)으로 데이터를 저장하는 자료구조이다.
파이썬에서는 딕셔너리(dict) 타입으로 구현되어 있고, set 자료구조 또한 해시테이블을 기반으로 구현되어 있다.
해시 테이블은 해시 함수를 이용하여 키 값을 해시값(hash value)으로 변환한다. 이 해시값을 이용하여 해당 키 값에 대응하는 인덱스(index)를 결정하고, 이 인덱스에 해당하는 공간(bucket)에 값을 저장한다.
따라서, 데이터를 찾을 때에는 순차적으로 배열을 탐색하는 것이 아니라, 해당 키 값을 해시 함수에 적용하여 해시값을 계산하고, 이를 이용하여 저장된 위치를 찾아갈 수 있다. 이를 통해 빠르게 데이터를 검색할 수 있다.
해시 충돌 (Hash Collision)?
서로 다른 두 개의 입력값이 같은 해시값을 가지는 경우, 해시충돌이 일어난다.
시 테이블에서는 해시값을 이용하여 해당 데이터의 저장 위치를 결정하는데, 만약 서로 다른 두 개의 데이터가 같은 해시값을 가진다면, 충돌이 발생하게 된다.
✔ 해시 충돌은 해시 테이블에서 불가피한 현상
👏해결방법
1. 개별 체이닝 (Seprate Chaining)
- 각 버킷마다 연결 리스트 를 만들고, 충돌이 발생한 데이터를 해당 버킷의 연결 리스트에 추가하는 방식
2. 오픈 어드레싱 (Open Addressing)
- 충돌이 발생한 경우, 다른 빈 버킷을 찾아서 데이터를 저장하는 방식
- 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 랜덤 프로빙(Random Probing) 등 다양한 방식이 있다.
