상상면접 1 : 해시 [CS]

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

 

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

 

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

 

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

 

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

 

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

 

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

 

나 : 예를들어서 들어오는 key값을 모두 100을 나누는 연산을 하게되면 100,200,300 같은 값들이 들어오게 되면 1,2,3의 값으로 변환을 시켜줍니다.

 

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

 

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

 

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

 

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

 

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

 

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

 

 

출처1 : https://www.youtube.com/watch?v=xls6jEZNA7Y

출처2 : 해시 나무위키