해시 테이블

해시 테이블(Hash Table)

해시는 내부적으로 배열을 사용해서 데이터를 저장한다. 그래서 평균적으로 O(1)의 시간 복잡도로 검색이 가능하다.

(collision때문에 평균적으로 라는 말이 붙는다.) 하지만 문제는 이 인덱스로 저장되는 키(key)값이 불규칙하다는 것이다.

그래서 특별한 알고리즘을 이용하여 저장할 테이터와 연관된 고유한 숫자를 만들어 내 이를 인덱스로 사용한다.

 

이 특별한 알고리즘을 해시 함수(hash function)이라고 한다.

 

좋은 해시 함순는 키 전체를 참조해서 해시 값을 만들어 낸다. 해시 함수를 무조건 1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 중요하다. Collision이 많아질 수록 Search의 시간 복잡도가 O(1)에서 O(n)에 가까워 지므로, 좋은 해시 함수를 사용하는 것은 성능에 중요한 영향을 끼친다.

 

충돌 해결(Resolvce Confilct)

1. 개방주소법(Open Address)

해시 충돌이 발생하면 다른 해시 버킷에 해당 자료를 삽입하는 방식이다.

2.  분리연결법(Seperate Chaining)

해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정하는 방식이다.