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

안녕하세요!? 이번 게시글에서는 자료구조 중 해시에 대해서 정리하도록 하겠습니다.

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

이러한 해시는 더 나아가서 암호, 블록체인, 메시지 인증 코드 등에서도 활용됩니다.

---

해시(Hash)

---

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

 

01. 자료구조의 특징

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

 

02. 알아둘 용어

1) 해시 함수(Hash Function)

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

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

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

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

 

2) 해시 테이블(Hash Table)

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

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

표와 유사한 해시 테이블

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

 

03. 해싱(Hashing)

해싱은 해시 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위를 말합니다. 이 과정을 그림을 나타내면 아래와 같습니다.

해싱(Hashing)

 

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

1) 장점

• 데이터 저장 / 일기 속도가 빠름 ( 검색 속도가 빠름)
• 해시는 키에 대한 데이터가 있는지 확인이 쉬움

2) 단점

• 일반적으로 저장공간이 많이 필요
• 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요

3) 주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현

참고 : 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에는 value를 가짐
    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;
        }
   }

---

실행

    public static void main(String[] args) {

        Hash myHash = new Hash(20);

        myHash.saveData("Lee","30000");
        myHash.saveData("James","15000");
        myHash.saveData("Denny","5000");

        System.out.println(myHash.getData("Lee"));
        System.out.println(myHash.getData("James"));
        System.out.println(myHash.getData("Denny"));

    }

결과

30000
15000
5000

---

---

충돌(Collision)

---

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

Hash function 부분을 보면, 입력받은 키의 첫 번째 문자를 배열의 크기로 나눈 나머지를 인덱스로 사용하는데요.

만약 다른 키가 있는데 이 키의 첫 번째 문자가 동일하다면, 인덱스는 동일하게 반환될 것입니다. 그럼 배열에서 같은 장소에 저장되고, 이전에 저장된 정보는 사라질 것입니다. 이를 충돌이 발생했다고 하는데요. 또는 Collision이라고 합니다.

이렇게 충돌이 발생되는 이유에는 2가지 정도를 알 수 있습니다. 첫 번째는 함수 알고리즘의 성능이 좋지 못하여 발생하거나, 두 번째는 저장되는 데이터 양이 해시 테이블의 크기(Size) 보다 클 때입니다. 이러한 충돌을 해결하기 위해서는 어떻게 해야 할까요?

01. 충돌 해결하기

충돌을 해결하는 기법은 정말 다양하게 존재합니다. 그중 Chaining 기법과 Linear Probing 기법이 대표적으로 활용됩니다. 물론, 해시 함수를 개선해도 괜찮습니다. 그렇지만 데이터가 대량으로 있을 때는 해시 함수의 성능이 정말 좋아졌는지 확인이 어렵습니다.

1) Chaining 기법

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

Chaining 기법으로 충돌 해결하기

Chaining 기법을 구현한 코드는 아래 Github에서 참고해주세요.

https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/Hash_Chaining.java

GitHub - Si-Hyeak-KANG/java_algorithm: JAVA를 활용한 코딩 테스트 공부

 

2) Linear Probing 기법

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

Linear Probing 기법은 해시 함수를 통해서 얻은 주소(인덱스)에 이미 데이터가 있다면, 다음 주소를 체크합니다. 만약 체크했을 때 데이터가 없다면, 해당 자리에 저장이 됩니다.

Linear Probing 기법을 구현한 코드는 아래 Github에서 참고해주세요.

https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/Hash_LinearProbing.java

GitHub - Si-Hyeak-KANG/java_algorithm: JAVA를 활용한 코딩 테스트 공부

 

---

---

시간 복잡도

---

마지막으로 해시 자료구조의 시간 복잡도를 보겠습니다.

해시 자료구조는 충돌이 없는 일반적인 경우는 O(1)이 발생합니다. 키를 통해 바로 저장과 검색을 하여 값을 구하기 때문입니다.

만약 최악의 경우, 즉 모든 index에서 충돌이 발생할 경우는 O(n)이 발생합니다.