해시 함수
-
해시 테이블 알고리즘프로그래밍 기초/알고리즘 2021. 12. 22. 14:42
해시 테이블 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조로 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. ※ 테이블의 모든 영역에 값을 적절하게 분배하지 못하는 경우 성능이 떨어질 수 있다. 해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때..