해쉬 테이블 Hash Table

Intro::

브루트포스 알고리즘으로 시간초과가 나는 문제의 경우 해쉬 테이블을 사용해야 한다. 이를 알아보자.

기본 개념

문자열에 대한 해쉬값을 직접 구해 배열로 그 개수와 존재여부를 체크하는 방식이다. 이렇게 접근하게 되면 같은 키값인 경우 배열로 임의 접근이 가능하기 때문에 탐색 시간을 줄여준다.

코드

package algorithm;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class HashTable {
	static final int HASH_SIZE = 1000;
	static final int HASH_LEN = 400;
	static final int HASH_VAL = 17; // 소수로 할 것

	static int[][] data = new int[HASH_SIZE][HASH_LEN];
	static int[] length = new int[HASH_SIZE];
	static String[][] s_data = new String[HASH_SIZE][HASH_LEN];
	static String str;
	static int n;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());

		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);
	}

	public static int getHashKey(String str) {

		int key = 0;
		for (int i = 0; i < str.length(); i++) {
			key = (key * HASH_VAL) + str.charAt(i) + HASH_VAL;
		}
		if (key < 0) {
			key = -key;
		}
		return key % HASH_SIZE;

	}
	public static int checking(int key) {
		int len = length[key]; // 현재 key에 담긴 수 (같은 key 값으로 들어오는 문자열이 있을 수 있다)
		if (len != 0) { // 이미 들어온 적 있음
			for (int i = 0; i < len; i++) { // 이미 들어온 문자열이 해당 key 배열에 있는지 확인
				if (str.equals(s_data[key][i])) {
					return ++data[key][i];
				}
			}
		}

		// 들어온 적이 없었으면 해당 key배열에서 문자열을 저장하고 길이 1 늘리기
		s_data[key][length[key]++] = str;
		return -1; // 처음으로 들어가는 경우 -1 리턴
	}
}

References::