Hash Tables이란?

#NomadCoders #자료구조

 

1. HashTable이란?

key value system으로 javascript에서는 object로 python에서는 dictionary, Go에서는 map 등등.. 이 있다.

array와 비교해보자. 예를 들어 카페 메뉴가 다음과 같이 배열로 되어있다고 가정하자.

menu = [{bread, 2000}, {coffee, 1500}, ... ];

 

여기서 coffee의 가격을 알고 싶으면 선형검색을 하면 되나 메뉴가 많을수록 오래걸린다.

이때 hash tables로 정리하면 다음과 같다.

menu = {"bread" : 2000, "coffee" : 1500, ... }; 	// key(메뉴) : value(가격)

 

Hash tables의 시간복잡도는 상수시간인 Q(1)이기 때문에 배열로 된 자료구조보다 찾는 속도가 더 빠르다.

다음은 배열 대신 Hash table을 응용하여 value만 저장해 자료구조 안에 값이 있는지 확인하는 방법이다.

보통 리스트 안에 값이 있는지 찾으면 선형검색을 하지만 다음과 같이 상수시간으로 바로 찾을 수 있다.

// 버스가 car에 있는지 확인하는 방법
// key 차종류 : value true 를 넣어 array처럼 응용

car = {
	"🚗" : true,
    "🚓" : true,
    "🚕" : true,
    "🛺" : true,
    "🚙" : true,
    "🚌" : true,
}


car["🚌"]; //true

 

 

2. Hash Tables 동작 원리

Hash Tables에는 array구조가 있다. item에 접근 방법은 인덱스 번호를 부여한다.

그럼 해쉬테이블은 어떻게 더 빠를까?

내부에 배열같은 모양으로 테이블이 있다. 바로 Hash Function이다.

노마드 코더 : https://www.youtube.com/watch?v=HraOg7W3VAM&ab_channel=%EB%85%B8%EB%A7%88%EB%93%9C%EC%BD%94%EB%8D%94NomadCoders

Hash Function은 저장할 키 값을 index로 바꿔버린다. Key를 가져다가 해시함수에 넣고 해시함수가 준 숫자에 value 저장한다.

예를 들어 bus이면 index 3을 부여하고 value에 넣는다. 그럼 index 3의 value에는 bus(key)의 value 값을 저장되는 것이다.

만약에 car를 저장하려면 어떻게 할까. car도 마찬가지로 index 3에 저장해야하는데 이를 해쉬 충돌이라고 하는데 해결방법은 다음과 같다.

같은 index에 들어가야할때에는 value에 array를 만들어 두개를 저장한다.

여기서 알 수 있는 건 Hash tables의 시간복잡도가 언제나 상수시간(Q(1))은 아니며 충돌이 일어나면 선형검색을 한다는 것이다.

 

 

마치며

이상 Hash Tables을 배워보았으며 Search를 할때에는 array보다 빠른 자료구조를 알게 되었다. 검색 알고리즘이 필요할때에는 고려해볼만한 자료구조이다.

 

Nomadcoder를 처음보고 코딩을 시작했는데 지금도 꾸준히 배우고 있습니다.

항상 감사합니다!

 

출처 : https://www.youtube.com/watch?v=HraOg7W3VAM&ab_channel=%EB%85%B8%EB%A7%88%EB%93%9C%EC%BD%94%EB%8D%94NomadCoders