자료구조로써의 Hash (해시) 개념 이해를 위한 간단한 그림

'Hash 해시' 는 크게 컴퓨터 공학에서 말하는 큰 개념으로서 Hash 와

암호학에서의 의미(단방향 암호화의 한 종류인 Hash ),

그리고 자료구조로써 활용되는 Hash 로 나누어 볼 수 있습니다.

 

결국 모두 같은 Hash 이므로 각 분야가 집중하는 기능/속성에 따라 활용법의 차이가 있는 것일 뿐입니다.

 

이번 시간에는  '자료구조로써 활용되는 Hash'  에 대해서 알아보겠습니다.

 

 

 

 

이번 글은 ' Hash ' 의 기본 개념을 이해하고 있다는 전제 하에 작성되었습니다.

 

 

 

 

컴퓨터 공학에서 말하는 큰 개념으로서 ' Hash ' 가 궁금하다면 아래글을 먼저 봐주세요.

'해시 Hash' 개념 이해를 위한 간단한 그림

 

 

 

 

암호학에서의' Hash ' 가 궁금하다면 아래글을 봐주세요.

암호학에서의 'Hash (해시)' 개념이해를 위한 간단한 그림

 

 

 

 

 

 

 

들어가기 앞서, 본문에서 사용되는 " 0 부터 n 사이의 정수 " , " 0 부터 시작되는 정수" 등과 같은 표현은

정확히 말하면 (0 이 정수가 아니기 때문에) "0 과 1부터 n 사이의 정수", " 0 과 1부터 시작되는 정수" 가 올바른 표현입니다. 

편의를 위해 위와 같은 표현이 사용되었다는 점을 알려드립니다.

 

 

 

 

 

 

 

자료 구조의 기본 개념

 

 

먼저 ' 자료 구조 '란 무엇일까요?

 

자료 구조란 최적의 실행 성능을 갖기 위해 데이터들을 어떻게 조직하여 저장하고 관리할지를 결정하는 것입니다.

 

 

최적의 생활 성능을 위한 방의 " 자료구조 "입니다만?

 

 

 

 

이해를 돕기 위해 가장 일반적이고 자주 사용되는 자료 구조인 ' Array list (배열) ' 를 한번 살펴보겠습니다.

 

array list 는 일정 크기의 연속되는 메모리 공간을 미리 정하고 첫 번째 자리부터 데이터를 순서대로 착착 저장하는 방식의 단순한 자료 구조입니다.

 

이때 전체 데이터는 하나의 덩어리로 인식되며 그 속에 착착 정리된 각 데이터는 ' index ' 라고 하는 0 부터 시작하는 순번을 가지게 됩니다.

이런 array list 는 어떤 장단점을 가지고 있을까요?

 

array list 는 index 라는 순번이 존재하기 때문에 원하는 데이터를 바로 찾을 수 있다는 장점이 있습니다.

 

예를 들어 철수라는 사람을 찾고 싶은데 번호표도 없고 모두가 질서없이 아무렇게나 서있다면,

 

철수라는 사람을 찾을 때 까지 모두를 일일이 확인해봐야 할 것입니다.

 

하지만 모두가 순번이 있고, 0번 부터 차례대로 서있다면,

 

철수라는 사람의 순번으로 곧장 찾아가면 되는 것이죠.

 

 

 

 

이렇게 index 를 통해 해당 데이터로 바로 접근하는 것을 ' Random access (임의 접근) ' 이라고 합니다.

 

random access 가 가능하면 데이터를 조회하고 수정하는 것에 굉장히 용이합니다.

 

누가 몇번 째에 있는지를 알고 있으니, 그 곳으로 곧장 찾아가 만날 수도 있고,

 

만약 몇번 째에 있는 누군가를 다른 누군가로 바꾸려고 할 때도 곧바로 해당 순번으로 접근해 바꿔줄 수 있는 것이죠.

 

 

 

 

 

 

 

 

 

그렇다면 단점으로는 어떤 것들이 있을까요?

 

array list 는 데이터 전체에 순번이 존재하기 때문에 데이터들이 연속적으로 배치되어야 합니다. 

 

