'set' 태그의 글 목록

정의 해시 테이블(hash table)은 키(key) (필요한 경우 연관된 value)를 저장, 삭제, 열람 할 때 평균 O(1) 만큼 시간이 걸리는 것을 목표로 한다. 이를 위해, key는 hash 함수를 통해 변환되어 hash code (int)로 array (=hash table)에 저장된다. key가 hash 함수를 통과하여 array에 매핑된 결과는 가급적 균일하게 분포하도록 hash 함수를 설계하는 것이 필요하다. (주의깊은 해싱함수의 설계에도 불구하고) 두 key가 array의 같은 위치에 매핑되는 것을 충돌(collision)이라고 부른다. 이를 처리하기 위해 각 위치에 연결리스트(linked list)를 두거나 open addressing, linear probing 등의 방법을 활용한다..