[알고리즘] 해시테이블과 충돌 회피 방안

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

2023.08.19