[자료구조] 11. 해시테이블(hash table) 이해하기(feat. codestates, self tutorial)

 

 

 

 

안녕하십니까 다제입니다.

 

지금까지는 배열과 정렬, 링크드 리스트 등에 대해서 배웠습니다. 

오늘은 hash Table에 대해서 한번 배워보도록 하겠습니다. 

 

 

출처 : 이미지 링크 참조

 

** 저장 진행되는 순서 ** 

data -> Hash Function -> Hash Table

 

학습하기에 앞서서 용어를 정리하고 넘어가도록 하겠습니다. 

 

 

** 용어정리 **

해시(Hash) : 데이터를 관리 및 유지하는 자료구조 

해시함수(Hash Function) : 데이터를 효율적으로 관리하기 위해 일정한 규칙으로 데이터를 변환하는 함수

해시값(Hash Value) 또는 해시코드 : 데이터가 해시함수를 통해 변형된 어떤 값

해싱(Hashing) : 데이터가 해시함수를 통해 특정값으로 변형되고 이를 key-value형태로 저장되는 일련의 과정 

해시테이블(Hash Table) : Hashing 과정을 통해 key-value형태로 데이터를 보관하는 장소( 또는 데이터 구조 )

버켓과 엔트리는 아래 그림을 참조해주세요~

출처 : 이미지 링크 참조

 

 

 

배열과 링크드 리스트는 순서를 이용하여 데이터가 저장되어 있기 때문에 인덱스를 이용하여 정보를 탐색하였습니다. 

그러나, 해시에서는 순서정보를 담고 있지 않기 때문에 인덱스를 통해서 데이터를 탐색할 수 없습니다. 이에, 찾고자 하는 값을 다시 해시함수(Hash Function)에 넣어주고 이를 통해 변환된 key으로 Hash Table에서 데이터를 탐색합니다. 바로 이러한 방법으로 탐색을 진행하기 때문에 Hash Table이 빠르게 데이터를 찾을 수 있습니다. 

 

자! 이렇게 Hash Table이 평화롭게 진행이 되면 얼마나 좋을까요?

그러나, Hash Table에 이미 저장된 곳에 또 다른 값이 저장하겠다고 찾아오는 경우가 있습니다. 

해수함수로 연산을 했을 때 동일한 값이 나올 수 있으니까요? 맞죠? 여기까지 이해되시죠?

이미 값이 저장되엉 있는데 나 여기 들어갈래~ 라고 하면 난감합니다. 이러한 문제를 회피하기 위해서 크게 2가지 방법이 있습니다. 

 

바로 체이닝(Chaining)과 개방 주소법(Open Addressing) 방법입니다. 

 

1. 체이닝(Chaining)

 버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식입니다.  

 → 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.

 → 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다

 

2. 개방 주소법(Open Addressing)

 체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않습니다.(Closed Addressing) 하지만 개방 주소법의 경우에는 다릅니다. 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 합니다. 개방 주소법은 대표적으로 3가지(선형탐색, 제곱탐색, 이중해시)가 있습니다.

선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.

 

제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)

 

이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

출처: https://preamtree.tistory.com/20 [Preamtree의 행복로그]

 → 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.

 → 삽입,삭제시 오버헤드가 적다.

 → 저장할 데이터가 적을 때 더 유리하다.

 

 

금일 학습한 내용은 여기까지 입니다. 

추가적으로 학습을 진행하여 업데이트 진행토록 하겠습니다. 

 

해당 포스터는 아래 유튜브와 링크를 참조하여 포스팅 진행하였습니다. 
출처 : https://www.youtube.com/watch?v=xls6jEZNA7Y&t=197s
출처: https://preamtree.tistory.com/20 [Preamtree의 행복로그]

 

오늘도 방문해주셔서 감사드립니다.