자주 출제되는 IT 회사 면접 질문: 해시 함수

 

IT 회사 면접에서 항상 나오는 면접 질문 중 하나는 해시 함수 질문입니다. 따라서 개발자로 취업하는 데 성공하고 회사에서 오랫동안 인정받기 위해서는 해시 함수에 대한 이해가 필수입니다. 자주 출제되는 IT 회사 면접 질문 해시 함수 알아보겠습니다.

 

1. 해시 함수란

해시함수는 길이가 다른 입력값을 입력하더라도 항상 길이가 같은 출력 값을 생성하는 함수입니다. 이러한 결과 값을 해시 값이라고 하지만 해시 코드, 해시 섬, 체크섬 등이라고도 합니다. 해시함수는 주로 안정성을 인정받은 SHA 알고리즘을 통해 구현됩니다.

2. 해시 함수 특징

2.1. 고정된 길이의 값을 출력합니다.

30자 또는 150자를 입력하더라도 해시 함수는 항상 동일한 길이의 해시 값을 출력합니다. 그러나 동일한 길이의 해시 값을 출력하기 때문에, 서로 다른 값을 입력해도 종종 동일한 해시 값이 출력되는 경우가 발생하는데, 이를 충돌이라고 합니다.

2.2. 입력 값을 유추할 수 없습니다.

작고 사소한 눈덩이가 산을 굴러 내려와 큰 눈사태가 발생하는 자연 현상처럼, 해시 함수는 입력 값의 사소한 부분이 바뀌어도 이전 입력 값의 해시 값과 전혀 다른 해시값을 생성합니다. 이를 눈사태 효과라고 합니다.

안녕하세요 ➤ E9A95DE0ADD7606BDA402B28A3630CF4B0F8C9B2
안녕하세유 ➤ 5C6EBE5C4419778D3DC189DDF0E36F82E5E5FE46

이러한 특징으로 이전 데이터를 사용하여 해시 함수에 의해 생성된 출력 값을 유추하는 것이 거의 불가능합니다.

2.4. 자원 소모가 적습니다.

해시 함수에 사용되는 알고리즘이 비교적 단순하기 때문에 CPU, 메모리 등 자원 낭비가 적어 빠르게 해시 값을 도출할 수 있다는 장점이 있습니다.

3. 해시 함수 자료구조

해시 함수를 사용하면 해시 값을 인덱스로 사용하는 자료구조를 만들 수 있습니다. 원리는 다음과 같습니다.

1. 해시 함수에 값을 입력합니다.
2. 해시 값을 리스트 일부 인덱스로 설정합니다.
3. 해시 값으로 인덱싱 된 공간에 해시 값 관련 입력 값을 삽입합니다.

그러나 고정된 길이의 값을 출력하는 해시 함수 특성으로 인해 서로 다른 값을 입력해도 동일한 해시 값이 생성될 수 있습니다. 따라서 다음과 같은 방법으로 충돌을 해결합니다.

3.1 해시 함수 자료구조 충돌 해결 방법

3.1. 개별 체이닝 방법 이용하기

개별 체이닝은 입력 값을 연결 리스트 방식으로 동일한 해시 값에 연결하는 방법입니다. 이러한 방법은 복잡한 기술이 필요하지 않고 직관적이기 때문에, 일반적으로 개별 체이닝 방법으로 충돌 문제를 해결합니다.

3.2. 오픈 어드레싱 방법 이용하기

오픈 어드레싱은 서로 다른 입력 값이 동일한 해시 값을 생성할 때 연결 리스트를 사용하여 입력 값을 같은 공간에 삽입하는 대신 서로 다른 공간에 삽입하는 방법입니다. 그러나 이러한 방법은 복잡하고 제한된 컴퓨터 리소스를 불필요하게 사용하기 때문에 성능 저하 문제를 일으킬 수 있습니다.