[컴퓨팅 사고력]해시(Hash)테이블 이해하기

길동이는 주차장에서 일을 하고 있습니다. 주차장은 5개 구역으로 나누어져 있고 1개 구역에는 10대씩을 세워 둘 수 있습니다. 길동이가 하는 일은 손님이 오면 손님의 차를 대신 주차 구역에 주차를 시켜 주고 찾으러 오면 차를 찾아서 전달해 주는 역할을 합니다. 하지만 차가 많아지면서 차를 어디에 두었는지 찾기가 힘들어 졌는데요~ 꾀 많은 길동이는 다음과 같은 아이디어를 생각해 냈습니다. 차의 뒷번호를 확인해서 뒷번호가 1,6 이면 1번 구역에 2,7이면 2번 구역에 3,8 이면 3번 구역에 4,9이면 4번 구역에 5,0 이면 5번 구역에 주차를 해 놓은 후에 손님이 찾는 번호만 확인하여 그 위치를 찾아 주었습니다. 그런데 하루는 50대를 주차 할 수 있는 주차장에 5대 밖에 주차를 하지 않았는데 1번구역이 모두 꽉 차 있는데 하필이면 또 끝자리가 6번이라서 1번 구역에 주차를 해야 됩니다. 그렇다면 이러한 문제는 어떻게 해결을 해야 할까요?

위의 문제에서 길동이가 차의 뒷번호를 이용해서 주차구역을 할당하는 것이 해시테이블의 기본이 되는 아이디어 입니다.

5로 나눈 나머지의 값이 키값이 되고 각 차량은 해당구역에 주차 되는데~

이렇게 키값으로 해당구역을 단 한번에 찾을수 있는것이 해시테이블입니다.

 

 

 

해시테이블이란?

 

이미지 출처 : 위키백과

해시 테이블 이란 컴퓨팅에서 키를 매핑할수 있는 구조인 연관배열을 사용하는 자료구조를 의미합니다.

해시 테이블은 해시 함수를 사용하여 색인(index)를 버킷(bucket)이나 슬롯(sloat)의 배열로 계산을 합니다.

데이터베이스 관리 시스템에서도 키값이나 인덱스 관리시에 해싱을 이용해서 데이터를 관리하게 되는데 해시테이블을 사용하게 되면 저장과 검색을 빠르게 처리 할 수 있습니다.

 

해시 테이블의 예를 들어 보겠습니다.

배열이 5개가 있는데 데이터가 9,20,31,53,77 의 값이 입력이 들어 왔습니다.

이 데이터를 5로 나눈 나머지 위치 즉 9(4번지),20(0번지),31(1번지),53(3번지),77(2번지) 에 저장을 하면 다음과 같이 저장이 됩니다.

0번지	1번지	2번지	3번지	4번지
20	31	77	53	9

이렇게 저장후 테이블에 해당 값이 있는지 없는지를 찾기 위해서 5로 나눈 나머지의 위치값을 조회 하면 9%5=4 가 되므로 4번지의 위치에서 9를 찾을 수 있습니다.

이것이 가장 기본적인 해시 테이블을 이용한 알고리즘입니다.

하지만 맨 위에서 길동이가 주차 하면서 5대만 주차하면서 5대가 모두 한구역에 주차 되면서 다음 차량이 주차 하면서 주차 할 곳이 없어지는 문제가 발생할수 있습니다.

 

이러한 문제는 해시 테이블을 설계하는데 발생 할수 있는 문제인데요~

이렇게 같은 공간안에 키값이 충돌하는 것을 Hash Collision(해시 충돌) 이라고 합니다.

Hash의 장점은 한개의 Key에 한개의 Data만 존재하는 경우 O(1) 이지만 이렇게 충돌이 나는 경우를 처리해 주어야 한다는 단점이 있습니다.

해싱충돌을 해결하는 방법은 여러가지가 있는데 이러한 문제들을 해결하기 위해 해시함수는 해시테이블에 편중되지 않고 골고루 분포되도록 하는것이 바람직합니다.

 

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

인천 서구 검단신도시 원당컴퓨터학원