[CS 노트] : Hash table에 대해서

Hash table이란?

효율적인 탐색을 위한 자료구조로 key-value 쌍의 데이터를 입력받는다. Hash function h에 key값을 넣어 얻은 해시값h(k)를 위치로 지정해 키,벨류 데이터 쌍을 저장하고 저장,삭제,검색의 시간복잡도는 O(1)이다.

 

Direct address table를 미리 알아보자

직접 주소화 테이블은 Key 값을 index에 저장하는 방식인데 문제는 메모리 공간이 낭비된다. 예를 들면 key 값이 1000부터 시작하면 1부터 999까지는 비어 있게 된다. 또, 다양한 자료형을 담을 수 없다는 문제도 있는데 String으로 들어온 경우 Key 값을 바로 index로 사용하는 특성상 활용이 불가능하다는 문제가 있다.

 

이런 단점을 보완하는 게 Hash table이다.

 

Hash table 자세히 !

Key-value 데이터 쌍을 저장하기 위한 방법이다. Key는 무조건 존재해야 하고 중복되면 안 된다. 여기서 key-value를 저장할 수 있는 공간을 slot, bucket이라고 한다.

 

서로 다른 key 값인데 hash 값이 같은 경우 Collision(충돌)이 발생한다. 이때 해결 방법은 다음 강의에서 다룬다.

 

시간 복잡도는 저장, 검색, 삭제는 O(1)인데 Collision인 경우 O(n)이 될 수 있다. 공간 효율은 좀 떨어지는데 데이터가 저장되기 전에 미리 공간을 확보해야 하기 때문에 덜 채워지거나 더 채워지는 경우가 있다.

 

좋은 hash function?

만능인 hash function은 없지만 연산 속도가 빠르고 해시 값이 최대한 겹치지 않아야 한다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.