[자료구조] 해시(Hash) 알아보기

bien·2024년 5월 21일

자료구조

목록 보기

1/1

해시는 저장 또는 검색 등에서 자주 활용되는 자료구조이다.
정확하게는 특정한 함수(알고리즘)를 통해서 값을 추출하고 활용한다.
함수(알고리즘)이 어떻게 구현되느냐에 따라 사용 용도와 성능이 달라진다.

해시(Hash)

해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말한다.
- 다른 말로 '해시 값(Hash Value), 해시 코드, 체크섬' 이라고도 한다.
- 이러한 해시는 뒤에서 알아볼 '해시 함수'에 의해 얻게 된다.
- 간단히 말하자면, 데이터의 Key 값이 해시 함수를 통해서 변환된 간단한 정수이다.
- 이렇게 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용된다.

01. 자료구조의 특징

키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조
해시 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산
키를 통해서 저장된 데이터를 빠르게 찾고, 저장 및 탐색 속도가 획기적으로 빨라짐

02. 알아둘 용어

1) 해시 함수(Hash Function)

임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

해시함수(Hash Function)는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 말한다. 이렇게 출력된 해시 값은 알고리즘에 따라 다양한 결과를 보인다. 그렇기 때문에 함수는 목적에 맞게 다양하게 설계되고 자료구조, 캐시, 검색, 에러 검출, 암호 등으로 유용하게 사용된다.

// 해시 함수 활용 예시
Integer hashFunction(String key) {
	return (int)(key.chaAt(0)) % 100;
}

위 코드는 입력받은 키에서 문자의 0번에 해당하는 부분을 정수화하여 100으로 나눈 뒤, 나오는 나머지를 반환하는 함수(메서드)이다. 이렇게 반환된 값은 배열의 인덱스가 되고, 해당 인덱스에 맞게 저장할 수 있게 되는 것이다. 이처럼 함수의 로직은 단순할수도, 복잡할 수도 있다.

02) 해시 테이블(Hash Table)

키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

해시 테이블(Hash Table)은 키와 값을 함께 저장해 둔 데이터 구조이다. 이는 데이터가 행과 열로 구성된 표에 저장하는 것과 유사하다. 테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성된다. 따라서 중간에 여유 공간이 발생할 수 있다.

추가용어
- 버킷(bucket): 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
- 슬롯(slot): 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러개의 슬롯이 있음

03) 해싱 (Hasing)

해싱은 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위를 말한다.

04) 해시 자료구조의 장, 단점과 용도

장점
- 데이터 저장 / 읽기 속도가 빠름 (검색 속도가 빠름)
- 해시는 키에 대한 데이터가 있는지 확인이 쉬움
단점
- 일반적으로 저장공간이 많이 필요
- 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요
주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현

참고: JAVA에서는 주로 HashMap 클래스를 사용한다.
=> 해시 테이블 구조를 활용하여 구현된 JAVA Collection Framework에 속한 클래스

05. 해시 구현하기

// 기본적인 해시 테이블 구현
public class Hash {

	// Hash table
	public Slot[] hashTable;  // 배열 형태로 선언
    
    // Hash 객체를 생성할 때 table 사이즈 지정
    public Hash(Integer size) {
    	this.hashTable = new Slot[size];
    }
    
    // Slot에는 vale를 가짐
    public class Slot {
    	String value;
        
        Slot(String value) {
        	this.value = value;
        }
    }
    
    // Hash function
    public int hashFunction(String key) {
    	return (int)(key.charAt(0) % this.hashTable.length; // 나머지
    }
    
    // 입력받은 key를 해시 함수로 인덱스화 하고, 해당 인덱스에 value 저장
    public boolean saveData(String key, String value) {
    
    	// key는 해시 함수를 거쳐서 해시 값(해시, 해시 주소)을 반환 -> 여기선 배열의 index와 동일
        Integer address = this.hashFunction(key);
        
        if(this.hashTable[address] != null) { // 해당 주소에 이미 데이터가 있는 경우
        	this.hashTable[address].value = value;
        } else {
        	this.hashTable[address] = new Slot(value);
        }
        
        return true;
    }
    
    // key에 해당하는 값을 반환
    public String getData(String key) {
    	
        // key는 해시 함수를 거쳐서 해시 값(해시, 해시 주소)을 반환
        Integer address = this.hashFunction(key);
        
        if(this.hashTable[address] != null) {
        	return this.hashTable[address].value;
        } else {
        	return null;
        }

	}

충돌 (Collision)

위에 작성된 코드는 해시의 기본 원리를 이해하기 위해 작성된 방법이다.

Hash functioin에서 입력받은 키의 첫번째 문자를 배열의 크기로 나눈 나머지를 인덱스로 사용하는데, 만약 다른 키가 있는데 이 키의 첫번 째 문자가 동일하다면 동일한 인덱스를 반환할 것이다.

그럼 배열에서 같은 장소에 저장되고, 이전에 저장된 정보는 사라지게 된다. 이같은 상황을 충돌이 발생했다고 하고, Collision이라고 한다.

이처럼 충돌이 발생하는 이유에는 2가지 정도가 있다.

함수 알고리즘의 성능이 좋지 못한 경우
저장되는 데이터의 양이 해시 테이블의 크기(Size)보다 큰 경우

01. 충돌 해결하기

Chaining 기법

개방해싱 또는 Open Hashing 기법 중 하나: 해시 테이블 저장공간 외의 공간을 활용하는 기법
충돌이 발생했을 때, 연결 리스트(Linked List) 자료구조를 활용해 해결하는 방법

Linear Probing 기법

폐쇄해싱 또는 Close Hashing 기법 중 하나: 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
충돌이 발생했을 때, 해당 해시 주소(index)의 다음 주소(index)부터 맨 처음까지 순회해가며 빈 공간을 찾는 방식
저장공간 활용도를 높이기 위한 기법

시간 복잡도

충돌이 없는 해시의 시간 복잡도: 일반적으로 O(1)
- 키를 통해 바로 저장과 검색을 하여 값을 구하기 때문
최악의 경우, 모든 index에서 충돌이 발생할 경우: O(N)

Reference

bien

Good Luck!