해시 테이블

이동근·2021년 5월 16일
0

자료구조

목록 보기
4/9

해시함수(hash)

해시 테이블을 알기전 우선 적으로 해시함수를 알아보자, 해시 함수는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 것을 의미 한다. 그리고 이러한 매핑해주는 과정을 보고 해싱이라고 한다.

해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 한개 이다. 해싱은 최적의 검색이 필요한 분야에 사용이 된다.

우리 주변에서 해싱을 하는 대표적인 경우는 bycrpt를 생각하면 쉽다

bycrpt

웹페이지 클론코딩 당시에 비밀번호를 저장하기 위해 사용한 라이브러리 이다. 비밀번호 그 자체를 데이터베이스를 저장할 수는 없으니, 인코딩을 통해 바이트 타입으로 바꿔서 저장을 해준다.

바이트 타입으로 저장이 된 비밀번호는 그 자체만으로는 알지 못한다. 하지만 매핑이 되는 데이터는 고유하기 때문에 이 바이트 타입을 가지고 해킹이 가능하다.

이런식으로 bycrpt가 대표적인 해싱의 예이다.

그럼 해시 테이블은 무엇 일까?

해시 테이블(hash table)

해시테이블은 key-value로 구성이 된 추상 자료형 이다.

추상 자료형
구현과 기능을 따져봤을때 기능에 주요한 중점 둔 자료형 이다. python에서 dict 를 사용할 때 key-value로 데이터가 들어가서 사용할 수 있다는 기능만 알고있지 어떻게 구현했는지에 대해서는 생각 할 필요가 없기 때문이다.
(자세한 내용은 추후에)

메모리 어딘가에 저장 된 데이터를 index값을 매겨 배열에 저장을 해놓은 것을 의미한다.

위의 그림 처럼 key와 관련된 데이터를 01,02,14와 같은 index 값을 매겨 배열에 저장하는 모습을 볼 수 있다.

충돌

해시 테이블에서 중요하게 생각할 내용이 충돌이다.
해시함수는 해시테이블의 키 값으로 레코드가 저장되어 있는 주소(혹은 색인)를 산출하는 함수이다. 순차검색에 비해, 해시테이블을 이용한 검색은 속도 측면에서 획기적이라고 할 수 있다.

하지만 임의의 값 두 개가 같은 index를 가진다면? 두 데이터 간의 충돌이 일어나는 상황이 만들어 지게 되고 해시테이블의 효율성이 떨어지게 된다.

그래서 해시테이블에서는 이러한 충돌을 처리 해줘야 한다.

그럼 왜 충돌이 일어나는 것일까?
비둘기 집의 원리란 것이 있다. 9개의 비둘기 집의 공간이 있을 경우, 10개의 아이템이 들어온다면 반드시 1번 이상의 충돌은 발생한다.

이런 기준으로 보면 최소한은 1번이 나겠지만 10개가 모두 같은 인덱스에 들어가게 되면 9번의 충돌이 일어나게 된다. 충돌이 일어나면 추가 연산을 필요로 하기 때문에 가급적 충돌은 최소화 하는 것이 좋다.

대표적으로 두 개의 방법이 있다.

1. chaining(체인)
2. open addressing(개방 주소법)

충돌을 처리하는데 있어 이 두 개가 대표적인 방법이다.

Chaining - 체이닝

말 그대로 체인 처럼 엮는 것을 의미한다.

똑같은 index를 가진 데이터들을 링크드 리스트를 사용해서 chain처럼 엮어놔 준다.

위의 그림에서 볼 수 있듯이 0번 인덱스에 있는 데이터들을 0번 노드, 1번 노드, 2번 노드 이런식으로 엮어 놓는다.

간단한 원리를 요약하면 다음과 같다.

  • 키의 해시값을 계산한다.
  • 해시 값을 이용해 배열의 인덱스를 구한다.
  • 같은 인덱스가 있다면 연결 리스트로 연결한다.

Open addressing(오픈 주소법)


충돌 발생 시 탐사를 통해 빈 공간을 찾아 나서는 방식이다.
충돌이 일어나게 되면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결하며 이 때문에 체이닝 방식과 다르게 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장 된다는 보장은 없다.

충돌이 발생하게 되면 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 특정 위치가 선점되어 있으면, 바로 그 다음 위치를 확인하는 식이다.

오픈 주소법의 특징은
해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점이다. 연속된 데이터 그룹이 생기는 이러한 현상을 클러스터링 이라고 하는데, 이렇게 되면 인근 클러스터들과 서로 합쳐지는 일이 발생하게 되면서 데이터가 몰리는 현상이 발생하게 된다.

언어별 해시 구현 방식

해시 테이블로 구현된 파있너의 자료형을 제시하라! 라는 질문을 받게 되면
주저없이 딕셔너리라고 답할 수 있어야 한다.

파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까?
-> 오픈 어드레싱 방식으로 구현 되어져 있다.

이유는?
연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고 추가 메모리 할당은 상대적으로 느린 작업 이기 때문에 선택하지 않았다

profile
하루하루 1cm 자라는 개발자

0개의 댓글