자료구조 - 해시(Hash)의 특징

자료구조 - 해시(Hash)의 특징

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 자료구조 중에서 중요한 해시(Hash)에 대한 강의 이전 포스팅에 이어서 진행하도록 하겠습니다.

 

정말 어렵지 않으니 잘 따라와주시고,

 

아직 해시의 개념이 잡히지 않았다면

 

이전 포스팅을 읽고 오시는 것을 추천드립니다!

 

 

- 자료구조 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

자료구조 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

 

 

- 해시(Hash)의 특징

1. 데이터 상에 순서가 존재하지 않는다.

해시 테이블은 (Key, value)쌍을 저장하게 됩니다.

여기서는 key, value로 데이터를 저장하기 때문에

 

데이터 상에 순서가 존재하지 않는다는 특징이 있습니다.

2. key는 고유한 값을 가진다.

해시 테이블에서 Value는 key를 기준으로 관리됩니다.

따라서 Key는 고유한 값을 가진다는 특징이 있습니다.

 

예를 들어서 우리가 개인정보를 관리해야 한다고 하면은

이름을 키로 사용할수도 있지 않을까? 생각 할 수도 있습니다.

그런데 이름은 동명이인이 존재할 수 있기 때문에

 

이름은 key로 쓰면 안되는 데이터입니다.

대신에 이런 경우에는 주민번호를 키로 쓰거나 새로운 아이디를 생성해주거나

사람마다 즉, 데이터마다 가지는 고유한 값을 Key로 써야 합니다.

 

 

3. 해시함수의 시간복잡도는 O(1)이다.

해시 함수는 임의의 데이터(키)를 특정 값(해시값)으로 매핑시키는 함수입니다.

 

앞에서 설명드린것처럼 해시 함수를 통해 데이터의 위치가 관리되기 때문에

 

리스트처럼 데이터를 전체 스캔하면서 찾을 필요는 없습니다.

그렇기 데이터가 100개 1000개가 되더라도

 

hash function으로 그 위치를 바로 찾을 수 있기 때문에

 

해시함수를 통한 데이터의 접근은 시간복잡도 O(1)을 갖게 됩니다.

 

 

- 좋은 해시함수란?

좋은 해시함수는 키 값을 고르게 분포시킨다는 특징이 있습니다.

키 값을 고르게 분포시키는게 왜 좋은 해시함수인지는 뒤에서 다시 한 번 다루도록 하겠습니다.

그리고 이 해시값을 계산해주는 속도가 빠릅니다.

스캔하는 속도보다 해시함수의 속도가 느리면 의미가 없겠죠.

 

그리고 좋은 해시함수는 충돌을 최소화 합니다.

충돌이라는 것은 정확하게 해시충돌이라는 말을 쓰는데,

해시 충돌은 키 값이 다른데 해시 함수의 결과 값이 동일한 경우를 말합니다.

헷갈리시면 안되는 게 키는 중복될 수 없어요.

 

키는 중복되면 안되지만 키를 가지고 실행한 해시 함수의 결과값은 중복이 나올 수 있습니다.

 

예를 들어서 이전 포스팅에서 사진으로 고유의 색깔을 찾아주는 프로그램 얘기로 다시 돌아가 보면

제 사진을 넣어도 빨간색이 나오고 여러분의 사진을 넣어도 빨간색이 나오는 경우가 되겠죠.

가장 이상적으로 해시 함수에서는 이런 경우가 있어선 안되겠지만

 

현실세계에서는 이런 경우가 존재할 수밖에 없습니다.

 

그렇다면 코딩을 하다가 해시 충돌이 나면 어떻게 해야 할까요?

 

해시 테이블을 구현할 때 충돌이 발생할 경우 체이닝 방식을 이용해서 충돌을 해결 할 수 있습니다.

 

해시 충돌과 이를 해결할 수 있는 체이닝 방식에 대해서는

 

바로 다음 포스팅에서 다뤄보도록 하겠습니다.

 

로스윗의 코딩캠프는

 

미래의 개발자 여러분을 응원합니다!

 

모두 화이팅!!

 

그림으로 쉽게 이해하는 자료구조 큐(Queue) (ft. 큐를 배열기반에서 절대 선형으로 구현하지 않는 이유)

그림으로 쉽게 이해하는 자료구조 큐(Queue) (ft. 큐를 배열기반에서 절대 선형으로 구현하지 않는