자료구조 - 해시충돌과 해결방안

자료구조 - 해시충돌과 해결방안

 

안녕하세요.

 

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

 

오늘은 자료구조 중에서 중요한 해시(Hash)충돌과 이에 대한 해결방안 강의를 진행하도록 하겠습니다.

 

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

 

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

 

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

 

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

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

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

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

 

-해시충돌이란?

-> 해시충돌이란 Key값이 다른데 동일한 해시값이 나온 경우 입니다.

 

이전 강의에서는 알록달록 서랍에서 사진 이미지를

 

해시function에 넣었을 때 해시값으로 고유한 색깔이 나와야한다고 했습니다.

 

해시설명 그림 예시

 

그런데 어떤 회원의 사진 이미지를 넣었는데

 

다른 회원의 해시값 색깔이 나와버린다면 해시충돌이 일어난거라고 볼 수 있습니다.

 

 

 

해시충돌 그림 예시

 

 

이 해시충돌은 

 

해시 자료구조의 성능을 떨어뜨리는 가장 큰 원이 되기 때문에

 

해시 함수를 가능한한 해시충돌이 적게 발생하도록 구현을 해야 합니다.

나쁜 해시함수는 이런 해시충돌이 많이 일으키는 해시함수가 되겠죠.

 

제가 '적게'라는 표현을 썼습니다.

그 이유는 해시충돌울 아예 피할 수는 없기 때문입니다.

 

컴퓨터 사이언스에서는 그 원인을 비둘기집 원리로 설명합니다.

 

 

 

비둘기집 원리

 

- 비둘기집 원리

비둘기집의 원리는 N+1개의 물건을 N개의 상자에 넣을 때는

 

적어도 어느 한 상자에는 두 개 이상의 물건이 들어가야 한다는 것을 말합니다.

쉽게 말해서 앞에 있는 알록달록 서랍은 총 12칸 밖에 없었는데

 

실제로 우리가 저장해야 하는 회원수가 13명 혹은 그 이상이라면 모든 회원의 데이터를 저장하기 위해서

어느 서랍칸에는 2명 이상의 데이터를 저장할 수 밖에 없게 됩니다.

해시 테이블에서는 인덱스의 개수가 한정되어 있습니다.

하지만 우리가 사용 가능한 데이터의 Key의 숫자는 해시테이블의 인덱스 수보다 많고

해시 함수의 특성상 무한대의 Key입력도 넣으려면 넣을 수 있습니다.

그렇기 때문에 해시충돌은 필연적으로 발생할 수 밖에 없는 구조인겁니다.

그리고 해시충돌에는 Birthday problem이라는 또다른 문제가 있습니다.

생일 문제도 비둘기집 원리와 비슷한 개념이라고 보시면 됩니다.

 

 

 

 

Birthday problem

 

- Birthday Problem

임의의 사람 N명이 모였을 때 그 중에 생일 같은 두 명이 존재할 확률을 구하는 문제입니다.

생일의 가능한 가짓수는 365일에 윤달인 2월 29일을 포함한 총 366가지가 가능합니다.

그러면 총 366명 보다 많은 사람이 모여야지 생일이 같은 경우가 존재하겠다고 생각할 수 있겠지만

수학적인 확률로 계산을 해봤을 땐 23명만 모여도 생일이 같은 두 사람이 존재할 확률은 50%가 넘습니다.

그리고 50명만 모여도 그 안에 같은 생일인 사람이 존재할 확률이 무려 97%나 됩니다.

 

지금 이 자료구조 파트에서 이 확률이 어떻게 계산되었는지 자체가 중요한 것은 아니기때문에 

굳이 수학적으로 계산해보지는 않을거에요.

그래도 굳이 왜 이런 확률이 나오는지 궁금하시다면

 

구글에 birthday problem을 검색해보시면 됩니다.

 

- 정리 및 요약

Key의 개수가 해시 테이블의 인덱스 개수와 비슷한 수준까지는 아니더라도

 

충돌이 발생할 가능성은 여러분이 생각하는 것보다 높을 수 있다는 점입니다.

 

인덱스의 일정 비율 이상만 데이터가 채워져도 충돌의 확률은 급격하게 증가합니다.

따라서 해시 충돌이 났을 때 이것을 꼭 해결해야합니다.

그러면 어떻게 해결할까요? 

 

해시 총돌을 해결하는 두 가지 방법에 대해서는

 

다음 포스팅에서 이어서 자세히 다루도록 하겠습니다.

 

로스윗의 코딩캠프는

 

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

 

여러분 모두 화이팅!!

 

자료구조 - 해시충돌 피하기 (ft. 체이닝, open addressing)

자료구조 - 해시충돌 피하기 (ft. 체이닝, open addressing)

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!