해시법

해시법

hashing

데이터를 저장할 위치(=인덱스)를 간단한 연산으로 구하는 것

검색/ 추가/삭제 효율적으로 수행할 수 있음

해시 충돌

키와 해시값은 일반적으로 다대일

저장할 버킷이 중복되는 현상을 충돌 이라고 함

충돌이 발생할 경우 (체인법/오픈주소법) 으로 대처 가능

체인법

해시값이 같은 데이터를 체인 모양의 연결리스트로 연결하는 방법

( = 오픈 해시법)