해시테이블 (Hash Table)개념 졸업하기
해시테이블 (Hash Table)개념 졸업하기 — #해시테이블 #hashtable #개발자의도구들 AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였...
#해시테이블 #hashtable #개발자의도구들
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다.
해시란?
해시란 해시함수에 특정 key를 대입하였을 때 나온 결과값입니다. 키들의 대표값으로 볼 수 있습니다.
해시함수는 알고리즘 중 하나입니다. 어떠한 형태로도 작성이 가능하지만, 해시충돌을 고려해야하기 때문에 잘 만드는 것이 중요합니다. (해시충돌은 아래에 나와있습니다)
해시가 필요한 이유
앞
서 해시는 key들의 대표값이라고 했습니다. 만약 key의 대표값 없이 자료를 저장한다면 어떻게 될까요?
철수와 영희의 수학점수를 저장하는 자료구조를 만들어 봅시다. 각각의 수학점수는 95점, 90점입니다. 이때 철수를 키값으로 검색하면 철수의 수학점수인 95가 출력되고, 키값을 영희로 하면 영희의 수학점수인 90이 출력되어야 합니다.
해시테이블 및 딕셔너리를 사용하지 않고 어떻게 자료를 저장할 수 있을까요?
배열 두개를 사용하여 자료구조를 만들 수 있습니다. 키를 저장하는 배열과, 수학점수를 저장하는 배열을 각각만듭니다.
이름과 점수가 똑같은 순번에 위치하도록 구현 후, 철수를 입력받고 키 배열의 인덱스를 구합니다. 구한 인덱스를 점수 배열에 입력하면 데이터가 출력됩니다.
문제는 인덱스의 크기인데요. 철수라는 문자열은 사실 숫자로 표현이 가능합니다. 대략 4btye라고 가정한다면. 2³²으로 42억이 넘는 비트값을 가집니다. 즉, 42억이 넘는 크기의 배열을 생성해야합니다.
단 두글자에 이 정도 크기의 배열이 필요한데, 글자수가 커진다면 훨씬 더 큰 배열이 필요합니다.
이때 고안된 게념이 바로 해시입니다. 해시함수를 만들어 키를 입력받아 결과값 해시로 인덱스를 결정하는 겁니다. 이렇게 된다면 불필요하게 큰 배열이 필요가 없을 겁니다.
해시함수: 나머지
가장 간단하게 생각해볼 수 있는 해시함수는 바로 나머지 입니다. 예를들어 13으로 나눈 나머지를 해시값으로 사용한다면 key에 따른 hash값은 다음과 같습니다.
이렇게 특정 key값을 해시함수에 넣고 그 결과 hash값을 인덱스로 사용하여 데이터를 저장할 수 있습니다.
해시충돌
위의 나머지 예시에서 key값이 14인 경우 문제가 발생합니다. key-14의 해시값은 1로 key-1과 동일한 해시값을 갖습니다. 서로다른 key값으로 부터 동일한 해시값이 발생할때를 해시충돌이라고 부릅니다.
해시테이블의 핵심은 해시충돌에 있습니다. 해시함수를 작성할때 해시충돌이 최대한 발생하지 않도록 해야하며, 해시충돌이 일어날때 자료를 어떻게 저장할지 고민해야합니다.
이런 고민으로부터 다양한 해시함수와, 해시테이블의 구조가 만들어집니다.
시간복잡도
해시의 시간복잡도는 해시함수의 시간복잡도입니다. 보통 O(1)로 해시값이 구해지도록 함수를 작성합니다.
앞서 말씀드린대로 나머지를 해시값으로 갖는 경우도 O(1)가 되겠네요!
해시테이블이란?
HashTable
해시테이블은 앞서 설명한 키, 해시함수, 해시를 활용하여 실제로 만든 자료구조입니다. key-value형태로 자료를 저장하며 내부적으로는 배열로 구현이 가능합니다. 배열의 각각의 원소를 버킷이라고 부르며 버킷에 실제데이터가 저장됩니다.
시간복잡도 & 공간복잡도
해시테이블은 효율적인 자료구조입니다. 기본적인 기능으로 저장, 검색, 삭제가 있는데, 모두 시간복잡도가 O(1)입니다. 이는 해시값을 인덱스로 사용하여 값을 저장하기 때문에, key값에 해당하는 hash인덱스의 값만 다루면 되기 때문입니다.
공간복잡도의 경우 key의 갯수에 따라 늘어나기 떄문에 O(n)이라고 할 수 있습니다.
다양한 종류
해시충돌을 관리하기 위해 다양한 해시테이블이 구현될 수 있습니다. 이번글에서는 대표적인 해시테이블 구현방법 두가지를 소개합니다.
체이닝 해시테이블
각 해시 버킷을 연결리스트로 구성하는 방식입니다. 해시충돌 발생시 동일한 해시 값에 해당하는 데이터들을 연결리스트로 연결하여 저장합니다.
배열의 요소를 링크드리스크로 구현한거라고 생각하시면 됩니다.
개방 주소법 해시테이블
충돌 발생시 빈 버킷에 데이터를 저장하는 방식입니다. 빈 버킷을 어떻게 결정할지에 따라 구현방식이 달라집니다.
선형탐사: 충돌발생시 앞에서 부터 차례대로 빈버킷을 찾아 값을 저장하는 방식입니다.
이차 탐사: 충돌발생시 차례대로 빈버킷을 찾는 것이 아닌 2², 3² 만큼 떨어진 빈버킷을 찾아 값을 저장하는 방식입니다.
이중해싱: 해시값을 한번더 해시함수에 넣어 다른 해시값을 도출하여 저장하는 방식입니다.
해시충돌을 근본적으로 해결하기
앞서서 해시충돌을 피하기 위해 다양한 해시테이블 기법이 존재함을 배웠습니다. 하지만, 해시충돌을 피하는 가장 근본적인 방법은 테이블의 크기를 넉넉하게 잡아두는겁니다.
그 뒤 충돌이 일어나지 않게 잘 만드는 것이 중요하며, 충돌이 발생시 어떻게 관리할지(개방주소법, 체이닝 등)이 중요하겠습니다.
해시와 해시테이블에 대한 설명은 여기서 끝입니다! 사실 해시테이블은 직접 구현할 필요가 없습니다! 우리는 파이썬의 내장 해시테이블인 딕셔너리를 사용하면됩니다! 거기다 딕셔너리는 크기가 제한될 경우 자동으로 늘려주는 기능도 가지고 있습니다!
앞으로는 딕셔너리를 적용하여 풀 수 있는 문제들을 정리해 보겠습니다 : D