✏️ 해시란?
해시란 임의의 데이터를 변환 함수를 사용해 고정된 크기의 데이터로 변환한 값을 의미한다. 특정한 값을 입력받으면 길이에 상관없이 항상 일정한 결과를 만들어내는 것을 말한다.
이러한 특성 때문에 값을 알고 있으면 어떤 결과를 알 수 있으며 정렬을 하지 않고 빠른 검색, 빠른 삽입을 할 수 있다. 파이썬에서는 딕셔너리(dictionary) 자료형이 해시에 해당한다.
✍🏻 해시 테이블(Hash Table)
해싱(hasing)을 사용하여 데이터를 테이블 형태로 저장하는 구조를 해시 테이블이라고 한다. 파이썬의 경우 선언한 Key가 해시 함수를 통해 특정 값으로 변환되어 내부적으로 관리되고, 그에 대응하는 데이터가 연결되는 자료구조를 말한다.
파이썬의 딕셔너리는 key와 value를 인자로 가지며, 선언할 때는 {key: value}의 형태로 선언한다.
fruit = {'apple': 3, 'banana': 2, 'cherry': 7}
fruit['apple']
>>> 3value를 호출할 때에는 리스트와 마찬가지로 대괄호를 사용하고 찾는 키를 직접 넣으면 된다. 단, 선언할 때의 제약이 있는데 Key는 문자열, 숫자, Boolean 형식만 사용이 가능하다. value의 경우에는 자료형의 형식에 구애받지 않으며 lambda 함수식도 지정할 수 있다.
✍🏻 해시의 시간복잡도
해시의 경우 시간복잡도 측면에서 매우 뛰어난 점을 보여준다. 탐색, 정렬에 걸리는 시간 비용이 크게 줄어든다. 배열의 경우 for문으로 순차 탐색을 시도하기 때문에 의 실행 시간을 가지지만 딕셔너리의 경우 특별한 경우가 아니라면 의 시간으로 원하는 요소를 찾을 수 있다.
앞서 말한 특별한 경우는 어떤 것이 있을까? 딕셔너리에 사용되는 키는 해시 함수를 기반으로 하는데 낮은 확률로 동일한 값이 나올 수 있다. 이것을 충돌이라고 하며 이 충돌을 해결하는 방법은 개별 연결과 공개 주소 방식으로 나뉜다. 파이썬에서는 공개 주소(Open Addressing) 방식을 사용한다.
개별 연결: 동일한 해시가 생성됐을 경우, 연결 리스트를 만들고 데이터를 집어넣어 한 해시에 연속적으로 연결된 형태를 취하는 방식. 만들기 쉽고 직관적이라는 장점이 있으나 연결이 많아지면 사실상 2차원 배열이 되는 단점이 있음.
공개 주소: 인근의 빈 공간을 검색하여 값을 넣는 방식, 충돌시 주어진 계산식에 따라 위치를 다시 계산하여 배정함. 이미 생성된 리스트 내에서 해결하므로 추가적인 메모리를 차지하지 않지만 '재충돌 현상'이 발생하기 쉬운 단점이 있음.
