해시 테이블(Hash Table)과 해시 충돌(Hash Collision) 쉬운 개념 정리

Array VS Hash Table

Pizza	50$
Coke	15$
Tea	3$
Burger	20$

 

Java에서 위 메뉴를 배열로 저장하고 Coke의 가격을 찾으려면 아래와 같이 O(N)의 순회를 하며 찾아야 한다.

String[][] menu = {
    {"Pizza", "50"},
    {"Coke", "15"},
    {"Tea", "3"},
    {"Burger", "20"}
};

// 출력 예시
for (String[] item : menu) {
	if(item[0].equals("Tea")) {
    	System.out.println(item[0] + " : " + item[1] + "$");
    }
}

 

이를 좀 더 빠르게 찾을 수 없을까?
이럴 때 Hash Table을 사용하면 된다. 이 경우 O(1)으로 순회하지 않고 key 값을 통해 찾을 수 있다.

또한 추가할 때와 삭제할 때도 O(1) 이다.

HashMap<String, Integer> menu = new HashMap<>();

// 데이터 저장
menu.put("Pizza", 50);
menu.put("Coke", 15);
menu.put("Tea", 3);
menu.put("Burger", 20);

int teaPrice = menu.get("Tea"); // Tea가 있는지 찾아 Tea의 가격을 넣는다.

 

음식점에 있는 메뉴가 1억개가 있다고 했을 때,

그 1억개 중 "Tea" 메뉴의 가격을 찾으려면 배열의 경우 최악의 경우 1억개를 뒤져봐야 하지만

Hash Table의 경우 1번만 연산을 하면 된다.

 

Hash Table 원리

출처 : 노마드코더

Hash Table에는 사실 내부에 array 구조가 있다.

그리고 Hash Table에서 값을 가져오기 위해서는 index 값을 알아야 한다.

 

출처 : 노마드코더

 

그럼에도 Hash Table이 Array보다 더 빠른 이유는 Hash Function이 있기 때문이다.

그래서 저장하고 싶은 키를 Hash Function이 숫자로 바꿔버리고 그 숫자가 index가 된다. 그리고 그 index에 값을 저장한 것이 value 값이 된다.

 

예를 들어 key 값이 "tea" 이고 value 값이 "5$" 이라면, Hash Table에는 아래와 같은 절차로 저장된다.

• 1) key 값이 "tea"인 것에 Hash Function을 돌려 3이 나왔다. (여기에서는 Hash Function이 key의 글자수로 지정된다고 가정한다.)
• 2) 3 인덱스에 값인 "5$"를 저장한다.

그러면 key 값이 "tea"인 value 값을 알아내려면 어떻게 할까?

• 1) key 값이 "tea"를 Hash Function으로 돌리면 3이 나온다. (여기에서는 Hash Function이 key의 글자수로 지정된다고 가정한다.)
• 2) 3 인덱스의 value 값을 확인해본다.

해시 충돌(Hash Collision)

만약에 key 값이 "pie"인 것을 넣는다고 생각해보자. Hash Function을 돌리면 3이 나올 것이다.

그러면 기존의 key 값이 "tea"가 들어가 있는 곳과 겹치게 될 것이다.

 

이런 경우를 해시 충돌이라고 한다.

 

해결하는 방법은 여러 가지가 있는데, 그 중에 하나를 보자.

index가 3인 곳에 key가 "tea"인 값과 key가 "pie"인 값을 모두 넣는 방법이 있다.

 

만약 key가 "Pie" 인 value 값을 찾아야 한다고 하면, 아래와 같은 프로세스로 찾을 수 있다.

• 1) key 값을 Hash Function으로 돌리면 3 이 나온다.
• 2) 3 인덱스의 value 값을 확인한다. (3 인덱스에서 선형으로 확인해서 key가 "Pie"인 것을 찾는다.)
• 3) value 값을 확인한다.

그래서 Hash Table 자료구조를 이용하여 데이터를 조회하는 것이 무조건 O(1)은 아니고 O(N)이 될 수도 있다. 하지만, 이러한 경우는 특수한 경우이고 일반적인 경우에서 O(1)으로 사용되는 경우가 많다.

 

예제

Hash Table의 필요성을 몸소 느낄 수 있는 예제이다.

[JAVA] 🌟프로그래머스 - 달리기 경주

 

참고자료

기초 : https://www.youtube.com/watch?v=HraOg7W3VAM&t=1s

 

심화 : https://www.youtube.com/watch?v=S7vni1hdsZE