해시 테이블 (Hash Table)

1. 개념 설명

(1) 해시 테이블은 키(key)를 값(value)에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다.

 

 

 

 

2. 과정

by wiki

- 실제로 수행되는 과정이며, key값을 가지고 해당하는 index위치에 가서 buckets에 있는 value에 매핑하고 있다.

 

- 아래는 실제 3. 코드에서 진행되는 과정 중 하나이며, 이것을 이해하면 코드를 쉽게 이해할 수 있을 것이다.

1. apple이 들어옴.
getHashkey(apple)의 결과 2가 나옴.
length[2]는 0이므로 처음 들어온 값임.s_data[2][0]에 apple을 저장함.
length[2]를 ++함.
 
2. abc가 들어옴.
getHashKey(abc)의 결과 2가 나옴.
length[2]는 1이므로 이미 들어온 값임.
length[2]만큼 반복하면서 s_data에 abc라는 데이터가 있는지 확인함.
s_data[2][0]은 apple이므로 일치하는 값이 없음.s_data[2][1]에 apple을 저장함.
length[2]를 ++함.
 
3. abc가 들어옴.
getHashKey(abc)의 결과 2가 나옴.
length[2]는 2이므로 이미 들어온 값임.
length[2]만큼 반복하면서 s_data에 abc라는 데이터가 있는지 확인함.
s_data[2][1]은 abc이므로 일치함.
data[2][1] 값을 1 증가 후. 1을 리턴함.
 
[출력값]
OK
OK
abc1

 

 

 

 

3. 코드

: 이 코드는 아래 링크에 있는 해시 테이블의 문제이다.

Problem - C - Codeforces

 

조건은 아래와 같다.

1. 처음 생성되는 문자열 key 값에는 "OK", 이미 존재하는 문자열 key 값에는 "문자열+index"로 출력한다.
 
2. Input과 Output의 예시는 아래와 같다.
 
[Input]
5
abcd
abc
abcd
abcd
ab
 
[Output]
OK
OK
abcd1
abcd2oK

public class HashTable {
    static final int HASH_SIZE = 1000;
    static final int HASH_LEN = 500;
    static final int HASH_VAL = 19;  //최대한 해시 충돌 방지를 위해 소수(ex) 17, 19 등)으로 잡는다.
    
    static int[][] data = new int[HASH_SIZE][HASH_LEN];  //입력값을 저장하는 변수
    static int[] length = new int[HASH_SIZE];  // 현재 key에 담긴 수를 저장하는 변수
    static String[][] s_data = new String[HASH_SIZE][HASH_LEN];  //입력 값으로 받은 문자열을 저장하는 변수
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
   static int N; // 총 입력받는 개수
    static String str; // 라인 입력받는 변수
    
    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(br.readLine()); // 입력 수 (1~100000)
        
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            
            int key = getHashKey(str);
            int cnt = checking(key);
            
            if(cnt != -1) { // 이미 들어왔던 문자열
                sb.append(str).append(cnt).append("\n");
            }else {
                sb.append("OK").append("\n");
            }
        }
        
        System.out.println(sb.toString());
    }
    
    static int getHashKey(String str) {
        int key=0;
        
        for(int i=0; i<str.length(); i++) {
            key = (key*HASH_VAL) + str.charAt(i);
        }
        
        // key값은 배열 인덱스를 활용하기 때문에 
        // 만약 음수라면 -> 양수로 바꿔준다.
        if(key<0) key = -key;
        
        return key%HASH_SIZE;
    }
    
    static int checking(int key) {
        int len = length[key]; 
        
        if(len != 0) { // 이미 들어온 적 있음
            for (int i = 0; i < len; i++) { // 이미 들어온 문자열이 해당 key 배열에 있는지 확인
                if(str.equals(s_data[key][i])) {
                    data[key][i]++;
                    return data[key][i];
                }
            }
        }
        // 들어온 적이 없었으면 해당 key배열에서 문자열을 저장하고 길이 1 늘리기
        s_data[key][length[key]++] = str;
 
        return -1;
    }
}

 

 

 

 

4. 시간 복잡도

(1) 최선과 평균의 시간복잡도는 O(1)이며, 최악은 O(N)이다.

 

 

 

 

5. 장점

(1) 완전탐색(Brute Force)에 빠지는 알고리즘 문제들을 해시로 적용하여 최대한 모든 데이터를 탐색할

필요없이 값(value)를 구할 수 있다.

 

(2) 해시 충돌이 없는 상태에서의 배열 또는 리스트, 트리와 같은 선형적인 구조보다 더 빠른 탐색이 가능하다.

 

 

 

 

6. 단점

(1) 아무리 많은 키(key)값을 만들더라도 같은 키 값을 가지는 서로 다른 값(value)이 존재할 수 있다.

( 이것을 우리는 해시 충돌이라고 부른다. )

 

(2) 만약 해시 충돌이 발생한다면, 시간 복잡도는 O(N)에 점점 수렴하게 된다.

 

(3) 정렬이나 순차적인 메모리 저장이 필요한 경우 적합하지 않다.

 

 

 

 

7. 해시 출동을 해결하는 기법 2가지

(1) 분리 연결법 (Separate Chaining)

: 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 방법이다.

 

 

 

 

(2) 개방 주소법 (Open Addressing)

: 추가적인 메모리를 사용하는 분리 연결법 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다.

 

( 아래와 같이 세 가지 방법이 존재한다. 여기서는 자세하게 다루지 않으므로, 한번 인터넷에 찾아보면 좋을 것 같다. )

1. Linear Probing

2. Quadratic Probing

3. Double Hasing Probing

 

 

 

 

8. 참고한 사이트

해시 테이블(Hash Table) | 👨🏻‍💻 Tech Interview (gyoogle.dev)

[자료구조] 해시테이블(HashTable)이란? - MangKyu's Diary (tistory.com)