자료구조 해싱

해시: 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 변경한 값

Key - Value를 저장해둔 자료구조

O(log2 n)으로 효율적인 자료구조 이다

 

해싱을 통해서 메모리에 적재

값을 적재하기 위해 나머지를 사용하는데 적은 값으로 설정하면 중복, 높은 값으로 설정하면 과다한 메모리 사용이 된다.

 

체이닝 방식

해시 충돌이 발생할 경우 동일한 해시값에서 해당하는 Key 끼리 연결

LinkedList 자료구조를 이용해 해시값 연결

 

오픈 어드레스 방식

해시 충돌 시 다른 버킷에 데이터를 삽입 비어있는 버켓을 찾을 때 까지 탐색