알고리즘특론 - 해쉬

해시 테이블삽입/삭제/탐색 연산이 지원되는 동적 자료구조* 일반적인 배열 개념을 일반화시킨 것레코드.키 -> (매핑 함수) -> 테이블의 인덱스(주소)* 최악 O(n), 평균 O(1)직접 주소 테이블 direct addressing table* 키 값 자체를 해시 테이블의 인덱스로 사용* key -> T[key]* U = {0, 1, ... , m-1} = T[0..,m-1]* 키의 범위가 크지 않은 경우에만 가능해싱키 값을 기반으로 데이터 저장 위치를 직접 계산* 상수 시간의 데이터 탐색/삽입/삭제 가능해시 함수키 값을 해시 테이블 주소로 변환하는 함수* h: U -> {0, 1, 2, ... , m-1}h(k): 키 k에 대한 해시값* 종류 -> 나눗셈법, 곱셈법, 유니버설 해싱, ............

원문링크 : 알고리즘특론 - 해쉬