신입 개발자 기술면접 실전 기출 : 해시

면접관 : 해시 테이블에 대해서 설명해주시겠습니까?

 

나 : 해시 테이블은 연관배열 구조를 이용하여 Key에 Value를 저장하는 자료구조입니다.

 

면접관 : 연관배열이 뭔가요?

 

나 : 연관배열은 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 알아낼 수 있는 자료구조를 의미합니다.

 

면접관 : 계속 설명해 보세요.

 

나 : 해시는 리소스를 포기하고 속도에 치중한 자료구조입니다. 특정 키 입력을 넣으면 해시 함수를 통해서 특정 연산을 통해 특정 값으로 변환시켜 줍니다.

 

면접관 : 특정 연산의 예를 간단히 들어주실래요?

 

나 : 예를 들어서 들어오는 Key값을 모두 100으로 나누는 연산을 한다면 110, 120, 130 이란 값이 들어올 때 10,20,30으로 변환시켜줍니다.

 

면접관 : 리소스를 포기하고 속도에 치중했다고 하셨는데 그 의미가 무엇입니까?

 

나 : 아까의 예를 다시 들어서 모든 Key값을 100으로 나누는 경우 110, 210 이 들어오면 둘 다 10이라는 같은 값을 가지게 되는데 이 때 해시 충돌이 일어났다고 합니다. 해시 충돌을 해결하는 방법 중 하나는 linked list 를 이용해서 이미 키에 해당하는 값이 있는 경우 linked list 에 키, 값 쌍을 연결해 넣어주는 방식입니다. 이렇게 되면 테이블을 이용하려고 만든 구조가 리스트로 계속 이어지기만 해서 리소스를 많이 소모하게 됩니다.

 

면접관 : 또 다른 해시 충돌 해결 법이 있을까요?

 

나 : Linear Probing (선형 탐사) 이란 방법을 이용합니다. 이 방법은 해당 인덱스에 이미 값이 있는 경우 자리가 빈 인덱스를 찾아서 값을 넣어두는 방식입니다. 그러다가 더 이상 Linear Probing 을 할 자리가 없는 경우에 table resizing 을 통해서 테이블의 크기를 늘린 후, 기존의 데이터를 다시 해시 함수에 넣어서 재정렬을 하는 방법입니다.

 

면접관 : 해시의 시간복잡도는 어떻게 될까요?

 

나 : 해시 충돌이 일어나지 않는다면 O(1) 의 상수시간 접근 시간을 가집니다. 해시 충돌이 발생하면 버켓 안의 모든 값들을 조사해야 하므로 O(N)의 접근 시간을 가집니다.