해시 테이블은 자료구조에 해당하는 부분이지만 알고리즘 스터디를 하면서 공부하게 되었습니다.

1.해시 테이블(Hash Table)이란?

해시 테이블은 직접 번지화를 피하기 위한 효율적인 탐색 방법이다.
해쉬 테이블은 해시 함수를 사용하여 변환된 값을 index로 삼아 키(key)와 데이터(value) 를 저장한다.

해싱(Hashing)이란?
임의의 길이의 값을 해쉬 함수를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.

해시값이란?
"키 k를 갖는 원사가 위치 h(k)에 해시된다"라고 말하고 k(k)는 키 k의 해시값이 된다.

해싱 과정을 통해 계산된 코드는 키의 자료형으로 보통 int 혹은 long이 된다.

그 다음엔 hash(key)%array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.

여기서 중요한 점은 해싱을 이용하는 경우 동일한 인덱스가 사용될 수 있다는 점이다.
이 상황을 충돌이라고 한다.충돌을 없앨수 있는 것이 가장 적절해보이나 이는 불가능에 가깝기 때문에 해결 방법이 여러가지 제시된다.

그중 하나는 체이닝(chaining)에 의한 충돌 해결이다.
같은 값을 가지는 위치에 해시 되는 모든 원소를 연결리스트에 넣어서 해결하는 방법이다.

2.해시테이블의 장점

1.적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
예) HDD, Cloud에 존재하는 많은 데이터들을 유한한 개의 해시(Hash)값으로 매핑하여 작은 크기의 캐쉬 메모리로 프로세스 관리가 가능하다.

2.배열의 인덱스(index)를 사용해서 검색, 삽입, 삭제가 빠르다. (평균 시간복잡도 : O(1))

인덱스를 사용해서 배열의 검색이 빠르다는 것은 당연한 소리이다. 하지만 삽입, 삭제는 왜 O(1)인가?
여기서의 인덱스는 데이터만의 고유한 위치이기 때문에 만약 삽입이나 삭제를 한다고 해도 다른 데이터로 채울 필요가 없다. 즉, 삽입이나 삭제할 때 데이터를 이동할 필요가 없기 때문이다.

3.키(key)와 해시값(Hash)이 연관성이 없어 보안에도 많이 사용된다.

4.데이터 캐싱(Data Caching)에 많이 사용된다.

get(key), put(key)에 캐시 로직을 추가하면 자주 hit하는 데이터를 바로 찾을 수 있다.

3.해시 테이블의 단점

1.충돌
2.공간 복잡도가 커진다.
3.순서가 있는 배열에는 어울리지 않는다.
4.해시 함수 의존도가 높아진다.

4.해시테이블의 시간 복잡도

해시 테이블을 통해 집합 K를 탐색하는데 소요되는 시간은 O(1)만큼의 소요된다.
그러나 충돌이 발생할 경우에는 O(N)까지 시간 복잡도가 증가될 수 있다.
충돌을 방지하기 위한 방법은 데이터의 규칙성을 방지하기 위한 방법인데 이는 공간을 많이 잡아 먹는다는 치명적인 단점이 존재한다.

또한 테이블이 꽉 차있는 경우라면 테이블을 확장해주어야 하는데,이는 매우 심각한 성능의 저하를 불러올수 있기에 가급저깅면 확장을 하지 않도록 설계하는 것이 중요하다.

참조
Introduction to Algoritms
https://mangkyu.tistory.com/102
https://hee96-story.tistory.com/48

학기중이라 주말같은 시간이 가능한 날짜에 더 보강해서 내용을 추가할 계획입니다.