[자료 구조][C언어] 해싱(hashing)
2018.12.09
해싱(hashing)? 해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다. 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다. 슬롯이 한개일 경우 무조건 충돌이 일어나며 우리는 충돌은 피할 수 없으므로 최대한 적게 일어나는 쪽으로 설계 해야 한다. 슬롯이 한개일 경우에는 오버플로우와 충돌은 같다. Hashi..