[DS] Hash(해시)

728x90

Hash Tables는 Key Value System을 이용하여 자료를 정리한다

그 예시로는 사전이 있다

배열과 해시 테이블을 비교해보자

예시로 레스토랑에서 메뉴를 배열과 해시 테이블에 저장한다고 해보자

이 때 메뉴에서 피자의 가격을 찾는다고 생각해보자

만약 배열의 메뉴에서 찾는다면 선형검색을 통해 찾아야 한다

이는 시간이 오래걸리게 된다

메뉴를 해시에 저장하면 아래와 같은 모양이 되고, 여기서 피자의 가격을 찾으려면 그냥 key값으로 pizza를 넘겨주면 그에 대한 value로 피자의 가격이 나올 것이다

자, 여기서 첫번쨰 배열에 저장했을 때의 시간 복잡도는 O(N)이라고 할 수 있다

이는 배열의 원소가 많아질수록 시간이 오래걸리게 된다 -> Linear Time(선형 시간)

하지만 해시 테이블의 경우에는 O(1)로 Constant Time(상수 시간)을 갖게 된다

해시에서는 원소 검색, 추가, 삭제 모든 연산에 대해서도 시간 복잡도는 O(1)이다

해시를 좀 더 효율적으로 사용하는 방법을 예시를 통해 알아보자

만약 나라들이 체크되었는지 여부를 확인하려고 할 때 배열로 구현하면 선형 검색을 해야하므로 시간이 오래걸린다

하지만 해시 테이블을 사용해서 아래처럼 표현한다면, 특정 나라가 체크되었는지 확인하려면 key값만 넘겨서 확인하면 되므로 훨씬 빠르게 수행이 가능하다

해시 테이블 또한 value는 index 별로 배열에 저장된다

그렇다면 어떻게 key 값으로 배열의 인덱스를 찾아 value를 반환하는걸까?

답은 Hash Function이다!

Hash Function이 key값을 숫자로 바꿔주고 그 숫자가 value array의 index가 되는 것이다

여기서 해시 테이블의 문제가 발생한다!

바로 Collision(해시 충돌)이다

각기 다른 Key에 대해 해시함수가 동일한 숫자를 준 경우에는 충돌이 발생하게 된다

이에 대한 해결 방법은 중복되는 array안에 또 array 넣기

이는 1차로 Hash function을 통해 검색하고, 검색된 배열 내에서 선형 검색을 통해 value를 찾게 되는 것이다

따라서 해시 테이블은 항상 O(1)의 시간 복잡도를 갖진 않는다

또한 대부분의 프로그래밍 언어들은 해시 테이블과 해시 함수들을 미리 만들어놨기 때문에 우리가 직접 구현해서 사용할 필요는 없다!

여기까지가 Hash Table 맛보기고 실제 사용 방법은 다음 글에서 다시 정리해보도록 하겠다!

728x90

야미의 맛있는 코딩일지🐰