[CS지식] 해시(Hash)

해싱, 해시함수, 해시테이블

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑 하는 것

해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

이 때 매핑 전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 **해싱(hashing)**이라고 합니다.

 

collision 현상 (해시충돌)

데이터가 많아지면서, 다른 데이터가 같은 해시 값으로 충돌나는 현상

→ 그래도 해시 테이블을 쓴다 왜?

: 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시 값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해짐.

 

장점

• 언제나 동일한 해시값 리턴, index를 알면 빠른데이터 검색이 가능해짐
• 해시 테이블의 시간복잡도 O(1), 이진탐색 트리는 O(logN)

 

충돌 문제 해결 방법

1. 체이닝 : 연결리스트로 노드를 계속 추가해 나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)

2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장 할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)

 

3. 선형 탐색 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함

4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

 

 

 

면접질문

1) 해싱 이란 무엇 일까요? 해시 테이블과 함께해서 설명해주세요.

• 해싱은 키 값에 직접 산술적인 연산을 적용해서 항목이 저장되어 있는 테이블의 주소를 계산해서 항목에 접근합니다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블 이라고 부르고, 해시 테이블을 이용한 탐색을 해싱 이라고 합니다.

2) 해시충돌이 일어나는 이유와, 이를 해결하는 방법 한가지를 말씀해주세요.

• 데이터가 많아지면서 중복되는 경우가 발생하게 되면서 해시충돌이 일어납니다. 이를 해결방법으로 open addressing 이나 separate chaining 방법이 있습니다. open addressing은 해시 함수로 얻은 해시값에 따라서 데이터와 키 값을 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 하는 기법. separate chaining은 추가적인 메모리를 사용해 동일한 버킷에 값이 있으면 링크드 리스트로 해당 value를 뒤에 저장하는 방법.