[자료구조] Hash에 대한 간단한 이해

자Hash란?

데이터 관리, 유지를 위한 자료구조.

 

전화번호부, 투표시스템에 사용되기도 함.

 

만약 내가 Apple, Banana, Cow라는 세 개의 단어를 입력 시

이 단어는 Hash 함수를 거쳐, Hash code가 된다.

아래의 표를 참고해보자.

 

Index	Value
A	Apple
B	Banana
C	Cow
D	NULL

 

Hash함수가 어떻게 구현이 되었는지 대충 느낌이 올 것이다.

근데 만약 여기서 ABCD라는 단어를 추가로 입력하게 된다면 어떻게 될까?

Hash Table에 A인덱스에는 이미 Apple이라는 Value가 있다.

그럼 이때 충돌이라는 현상이 발생하게 된다.

 

충돌을 해결하는 굉장히 많은 알고리즘이 있다.

하지만 이 글에서는 가장 대중적인 분리연결법(Separate Chaining)을 사용할 것이다.

분리연결법은 한마디로 Linked List를 이용하여 Value를 링크 시켜서 여러 값을 넣게 하는 것이다.

 

Linked List를 모른다면

http://hyun222.tistory.com/16

 

Index	Value
A	ABCD -> Apple
B	Banana
C	Cow
D	NULL

Linked list를 통하여 이런식으로 입력이 된다.

A라는 Index에 Head(첫번째 값)는 ABCD가 되고, ABCD는 Apple 이라는 값을 가리킨다.

이 방식은 Data가 허용하는한 무한대로 늘릴 수 있다.

 

하지만 데이터의 부피를 많이 차지할 수 있어서 메모리 문제를 야기할 수 있다.