[자료구조] Hash

해시(Hash)란?

데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조

• 해시를 사용하면 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있음
• 빠르게 데이터에 접근할 수 있어 데이터베이스 등에 활용
• 특정한 값을 찾고자 할 때 키(Key)로 접근할 수 있음
• 일반적으로 해시 함수는 모듈로 연산 등의 수학적연산으로 이루어져 있어 O(1)만에 값에 접근할 수 있음

이미지 출처 : Wikipedia

• 해싱 알고리즘은 나눗셈법이 가장 많이 활용됨
• 입력값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식 테이블 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높음

 

해시의 충돌

• 해시 함수의 입력값으로는 어떤 값이나 들어갈 수 있지만, 해시 함수를 거쳐 생성되는 키의 경우의 수는 한정적이라 키 중복이 발생할 수 있음
• 해시 테이블에서 키가 중복되는 경우 충돌(Collision)이 발생했다고 표현함

 

충돌을 처리하는 방법

1. 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장: 선형 조사법, 이차 조사법 등
2. 해시 테이블의 하나의 버킷에 여러 개의 항목을 저장 : 체이닝 등

 

 

선형 조사법

• 중복되는 키값의 다음이 비어있다면 다음 위치에 넣어줌
• 충돌이 발생하기 시작하면 유사한 값을 가지는 데이터끼리 서로 밀집되는 "집중 결함" 문제가 발생하는 단점 존재
• 선형조사법도 해시테이블의 크기가 비약적으로 크다면(= 메모리를 많이 소모한다면) 충돌이 적게 발생하므로 매우 빠른 데이터 접근 속도를 가질 수 있음
• 일반적으론 한정적이라 충돌이 최대한 적게 발생하도록 해야함

 

이차 조사법

• 선형 조사법을 약간 변형한 형태. 키값을 선택할 때 완전 제곱수를 더해가는 방식
• 한번 중복되면 1제곱만큼, 두번 중복되면 2의 제곱만큼 뒤의 빈자리에 삽입함

 

※ 크기 재설정 : 위 두 조사법에서 테이블이 가득차게 되면 테이블의 크기를 확장하여 계속해서 해시테이블을 유지할 수 있도록함

 

 

체이닝

• 연결리스트를 활용해 특정한 키를 가지는 항목들을 연결하여 저장
• 연결리스트라 삽입과 삭제 용이
• 동적할당을 통해 테이블 크기 재설정 문제 쉽게 해결. 다만, 동적할당을 위한 추가적인 메모리 공간이 소모됨

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수