🖥️ 해시 테이블(HashTable)이란?
해시테이블은 Key-Value 형태로 저장되는 자료구조로, 평균 O(1)의 시간복잡도를 가짐. 흔히, HashMap이라고 불리기도 함.
key 값을 Hash Function을 이용해, Hash Table에 저장할 위치를 정함.
대표적인 Hash Function에는 Division Method(mod 연산)가 있음.
🖥️ DAT(Direct Access Table)
키 값을 인덱스로 직접 사용하여 배치하는 자료구조이며, 빠른검색과 삽입•삭제가 가능함.
최대값에 1을 더한 크기의 배열을 만든 다음(0 기반 인덱스로 가정) 값을 인덱스로 사용함.
🖥️ 충돌은 왜 발생하는가?
해시 충돌은 어떤 entry를 넣으려고 할때, Hash Function으로 찾은 위치에 이미 다른 entry가 존재하는 경우 발생함.
즉, 다른 키 값일때, Hash Function을 통해 같은 값을 가지게 되는 경우 해시 출돌이 발생함.
🖥️ 충돌 해결방법 - 체이닝(Chaining)
- 같은 주소로 해싱 될 때, 연결 리스트(Linked List)로 연결하는 방식.
- 각 인덱스는 자체 목록이 되므로 동일한 해시 인덱스를 가진 값이 동일한 목록에 배치됨.
- 추가 공간 활용
🖥️ 충돌 해결방법 - 개방주소법
출처 :
게임 개발 공부 시작!