해시테이블을 구현할 때 고민되는 부분이 몇 가지 있다. 해시 테이블 크기와 해시 함수이다. 먼저 해시 테이블 크기를 정해보자. 해시 테이블의 크기 해시 테이블에서 원소의 개수 / 테이블의 크기를 load factor라고 하고, 원소의 최대 개수는 곧 삽입의 최대 횟수이다. load factor를 작게 유지하면 충돌이 덜 생겨 연산들이 O(1)에 동작하겠지만 cache hit rate가 줄고 메모리를 많이 차지한다. 반대로 load factor를 크게 유지하면 충돌이 많이 생겨 성능에 악영향을 줄 수 있다. load factor를 정하는 방식은 체이닝 기법이냐 개방 주소화 기법이냐에따라 나뉜다. 먼저 체이닝 기법은 충돌이 어느 정도 발생하더라도 load factor를 1 이하로 둔다. 반면 개방 주소화 기..

일반적으로 효율적인 데이터의 저장 방법(직접 주소 테이블) 일반적으로 (key : value) 데이터를 기본 자료구조에 배치하면 탐색에 O(N)이 걸리거나 삽입/삭제에 O(N)이 걸린다. 가장 빠른 방법이 배열의 index로 key를 사용했을 때 탐색에 O(1) 시간이 걸린다. 그러나 key값의 종류가 대략 10^16 정도로 매우 많아지면 똑같이 배열로 구현할 수 있을까? 현실적으로 불가능하다. 혹은 key값이 최대 2000인데 실제 존재하는 key값은 0, 2000 뿐이라면 배열의 1~1999까지의 공간은 낭비된다. 이러한 문제들을 해시 테이블을 통해 해결할 수 있다. 해시 테이블이란? 해시 테이블은 임의의 길이를 가진 key값에 해시함수를 적용해 고정된 크기의 index를 생성하여 그 index에 값..