그 덕분에 random access 가 가능하고 조회와 수정이 쉬웠죠.

 

하지만 동시에 이러한 특성 때문에 데이터를 중간에서 추가하거나 삭제하는 것에는 번거로움이 있습니다.

 

몇번 째에 있는 누군가를 다른 누군가로 바꾸는 건 전체 순번에 영향을 주지 않습니다.

 

하지만 몇번 째의 누군가를 빼내기만 하고 싶은 경우에는 어떨까요? 

 

혹은 누군가를 중간 순번에 끼워넣고 싶은 경우에는?

 

이럴 경우 해당하는 순번 뒤로 모든 사람들의 순번이 한 칸 씩 밀리거나 당겨지게 됩니다.

 

즉, 전체 순번에 영향을 주기 때문에 다시 순번에 맞게 index를 할당해야 하는 번거로움이 발생하는 것입니다.

 

 

 

또 array list 는 데이터를 담을 '연속된 메모리 공간의 크기'를 미리 정해두기 때문에, 하나의 덩어리로 인식되는 '전체의 크기'를 변경할 수 없습니다.

 

즉, 앞에서부터 착착 데이터를 저장할 때 비어있는 뒷 공간이 있다면 메모리 공간의 낭비가 발생할 수도 있고

 

반대로 만약 저장할 데이터의 양이 미리 정해둔 전체의 크기를 넘어간다면 더이상 저장할 수가 없는 것입니다.

 

 이 경우는 새로운 array list 를 더 큰 크기로 만들고 모든 데이터를 옮겨야 하는 비효율이 발생할 수도 있습니다. 

 

 

 

 

 

 

 

 

 

그렇다면 이번에는 이러한 단점들을 보완하기 위해 등장한 자료 구조 중에서, ' Linked list (연결 리스트) ' 라는 자료 구조를 한번 살펴보겠습니다.

 

linked list 는 데이터들을 임의의 공간에 따로따로 저장하는 대신, 각 데이터마다 '그 다음 데이터의 위치'를 함께 저장하는 방식으로 데이터들 간의 전후관계를 설정하는 자료 구조입니다.

 

이때 데이터와 함께 저장되는 다음 데이터의 위치를 ' Pointer (포인터) '라고 하고 데이터와 pointer 를 묶어 하나의 ' Node (노드) ' 라고 표현합니다.

Pointer 로 다음 Node 를 가르키는 Node들

 

 

 

linked list 는 (array list 와 달리) 미리 전체 크기가 정해진 하나의 덩어리로 데이터를 저장하는 것이 아니라, 필요할 때마다 임의의 공간을 할당하기 때문에 전체 크기의 '가변성'을 가집니다. 

 

저장할 데이터의 양이 늘어나면 그에 맞게 자료 구조의 전체 크기도 늘어나는 것이죠.

 

또한 메모리 공간상에서 연속적으로 배치되지 않기 때문에 전체 순번이라는 것도 존재할 수 없습니다.

 

따라서 데이터를 중간에서 추가하거나 삭제할 때 전체 순번이 밀리고 자시고 할 것도 없이, 해당 노드의 전후 관계만 재설정 해주는 것으로 간단히 수행할 수 있는 것이죠.

추가된 Node 에 맞춰 제자리에서 삿대질만 재설정.

 

 

 

 

하지만 그렇기 때문에 각 데이터들을 전후 관계로만 접근할 수 있다는 큰 단점도 존재합니다.

 

random access 가 불가능한 것이죠.  데이터에 접근 (혹은 수정) 하고자 할 때, 해당 데이터를 찾기 위해 첫 node 부터 pointer 를 타고타고 원하는 데이터로 접근할 수 있는 것입니다.

 

 

 

 

 지금까지 살펴본 두 자료 구조를 정리하자면... 

 

 

 

 

 

 

이렇게 자료구조가 무엇인지에 대한 기본 개념과 가장 일반적인 자료 구조 두가지를 알아보았는데요.

 

이렇듯 자료구조는 필요와 목적에 맞춰 아주 다양하게 존재합니다.

 

자료구조를 공부한다는 것은 결국 다양한 자료 구조 각각의 장단점을 이해하고 상황에 맞게 최적의 자료구조를 선택할 수 있는 능력을 키우는데에 있는 것입니다.

 

 

