[알고리즘/C++] - 해시

해시

: 임이의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수.
쉽게 말해, 아무리 큰 숫자를 넣어도 정해진 크기의 숫자가 나오는 함수입니다.
해시는 DJB2, Murmur3등의 방법을 통해 구현됩니다. 상황에 맞게 알고리즘을 잘 선택하여 진행합니다.

 

다음은 DJB2를 활용한 해시 함수입니다.

unsigned long hash(unsigned char *str)
{
	unsigned long hash = 5381;
	int c;
	while (c = *str++)
	{
		hash = (33*hash) ^ c;
	}
	return hash;
}

 

ex) 어떤 숫자를 10으로 나누었을 때 나머지를 구하는 함수 또한 해시 함수입니다.

• 활용 방안: '해시 테이블', '해시 셋' 등의 자료구조에 활용됩니다.해시 함수의 사용 사례:
• 해시 함수는 암호화, 데이터 검색, 데이터 무결성 확인, 로드 밸런싱, 디지털 서명 등에서 사용됩니다.

특징:

• 해시 테이블의 시간 복잡도는 보통 평균적으로 O(1)입니다. 이는 충돌이 잘 해결되고, 해시 함수가 데이터를 균등하게 분포시킬 때 가능합니다. 하지만 충돌이 많이 발생하는 최악의 경우에는 O(n)의 성능을 보일 수 있습니다.
• 해시 함수는 결정적이어야 합니다. 즉, 동일한 입력값에 대해 항상 동일한 해시 값을 반환해야 합니다. 이 속성은 데이터 검색과 비교에서 매우 중요합니다.
• 해시 함수는 빠르게 계산 가능해야 하며, 입력 데이터가 거의 균등하게 분포된 해시 값을 만들어야 충돌이 최소화됩니다.

해시값(해시코드)

:위의 해시를 적용하여 나온 고정된 길이의 값을 부르는 명칭입니다.

해시 충돌

입력범위보다 출력의 범위가 작아 서로 다른 입력값에도 동일한 값이 출력되는 충돌이 일어나는데, 이것을 해시 충돌이라고 합니다.
해결방법으로는 체이닝, 오픈 어드레싱 등의 기법이 있습니다. 필요에 따라 두가지 중 적절한 해시 함수를 선택합니다.

체이닝

: 배열의 각 요소를 연결 리스트나 이진 탐색 트리로 만들어 계속 해당 index에 데이터를 추가합니다.

오픈 어드레싱

: 동일한 해시 테이블 내의 다른 위치를 탐색하여 데이터를 삽입하는 방법입니다.
계산방법

1. 선형 프로빙(Linear probing): 간격을 고정하여 증가
2. 이차 프로빙(Quadratic probing): 임의의 2차 다항식의 연속적인 값을 추가하여 증가
3. 이중 해싱(Double Hashing): 보조 해시 함수에 의해 계산

---

정리해보자면..

해싱: 데이터를 해시 함수에 넣어 고정된 길이의 값으로 변환하는 과정

해시 함수: 해싱을 처리하는 함수
Murmur3, DJB2: 해싱을 처리하는 데 사용되는 함수
체크섬: 해시를 적용하여 나온 값
해시 충돌: 해싱을 처리하는 과정에서 나타나는 문제점
체이닝/오픈 어드레싱: 해싱을 처리하는 과정에서 해시 충돌을 해결하기 위해 사용되는 기법들 중 하나
해시테이블, 해시 셋: 해시를 통해 도출된 체크섬을 저장하고 활용하도록 하는 자료구조

---

반응형

참고자료
https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C
https://www.geeksforgeeks.org/introduction-to-hashing-2/