Direct Access Table과 Hash Table

---

 

다음과 같은 key-value쌍의 데이터를 저장하려고 한다 

 

 

key-value쌍을 저장하는 기본적인 두 가지 방법에 대해 알아보자

 

---

 

Direct Access Table

 

배열의 인덱스로 바로 접근하는 방법이다

 

배열에서 인덱스를 순서가 아니라 key라고 생각하고 key-value쌍을 저장하는 방식이다

 

 

key를 바탕으로 배열의 인덱스에 데이터를 저장한다

 

'57'키는 배열의 57번 인덱스에 저장하고

 

'208'키는 배열의 208번 인덱스에 저장하고

 

'900'키는 배열의 900번 인덱스에 저장하면 된다

 

각 key에 해당하는 value를 알고 싶으면 해당 인덱스에 접근하면 된다

 

가장 큰 장점은 배열의 인덱스에 O(1)으로 바로 접근할 수 있다는 것이다

 

반면에 단점은 공간을 많이 낭비한다는 것이다

 

위의 예시를 보면 사용하는 인덱스는 3개 인데

 

나머지 898개의 인덱스를 낭비하게 된다

 

---

 

Hash Table

 

공간을 많이 낭비하는 Direct Access Table을 효율적으로 사용하는 방법이다

 

Hash Table은 해시 함수와 배열을 같이 사용하는 자료 구조이다

 

해시 함수

 

해시 함수는 특정 값을 원하는 범위의 자연수로 바꿔주는 함수이다

 

해시 함수에 아무 숫자를 넣었을 때 원하는 범위의 자연수가 나와야 한다

 

대표적인 해시 함수로는 나누기가 있다

 

key를 배열의 크기로 나눈 나머지를 사용하는 방법이다

 

 

만약 배열의 크기가 100이고

 

key의 값들이 57, 208, 900이라고 하자

 

 

그럼 그냥 key를 100으로 나누어서 남는 나머지를 리턴하면 된다

 

57, 208, 900을 해시 함수에 넣으면 각각 57, 8, 0이 리턴되는 것이다

 

 

어떤 키가 들어와도 0부터 원하는 정수의 범위의 자연수로 바꿔줄 수 있는 것이다

 

간단하게 나눈 나머지를 이용한 해시 함수를 살펴보았다

 

이외에도 다양한 해시 함수가 존재한다

 

---

 

Hash Table 계속

 

크기가 100인 배열에 다음과 같이 key-value 쌍을 저장할 수 있다

 

208번: 강아지를 예를 들어 보자

 

우선 key에 해당하는 208을 해시 함수에 넣고 8이 리턴되었다고 하면

 

배열의 8번 인덱스에 key와 value를 모두 저장한다

 

 

마찬가지로 다른 key-value쌍도 해시함수를 이용하여 key와 value값을 모두 저장해주면 된다

 

---

 

저장한 데이터를 가지고 올 때

 

만약 key가 208인 value를 알고 싶으면

 

208을 해시함수에 넣고 리턴된 값 8을 이용하여

 

배열의 8번 인덱스에 접근하여 데이터를 가져오면 된다

 

---

 

정리

 

Direct Access Table - 인덱스를 key로 생각하고 데이터를 저장한다

 

-효율적으로 key-value쌍을 저장하고 가져올 수 있다

 

-낭비하는 공간이 많다

 

Hash Table - 고정된 크기의 배열을 만든다

 

-해시 함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다

 

-해시 함수 결과 값 인덱스에 key-value쌍 데이터를 저장한다

---