그렇다면 더더욱, 보다 많은 자료구조에 대해 이해하는 것이 유리하겠죠?

 

그럼 어서 빨리  Hash 가 자료 구조로써 어떻게 활용되는지 본격적으로 알아보러 가보겠습니다.

 

 

 

 

 

 

 

 

Hash table  (해시 테이블)

 

 

Hash.. table.. 뭔가 Hash 를 사용해서 테이블을 만든다는 소리인 건 알겠는데, 그래서 도대체 Hash table 은 어떤 것일까요?

 

사실 여러분들 대부분은 이미 Hash table 을 아주 유용하게 잘 사용해 왔을 것입니다.

 

왜냐하면 JS의 object, Python의 dictionary, Java의 hash map 등 " key : value " 로 데이터를 저장하는 이 모든 것들이, 바로 Hash table 을 사용하여 구현되어있기 때문입니다.

 

Hash 를 활용하여 원하는 데이터를 쉽고 빠르게 찾기 위해 만든 자료 구조가 바로 ' Hash table ' 입니다.

 

Hash table 은 저장하고자 하는 데이터의 Hash 값 을 index로 활용하여 데이터를 저장하는 방식의 자료 구조입니다.

 

이때 데이터를 저장할 공간은 미리 전체의 크기를 정하고 그에 맞게 연속된 메모리 공간을 할당합니다.

(그렇습니다. ' array list ' 와 메모리 할당 방식이 같습니다.)

 

그렇다면 이미 index 값으로 데이터에 빠르게 접근할 수 있는 ' array list ' 가 있는데, Hash table 을 사용해야하는 이유가 무엇일까요?

 

사실 array list 는 찾고자 하는 임의의 데이터가 있을 때, 데이터의 값은 아는데 순번을 모르는 상황이라면,

 

결국 원하는 데이터를 찾기 위해 모든 테이터들을 일일이 탐색해야만 합니다.

 

데이터 값을 안다고 해도 그 데이터의 index 를 모른다면 random access (임의 접근) 가 불가능한 것이죠.

 

index 란 0 부터 차례대로 매겨진 순번입니다. 다시말해, ' 일정한 범위 내의 정수 '를 할당하는 것이고 이를 이용해 데이터에 접근하는 것이죠...

 

어????!!!! 임의의 데이터와?? 일정한 범위 내의 정수?? 바로 뭔가 떠오르지 않나요???

소오름

 

그렇습니다! 바로 Hash 가 이러한 문제를 해결하기 위한 적임자라는 생각이 듭니다.

 

어떠한 데이터든 일정한 길이의 정수로 만들어주는 Hash, 그리고 그렇게 얻은 Hash 값을 index 로 활용해 데이터를 저장해둔다면?

 

이때의 index 는 순번의 개념이 아니기 때문에 굳이 순서대로 착착 배치할 필요도 없을 뿐더러, 어떠한 타입의 데이터를 가지고도 random access 가 가능해지는 것입니다.

 

왜냐하면 찾고자 하는 데이터가 어차피 Hash 함수를 통해 고유한 일정 범위의 정수로 바뀔 것이고, 이를 index 로 사용하여 저장되어 있기 때문에 그에 맞게 곧장 접근할 수 있는 것이죠.

 

 

그래서 Hash table 은 Hash 함수 를 자료 구조에 포함하고 있습니다.

 

이때의 Hash 함수 는 ' 암호화 '를 위해 사용할 때와는 알고리즘이 추구하는 방향이 달라야 할 것입니다.

 

일단 해시값을 index 로 사용하기 위해서는 ' 0 부터 n(미리 할당한 메모리 공간의 크기) ' 내에서 ' 정수 '를 반환해야 합니다.

 

그래서 보통 자료 구조에서 활용되는 Hash 함수 는 알고리즘의 마지막 단계에서 모듈러 연산을 포함하는 것이 일반적입니다.

 

모듈러 연산  : 한 숫자를 다른 숫자로 나누고 그 나머지를 구하는 연산

 

