알고리즘/자료구조 (1) 썸네일형 리스트형 해시(Hash) 해시함수? 해시 함수(짧게 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다. 어떠한 데이터 집합 U에 대해 K 집합으로 변환 또는 매핑하게 되고, 이 때 사용되는 함수를 해시함수라고 부릅니다. 해시 함수는 '입력 값의 범위' 보다 '출력 값의 범위'가 좁기 때문에 다른 입력이더라도 동일한 값이 출력되는 경우도 존재합니다. 다른 값이지만 드물게 같은 해시 값을 갖는 이러한 경우를 '해시 충돌'이라고 합니다. (그림1에서 Sandra Dee 와 John Smith는 02라는 동일한 hash 값을 가지게 됩니다) 해시 충돌은 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 항상 존재하게 됩니다. 이러한 상황을.. 이전 1 다음
