해시 테이블이란?

컴퓨터 과학에서 해시 테이블은 키라는 값 목록으로 구성된 데이터를 저장하기위한 데이터 구조로, 배열이라는 해당 값 목록과 쌍을 이룹니다. 예를 들어 업체 이름이 주소와 쌍을 이룰 수 있습니다. 일반적으로 배열의 각 값에는 해시라고하는 위치 번호가 있습니다. 해시 함수는 일반적으로 각 키 값을 해시에 매핑하는 일련의 명령어 또는 알고리즘으로, 비즈니스 이름을 주소, 전화 번호 및 비즈니스 범주에 연결합니다. 해시 함수의 목적은 각 키를 배열의 고유 한 해당 값에 할당하는 것입니다. 이것을 일반적으로 해싱이라고합니다. 해시 테이블이 제대로 작동하려면 해시 함수의 형식이 올바르게 지정되어야합니다.

데이터 세트에서 해시 테이블의 성능은 해시 함수의 효율성에 따라 다릅니다. 좋은 해시 함수는 일반적으로 해당 배열에서 균일 한 키 조회 및 균일 한 매핑 분포를 제공합니다. 두 개의 키가 동일한 해당 값에 할당되면 해시 충돌이 발생합니다. 해시 충돌이 발생하면 해시 함수는 일반적으로 고유 한 해당 값을 찾을 때까지 다시 실행됩니다. 일반적으로 해시 시간이 길어집니다. 해시 테이블의 키 수는 일반적으로 고정되어 있지만 때로는 중복 키가있을 수 있습니다. 그럼에도 불구하고 잘 설계된 해시 테이블에는 각 키를 배열의 고유 한 해당 값에 매핑하는 효과적인 해시 함수가 있습니다.

때로는 해시 테이블에서 비효율적 인 해시 함수가 매핑 클러스터를 생성 할 수도 있습니다. 해시 함수가 기존 키에 대한 매핑 클러스터를 만들면 해당 값을 조회하는 데 걸리는 시간이 늘어날 수 있습니다. 대부분의 해시 함수는 일반적으로 배열에서 사용 가능한 다음 위치를 찾기 때문에 향후 키의 해싱 속도가 느려질 수 있습니다. 큰 값의 클러스터가 이미 할당 된 경우 일반적으로 새 키에 할당되지 않은 값을 찾는 데 시간이 더 오래 걸립니다.

로드 팩터는 해시 함수의 효율성과 관련된 또 다른 개념입니다. 로드 팩터는 해시 테이블에서 해당 배열의 전체 크기와 관련하여 이미 존재하는 해싱의 양입니다. 일반적으로 이미 할당 된 키의 수를 해당 배열의 크기로 나누어 정의합니다. 로드 팩터가 증가함에 따라 양호한 해시 함수는 일반적으로 일정한 지점까지 일정한 수의 충돌 및 클러스터를 계속 유지합니다. 종종이 임계 값은 주어진 수의 키로 해시 함수가 얼마나 효율적인지, 그리고 새로운 해시 함수가 필요한시기를 결정하는 데 사용될 수 있습니다.

많은 컴퓨터 과학 연구자들은로드 팩터가 증가 할 때 충돌이나 클러스터를 생성하지 않는 완벽한 해시 함수를 만들기 위해 노력해 왔습니다. 이론적으로 완벽한 해시 테이블을 생성하는 핵심은 완벽한 해시 함수를 생성하는 것입니다. 일반적으로 연구자들은 완벽한 해시 함수는 부하 계수가 증가함에 따라 일정한 성능 (충돌 및 클러스터 수)을 가져야한다고 생각합니다. 최악의 시나리오에서 완벽한 해시 함수는 여전히 임계 값에 도달하지 않고 지속적인 해싱을 허용합니다.