해시테이블이란?

해시테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다.

이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있습니다.

삽입, 삭제, 탐색 시 **평균적으로 O(1)**의 시간복잡도를 가지며, **최악의 경우 O(N)**의 시간복잡도를 가집니다.

unordered_map으로 구현합니다.

해시

다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 mapping한 값

해싱

임의의 데이터를 해시로 바꿔주는 일이며 해시 함수가 이를 담당

해시 함수

임의의 데이터를 입력으로 받아 일정한 길이의 데이터로 바꿔주는 함수

충돌 해소 전략

해시테이블과 연결리스트로 LRU 알고리즘 구현하기

탐색이 빠른 해시테이블과 삽입과 삭제가 빠른 연결리스트의 장점만 콜라보레이션하기 위함!