해시란?

해시는 특정 데이터를 특정한 계산방법으로 치환하여 저장 하는 방법입니다. 이러한 일을 하는 이유는 크게 2가지인데,

하나는 데이터의 위변조를 확인하는 수단으로 쓰이고, 또 하나는 많은 양의 데이터를 인덱싱 하여 빠르게 찾기 위해 사용합니다.

해시 충돌

인덱싱 목적으로 사용한다면, 다른 데이터가 같은 해시값으로 변환 될 수있는데, 이것을 충돌이라고 합니다.

이를 해결하기 위하여는 크게 3가지 방법이 있습니다.

첫번째로는 로우 체이닝 기법입니다. 해시테이블을 만들고, 저장을 하되, 저장 하는 도중에 충돌이 일어나게 되면,

리스트로, 그 뒤에 차례대로 연결 하게 됩니다. 만약 충돌이 너무 많이 일어난다면, 탐색하는데 시간이 많이 늘어나게 됩니다.

두번째로는, 개방주소법이 있습니다. 개방주소법은 충돌이 일어나면, 해당 데이터를 일정한 규칙에 의하여 다른곳에 저장하는 방법입니다.

예를들어 해당 데이터 바로 뒤에 저장한다던가, 충돌이 일어나지 않을 때까지 다시 해싱을 하는 방법 등이 있습니다.

마지막으로 재해싱 하는 방법으로, 위의 방법을 이용 할 때 데이터가 한군데에 집중하여 변환되어 실용성이 떨어질 때 하는 방법으로,

새로운 해시 테이블과, 해시 계산식을 만드는 방법 입니다. 새로운 해시 테이블을 만들어 옮겨야 하기 때문에, o(n) 의 시간이 발생합니다.

시간복잡도

해시의 탐색에는 O(1+a)의 시간이 걸립니다. a는 중복으로 인하여 체이닝이나 개방주소법에 의해 접근 하는데 걸리는 시간을 의미합니다. 삽입, 삭제 또한 O(1+a) 의 시간이 걸립니다.