04_Hash.md

해시 테이블

해시테이블이 무엇인지 설명해보세요.

• 헤시 테이블은 Key-Value 맵핑으로 데이터를 저장하는 자료구조입니다. 어떤 Key 값에 대해서 해당 키에대한 고유한 인덱스를 해시함수를 통해 만들고 Value에 이 인덱스를 부여합니다. Key 값을 넣으면 바로 Value가 나오기 때문에 O(1) 의 시간복잡도를 가집니다.

해시 충돌에 대해서 설명해보세요.

• 해시 충돌은 어떤 키 값들이 해시 함수를 통해 동일한 해시값을 가지게 되는 현상을 의미합니다.

그럼 해시 충돌을 해결할 수 있는 방법을 말해보세요.

• 두 가지 대표적인 방법이 있습니다. 분리 연결법과 개방 주소법입니다.
• 분리 연결법은 어떤 Key 에 대한 해시함수로 얻은 해시가 이미 존재하여 충돌이 일어났을 때 기존에 있던 데이터 뒤에 새로운 데이터를 연결시켜주는 방법입니다. 데이터에는 Key와 Value 가 모두 저장되고 Key 값을 탐색해서 입력된 Key 와 일치하는 데이터의 Value 를 반환합니다.
• 개방주소법은 어떤 Key 에 대해 해시 충돌이 일어났을 때 다른 비어있는 인덱스를 찾아 데이터를 저장하는 방법입니다. 다른 인덱스를 찾는 방법은 동일한 방법을 적용해서 진행해야합니다.

분리 연결법에는 어떤 단점이 있을까요?

• 해시충돌이 일어날 때마다 같은 인덱스에 새로운 데이터를 계속 연결시키기 때문에 같은 해시에 대한 충돌이 여러번 일어나면 다른 인덱스에 빈 공간이 있는 경우에도 한쪽으로 데이터가 쏠릴 수 있습니다. 또한 데이터 저장을 위해 추가적인 메모리를 사용해야한다는 단점도 있습니다.