[자료구조] 자바에서의 해쉬 테이블과 충돌 문제 해결

해쉬 테이블

Hash Table : 키(Key) 에 데이터(value) 를 저장하는 데이터 구조(데이터베이스와 비슷한 구조이다.)

- key 를 통해 즉시 데이터를 받아올 수 있으므로 탐색 속도가 빠르다.

- 자바의 경우 HashMap<K, V> 클래스를 통해 객체를 생성할 수 있다.

 

용어

해쉬(Hash) : 임의 값을 고정 길이로 변환하는것

해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

해싱 함수(Hashing Function) : key 에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) : key 를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 key 에 대한 데이터 위치를 일관성 있게 찾을 수 있다.

슬롯(slot) : 한 개의 데이터를 저장할 수 있는 공간 

 

장,단점

장점:

- 데이터 저장/읽기 속도가 바르다.(검색 속도가 빠르다.)

- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.

단점:

- 일반적으로 저장공간이 좀 더 많이 필요하다.

- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조(연결 리스트와 같은)가 필요하다.

 

충돌(Collision) 해결 알고리즘 (서로 다른 키들에서 추출한 해쉬 주소가 동일한 경우)

- Chaining 기법

개방 해싱 또는 Open Hashing 기법 중 하나이다.

해쉬 테이블 외의 저장공간을 활용하는 기법으로서, 충돌이 일어나면 연결 리스트 같은 자료 구조를 이용하여 충돌이 일어난 주소의 데이터 값 뒤에 추가로 연결시켜서 저장해주는 기법이다.

 

* 이를 활용하여 문제를 해결하는 좋은 예시

- 백준 1302번 베스트 셀러 문제

https://www.acmicpc.net/problem/1302 

1302번: 베스트셀러

위의 문제를 풀이해본 결과 다음과 같은 코드로 해결할 수 있었다.

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		HashMap<String, LinkedList<Integer>> hashmap = new HashMap<String, LinkedList<Integer>>();
		
		int count = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < count; i++) {
			LinkedList<Integer> list = new LinkedList<Integer>();
			String str = br.readLine();
			if(hashmap.containsKey(str)) {
				list = hashmap.get(str);
				list.add(0);
				hashmap.replace(str, list);
			}
			else {
				list.add(0);
				hashmap.put(str, list);
			}
		}
		
		Object maxbook = "";
		int max = 0;
		Object[] keyArray = hashmap.keySet().toArray();
		List<String> overlapBook = new ArrayList<String>();
		for(int i = 0 ; i < hashmap.size(); i++) {
			LinkedList<Integer> list = new LinkedList<Integer>();
			list = hashmap.get(keyArray[i]);
			int listSize = list.size();
			if(listSize > max) {
				max = listSize;
				maxbook = keyArray[i];
				overlapBook.clear();
				overlapBook.add((String) maxbook);
			}
			else if(listSize == max) {
				maxbook = keyArray[i];
				overlapBook.add((String) maxbook);
			}
		}
		if(overlapBook.size() > 1)
			Collections.sort(overlapBook);
		bw.write(overlapBook.get(0) + "\n");
		bw.flush();
		bw.close();
	}
}

- HashMap 객체의 value 필드를 연결리스트 타입으로 선언해주었다.

- 이를통해 키값의 중복으로 같은 공간에 저장되는 데이터들을 연결리스트로 연결해서 묶어주었다.

- 해쉬 맵 내부에 저장된 연결리스트들 중에서 이전 연결리스트의 크기보다 더 큰 것이 발견되면 해당 연결리스트의 키 값(책 제목)을 최대 갯수 중복 검증용 리스트(overlapBook) 에 추가해주었다.

- 만약 최종적으로 overlapBook 리스트의 길이가 2이상이면, 최대값으로 팔려나간 책이 2개 이상 존재한다는 것이므로 Collections.sort() 메소드를 활용하여 책 제목을 사전순으로 정렬해준 다음 출력하는 것으로 문제를 해결했다.

 

 

- Linear Probing 기법

폐쇄 해싱 또는 Close Hasing 기법 중 하나이다.

해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법으로, 충돌이 일어나면 해당 해쉬 주소의 바로 다음 주소부터 맨 처음 나오는 빈 공간에 저장하는 기법이다.

- 저장공간의 활용도를 높이기 위한 기법