with with

hash table은 해시 함수를 이용해서 어떠한 입력이라도 특정 정수로 치환된 주소에 데이터를 저장할 수 있는 자료구조로 일반적으로 O(1)의 시간복잡도를 갖는다. 사실 해시함수를 구현하기에 따라 해시 테이블의 탐색 시간 복잡도가 크게 차이날 수 있는데, 이 포스트는 자료구조의 해시 테이블를 다루는 것 보다, 데이터베이스에서 데이터를 다룰 때 해시 테이블을 사용하는 방식을 다루기 때문에 깊은 내용은 생략합니다. 해시 테이블을 설계함에 있어 몇가지 부분에서 Trade-off가 요구됩니다. - Hash function 해시 함수는 큰 범위의 입력 값을 작은 도메인으로 줄여야 합니다. 그 과정에서 필연적으로 다른 입력에 대해 같은 값(collision)이 나올 수도 있습니다. 이 과정에서 collision ..