해쉬 테이블은 dynamic set을 구현하는 효과적인 방법 중 하나입니다.적절한 가정하에서 평균 탐색, 삽입, 삭제시간 o(1)보통 최악의 경우 O(n) 해쉬 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장h : U -> {0,1,...,m-1}, 여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합키 k가 h(k)로 해슁되었다고 말함해쉬 함수의 예모든 키들을 자연수라고 가정. 어떤 데이터든지 자연수로 해석하는 것이 가능예 : 문자열 ASCII코드, CLRS 해쉬 함수의 간단한 예 : h(k) = k %m, 즉 key를 하나의 자연수로 해석한 후 테이블의 크기 m으로 나눈 나머지 항상 0~m-1 사이의 정수가 됨충돌 (collision)두 개 이상의 키가 동일한 위치로..