Hash 를 통해 얻은 일정 크기의 정수값을 n 만큼 나눈 나머지는 0 부터 n 사이의 정수일 것이니 말이죠.

 

 

실제는 이미지와 다를 수 있습니다.^^

 

 

 

 

이제 왜  Hash table 이 원하는 데이터를 찾는데 쉽고 빠른 자료 구조인지, 그 이유가 잘 이해되셨을 것입니다.

 

 

 

 

 

 

충동가능성 과 대처 방법

 

하지만 Hash table 도 어쨌든 Hash 를 사용하기 때문에 저장하고자 하는 데이터가 늘어남에 따라 충돌이 필연적으로 발생합니다.

 

심지어 Hash table 에서는 Hash 값을 ( 할당 받은 공간의 크기에 맞춰 ) index 로 또 한번 환산해야하기 때문에,  그렇게 범위를 축소하는 과정에서 더 자주 더 많은 충돌이 발생할 수 밖에 없습니다.

 

그렇기 때문에 Hash table 은 충돌에 대처하는 방법으로 보통 두 가지, ' Separate chaining (개별 체이닝) ' 과 ' Open adressing (오픈 어드레싱) ' 을 사용합니다.

 

 

' Separate chaining ' 은 충돌이 발생했을때 미리 할당된  Hash table 공간 외의 공간에서 새로운 Node 를 만들고 기존의 데이터에 Pointer 를 추가하는 방식입니다.

 

그러니까 Hash table 의 각각의 index 마다, 충돌이 발생하여 여러 데이터가 쌓일 경우를 대비해 개별적으로 linked list 를 만들고 체인처럼 이어붙이는 방식인 것이죠.

 

 

파..파도 맛있습니다...

 

 

 

Separate chaining 방식은 아무리 충돌이 많이 발생하더라도 메모리가 허용된다면 사실상 무한정 데이터를 저장할 수 있습니다.

 

하지만 그렇다면 결국 일일이 데이터를 찾는 방식과 다르지 않기 때문에 해시 테이블을 사용할 이유가 없어져 버리긴 합니다.

 

그리고 문제는 미리 할당한 메모리 공간의 활용도가 떨어진다는 점에 있습니다.

 

어딘가에선 충돌이 발생해 linked list 로 추가 메모리 공간을 사용하는데, 어딘가에선 아직 데이터를 할당받지 않는 index 공간이 낭비되고 있을 테니 말이죠.

 

 

 

 

 

그래서 이렇게 미리 할당한 table 공간을 최대한 활용하고자 만들어진 충돌 대처 방법이 ' open adressing ' 입니다.

 

open adressing 은 충돌이 발생했을 때 아직 할당되지 않은 index 의 빈 공간에 새로운 데이터를 할당하는 방식입니다.

 

이 경우 모든 데이터가 자신의 해시값과 연결된 index 공간에 저장된다는 보장은 없습니다.

 

그리고 미리 할당된 table 전체 크기를 초과한 데이터는 저장할 수 없다는 단점도 존재합니다.

 

참고로 이러한 open adressing 방법은 충돌 시 대체할 공간을 선정하는 기준에 따라 또 세부적인 방법이 나눠지기도 합니다.

 

 

 

 

 

이렇듯 Hash table 은 Hash 함수 에 대한 의존도가 굉장히 높습니다.

 

Hash 함수 는 기본적으로 Hash 값 이 전체에 걸쳐 균등하게 배정되게 하는 것이 중요하고, 그럼에도 충돌이 발생했을 때 어떤 대처 방법을가지고 있는가도 중요한 사항입니다. 

 

그러니까 Hash table 을 사용할 때는 보유할 데이터의 특성과 규모에 맞게 얼마나 견고하고 빠르게 효율적으로 잘짜여진 Hash 알고리즘을 사용하느냐가 중요한 것입니다.

 

 

 

 

 

 

 

 

 

지금까지 Hash 가 자료 구조에서 어떻게 활용되는지, 그리고 그렇게 만들어진 자료 구조 ' Hash table ' 은 무엇인지에 대해서 알아보았습니다.

 

그럼 앞서 배운 두 가지 자료 구조들과 함께 정리를 하며 마치겠습니다~