1. Hash란?
Hash는 데이터를 고정된 크기의 값으로 변환하는 과정 또는 그 결과를 말한다. 이때 변환된 값은 보통 정수형이나 문자열로 나타내며, 원본 데이터와 관련된 유일한 값을 생성하려는 목적을 가진다. 이를 해시 값(Hash Value) 또는 해시 코드(Hash Code)라고 한다.
왜 Hash를 사용할까?
Hash를 사용하는 이유는 데이터를 빠르게 비교하거나 찾기 위해서이다. 예를 들어, 특정 데이터가 리스트나 배열 안에 있는지 확인할 때, 모든 데이터를 하나하나 비교하지 않고, 해시 값을 통해 빠르게 확인할 수 있다. 해시 값을 사용하면 데이터를 고유한 번호로 변환하여, 비교 및 검색 작업을 효율적으로 할 수 있다.
Hash는 어떻게 더 데이터를 빨리 찾을 수 있을까?
1. 저장 (Insert) 과정
키가 들어오면, 이 키는 해시 함수에 의해 해시 값으로 변환된다.
이 해시 값을 사용하여 해시맵 내부의 특정 위치(버킷)에 값을 저장한다.
예를 들어,my_dict['apple'] = 10이라는 저장이 들어오면, 'apple'을 해시 함수에 넣어 해시 값을 계산하고, 그 해시 값을 기반으로 해시맵에서 저장할 위치를 찾는다.
값은 해당 위치에 저장된다.2. 검색 (Search) 과정
키를 검색하고 싶다면, 그 키에 대해 해시 함수를 사용해 해시 값을 계산한다.
계산된 해시 값을 통해 저장된 위치를 찾아 해당 값을 빠르게 확인할 수 있다.
예를 들어,my_dict['apple']을 검색하면, 'apple'에 대해 해시 값을 계산하고, 그 해시 값이 가리키는 위치에 있는 값(즉,
10)을 빠르게 가져올 수 있다.
해시 함수 (Hash Function)
해시 함수(Hash Function)는 원본 데이터를 입력받아 고정된 크기의 해시 값을 반환하는 함수이다. 예를 들어, 문자열 "apple"에 대해 특정 해시 함수를 적용하면 항상 동일한 해시 값을 반환하게 된다.
간단한 예시로, 문자열 "apple"을 숫자로 변환하는 해시 함수가 있다고 가정할 때, 이 함수는 "apple"이라는 문자열을 특정 수치 값으로 변환해 준다. 이 수치 값은 해당 문자열에 대한 유일한 식별자로 사용될 수 있다.
2. HashMap (해시맵)
HashMap은 키(Key)와 값(Value)을 쌍으로 저장하는 자료구조이다. 해시맵의 핵심은 해시 함수를 이용해서 각 키를 해시 값으로 변환한 뒤, 그 값을 사용하여 빠르게 값을 찾고 저장하는 것이다. 해시맵에서 키는 반드시 고유해야 하며, 값은 그 키에 대응하는 데이터를 나타낸다.
HashMap의 작동 원리
- 키에 대해 해시 함수를 적용하여 해시 값을 계산한다.
- 이 해시 값을 통해 값을 저장할 위치를 찾는다. 해시맵은 이 위치에 해당하는 버킷(Bucket)에 값을 저장한다.
- 값을 검색할 때, 키를 해시 함수에 넣어 해시 값을 구한 후, 해당 버킷에서 값을 찾는다.
장점
- 빠른 검색 및 삽입: 해시맵은 평균적으로 O(1) 시간 복잡도를 가진다. 즉, 데이터를 저장하거나 검색하는 데 걸리는 시간이 일정하다.
- 고유한 키: 키를 해시값으로 변환하여 고유성을 보장하고, 값을 빠르게 찾을 수 있다.
단점
- 충돌(Collision): 서로 다른 키가 같은 해시 값을 가지는 경우가 발생할 수 있다. 이를 해시 충돌이라고 하며, 충돌을 해결하는 방법으로 체이닝(Chaining)이나 오픈 어드레싱(Open Addressing) 기법을 사용할 수 있다.
이에 관해서는 본문에서는 너무 길어지므로, 나중에 정리하도록 하겠다.
3. 해시맵 예시
파이썬에서는 dict 자료형이 사실상 해시맵을 구현한 것이다. 예를 들어, 다음과 같이 dict를 사용할 수 있다.
# 해시맵 예시
my_dict = {'apple': 10, 'banana': 5, 'orange': 7}
# 특정 키의 값 조회
print(my_dict['apple']) # 10
# 값 추가
my_dict['grape'] = 3
# 값 수정
my_dict['banana'] = 6
# 키 삭제
del my_dict['orange']
print(my_dict)이 예시에서 my_dict는 해시맵으로 작동하며, 'apple', 'banana', 'orange' 등의 키에 각각 값을 매핑해 둔다. 해시맵은 내부적으로 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 바탕으로 값을 빠르게 검색하거나 삽입할 수 있다.
4. HashMap이 Hash의 서브클래스인 이유
HashMap은 Hash의 개념을 바탕으로 만들어진 자료구조이다. Hash는 단순히 데이터를 고정된 크기의 값으로 변환하는 과정이라면, HashMap은 이러한 해시 값을 사용하여 키와 값을 효율적으로 매핑하는 자료구조다. 즉, 해시맵은 해시 값을 기반으로 데이터를 저장하고 찾는 구조이므로, 해시의 개념을 확장한 형태로 볼 수 있다.
5. 정리
- Hash는 데이터를 고정된 크기의 값으로 변환하는 과정이며, 이 값을 해시 값이라고 한다.
- HashMap은 해시 값을 사용해 키와 값의 쌍을 저장하는 자료구조로, 키를 해시 값으로 변환하여 데이터를 빠르게 검색하고 삽입할 수 있게 해준다.
- 해시맵의 핵심 원리는 해시 함수를 사용하여 키에 대한 해시 값을 계산하고, 이를 통해 데이터를 빠르게 저장하고 찾는 데 있다.
- 다만, 해시맵은 해시 충돌로 인해 발생할 수 있는 문제가 존재하므로 이를 주의해야 한다.
