해쉬 overflow

1. Hash

데이터를 저장하고 찾는데 사용되는 자료 구조의 한 종류. 찾고자 하는 문자열을 특정한 함수(hash function)로 처리해 얻은 값으로 데이터의 위치를 찾는 방법을 말한다.

데이터를 찾는 속도가 데이터 개수의 영향을 거의 받지 않는 특성을 지니고 있어, 효율적이고 빠르게 데이터의 위치를 찾을 수 있다. 다른의미로 데이터베이스에서 임의의 레코드를 빠르게 찾아가기 위한 직접 파일 구조를 말하기도 한다.

2. Hash table

레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간을 말한다. 레코드들을 보조 기억 공간에 저장할 때는 그 공간 내의 주소와 레코드 키를 한 단위로 해시 테이블에 보관하고, 이 해시 테이블을 주기억 공간에 보관하기도 한다.

참고) 버킷(Bucket) : 어떤 종류의 레코드를 몇 개씩 묶은 것을 기억하는 장소이다. 이 경우 주소는 1버킷에 1개만 붙인다. 또 다른 의미로 여러개의 데이터를 어떤 기준에 의해 묶을 때 같은 부류에 속하는 데이터들의 모임을 말한다.

해시 테이블의 시작 주소로부터 각 버킷들은 연속된 주소를 가지며 그 시작 주소를 기준으로 상대 주소를 산출할 수 있으므로 이 상대 주소를 이용하여 각 버킷들을 구별하면 편리하다.

3. Hashing

여러개의 명칭(identifier)들이 무작위로 들어있는 테이블에서 특정 명칭을 찾고자 하는 경우 원하는 키값을 가지는 테이블 항목을 검색하기 위해 특정한 변환 함수를 이용하여 키값을 항목 의 주소로 직접 바꿔서 검색하는 방법을 해슁이라 한다. 이때 변환 함수는 해쉬 함수(hash function)라 한다.

명칭 테이블에서 키 값과 일치하는 명칭을 찾는 방법으로는 테이블에 있는 각각의 명칭을 키 값과 차례로 비교하는 방법이 있다. 이 방법을 사용하면 최악의 경우 n회의 비교가 필요하다. 해슁을 이용하면 해쉬 함수가 키값을 해당 주소로 단번에 변환해 주므로 매우 빠른 검색이 가능하다.

정적 해싱은 고정 크기의 테이블을 이용하여 해슁하는 방법으로서 한번 저장된 명칭의 상대적 위치가 변경되지 않는다. 해싱을 이용하지 않는 경우에는 명칭들의 모든 가능한 조합을 수용할 수 있도
록 명칭 테이블을 만들어야 한다.

조합 가능한 명칭들 중에 실제로 존재하는 명칭들의 수는 매우 적기 때문에 대부분의 공간은 낭비된다. 명칭 테이블의 기억공간 낭비를 막기 위해 해쉬 테이블을 사용한다. 해쉬 테이블은 b개의 버켓(bucket)으로 구성되고, 하나의 버켓은 s개의 슬롯(slot)으로 구성된다. 각각의 슬롯에는 명칭 테이블 항목처럼 하나의 명칭이 저장된다.

해쉬 테이블의 크기는 필요에 따라 달리할 수 있는데 일반적인 명칭 테이블보다는 크기가 현저히 작다. 하나의 버켓에 여러개의 슬롯을 두는 이유는 서로 다른 두개의 명칭이 해쉬 함수에 의해 동일한 주소로 변환되는 경우 두 명칭을 같은 버켓에 저장하기 위해서이다.

해슁을 하는 경우 서로 다른 두개 이상의 명칭이 해쉬 함수에 의해 동일한 주소로 변환되는 경우가 있다. 이 현상을 "충돌(collision)"이라 한다. 충돌이 자주 발생하면 탐색 시간이 길어지는 등 성능이 저하되므로 해쉬 함수를 수정하거나 해쉬 테이블의 크기를 적절히 조절해 주어야 한다.

충돌이 발생한 경우 같은 버켓에 있는 다른 슬롯에 명칭을 저장하면 된다. 그러나 슬롯의 갯수만큼 충돌이 생기면 빈 슬롯이 소진되어 오버플로우(overflow)가 생길 수 있다. 오버 플로우가 발생하면 해슁에 의해 원하는 명칭을 찾을 수 없게 되므로, 오버 플로우를 해결하기 위한 방법이 고안되어야 한다.

[출처] Hash(해쉬) 기본개념 이해|작성자 몽키몽키