네 여러분 반갑습니다. 자 오늘은 6월 14일 현지 시간 6시 약 45분 지난 시간에 해시맵의 해시 충돌에 대해서 살펴봤다면 오늘은 이 해시

충돌을 어떻게 해결할 수 있는지 그 해결 방법에 대해서 살펴보도록 하겠습니다. 긴장하지 마시고 잠시 몸을 그리고 마음을 편하게 풀어 주신 뒤에 저와 함께

출발해 보시죠. 자 회, c 춤도 우리가 해시 충분히 어떤 건지는 지난 시간에 충분히 살펴보았기 때문에 그에 대해서는 설명하지 않구요.

이제 그 해시 충돌을 어떻게 해결할 수 있는지 그 해결 방법에 대해서 살펴보도록 하겠습니다. 해시 충돌 해결 방법은 크게 두 가지로 나뉘는데요. 하나는 체인 방식이 있고 또 다른 하나는 오픈 어드레싱 방식이 있습니다.

먼저 체인 방식은 추가적인 공간을 활용해서 해결하는 방식이에요. 해시맵은 배열로 구현되어 있다는 것을 지난 영상을 통해서 우리가 확인했는데 그 배열 외에도 추가적인 공간 활용을 해 가지고 충돌이

발생하면 그 공간에 추가적으로 저장하는 방식입니다.

발생했을 때의 추가적인 공간으로 데이터를 저장한다. 그래서 그 대표적인 방법이 링크드 리스트를 사용한다. 이렇게 이해하시면 될 것 같구요.

자, 그리고 두번째로 2. 오픈 어드레싱 방식은 뭐냐? 추가적인 공간을 사용하는 게 아니에요. 비어있는 인접한 공간을 활용해서

충돌을 해결하는 방식입니다. 그래서 추가적인 공간 활용을 하지 않아요. 이미 있는 확보된 배열 만으로 순수히 충돌 해결하는 방식입니다.

세부적으로 살펴보면 크게 세 종류로 나뉘는데요. 하나는 리니어 프로빙 방식으로써 고정 폭으로 이동하여 빈 공간을 찾는

방식입니다. 그리고 두번째로는 쿼드러틱 프로빙 방식으로써 제곱 폭으로 이동하여 빈 공간을 찾는 방식이에요.

그리고 마지막으로 더블 해싱 방식으로써 충돌이 발생했을 때 또 다른 해시 함수를 사용해서 빈 공간을 찾는 그런 방식이 있습니다.

자 뒤에서 예를 통해서 설명될 테니까요 바로 예제로 넘어가시죠 그래서 뭐 이제 3 파이트 케인 방식으로 어떻게 해시 충돌을 해결하는지를

살펴보도록 할게요 먼저 이 어레이처럼 배열처럼 보이는 이것은 눈치 빠르신 분들은 이미

아시겠지만 바로 해쉬맵입니다 으 해쉬맵 이구요 해쉬맵은 내부적으로 배열로 구현되어 있다고 했잖아요

이 배열에 사이즈는 지금 제가 예를 들기 위해서 사이즈는 10으로 잡았습니다 이렇게 자 그리고 얘를 편하게 또 쉽게 되기 위해서 앞으로 예제에서는 키와 밸류가

값이 같다고 할게요 즉 키가 100이면 밸류도 100인거고 키가 921이면은 밸류도 921 이런겁니다

쉽게 이해를 시켜 드리기 위해서 지금 키 밸류 값이 같다고 정의를 할게요 자 그리고 키 밸류 순서는 이렇게 됩니다 위에서부터 아래로 그래서

100을 놓고 그 다음에 921 그 다음은 506 이 순서대로 이제 넣게 된다고 보시면 될 것 같습니다 자 그러면 이제 3 플레이트 체인 방식이 링크드 리스트를 통해서 어떻게

해시 충돌을 해결하는지를 같이 예제를 통해서 살펴보도록 할게요 자 먼저 덱을 넣었어요 덱을 넣었으며 는 키가 100인 거죠 벨류는 백

인거고 이때에 100에 대해서 해쉬 펑션에 적용을 했더니 해쉬 값이 1이 나왔습니다 그리고 이 1에 대해서 해쉬 테이블 사이즈는 5로 모듈러 연산을 했더니

최종적으로 1이 나왔어요 그러면은 요기에 저장이 되겠죠 이때 3 플레이트 체인링은 어떤 식으로

링크드 리스트를 통해서 충돌을 해결했냐면 보통은 여기에다가 벨류 값인 백을 저장을 하겠죠 그런데 그렇게 하지 않고

요 공간은 배열에 데이터를 저장하는 이 공간은 노드를 가리킬 수 있는 포인터로 사용하게 됩니다 자 지금 그래서 백을 저장해야 되는 상황인 거잖아요 이때에

노드 하나를 100으로 만들고 얘가 예를 가리키게 됩니다. 자, 이어서 이제 부족해 볼게요. 그 다음에 이제 921을 넣어야 돼요.

키 921을 해시 함수에 넣었더니 해시 값이 12가 나왔습니다. 12에 대해서 10으로 모듈 연산을 했더니 최종적으로 2가 나왔어요.

그럼 이는 요기를 가리키게 되겠죠. 그럼 이때도 마찬가지로 어떻게 되느냐, 요기에 데이터 자리에 바로 921 쓰는 것이 아니라

노드를 하나 만들고 921 하나 만들고 애가 얘를 가리키게 됩니다. 자, 아직까지는 충돌은 나지 않았어요. 그 다음에 넘어가 볼게요. 키 506, 해시 함수에 넣었더니 어떤 해시

값이 10이 나왔고 10에 대해서 10으로 모듈 연산을 했더니 0이 나왔습니다. 충돌이 됐죠. 그러면 이때 어떻게 하냐면은 새로운 노드를 하나 추가할

해요. 이때 새로운 노드를 어떻게 추가를 하느냐, 링크드 리스트의 헤드에 놓습니다. 해드에 넣는다는 게 무슨 말이냐면은 자 여기 이렇게 지우고 쪽이 하나도

만들어요 그리고 여기에 506을 넣습니다 그리고 얘는 얘를 가르키는 거예요 얘 되셨죠 얘가 지금 예를 가르치는 거

헤드의 새로운 노드를 추가해야 새로운 뭔가를 추가를 할 때 빠르게 넣을 수 있어 그게 아니라 이 맨 끝자리 끝자리에 놓게 되면은

만약에 링크드 리스트가 되게 길어지면 그 짜리까지 찾아가는 데 시간이 좀 걸리겠죠 그래서 보통은 헤드에 넣는다 헤드의 앞쪽에 넣는다

이렇게 생각을 하시면 될 것 같습니다 자 다음 걸로 바로 넘어가 볼게요 다음은 200입니다 이 백을 해시 함수에 넣었더니 해시 값이 2가

나왔어요 10으로 모듈러 연산했더니 이 또 2가 나왔습니다 그러면 위치가 어떻게 되죠 또 여기 충돌이 발생했네요 그러면 마찬가지로 얘도 이제 해시에

넣어야 되니까 짐작이 가시죠 요 부분을 주력 지워주고 테일 노드를 추가를 합니다 그리고 제가 얘를 가리키고 여기 200을 놓고 이렇게 어렵지 않습니다

그래서 인덱스는 또 새로운 추가된 노드를 가리키게 되는 겁니다. 마지막으로 또 787 한번 볼까요? 추려 87을 해쉬 펑션에 입력해서

넣었더니 해쉬 값이 22가 나왔구요. 그 22에 대해서 10으로 모듈러 연산했더니 또 이거 나왔습니다.

예, 이거 또 나왔어요. 금토요일이잖아요. 그러면 또 헤더에 넣어야 되겠죠. 지금 축 ob 루주 여기에 하나 또 추가를 합니다.

787 넣고 헤드는 또 새로 추가된 노드를 바라보게 되는 거죠. 3 플레이트 체인 방식은 이런 식으로 이제 문제를 해결한다.

이렇게 이해를 하시면 될 거 같습니다. 어렵지 않죠? 자, 그런데 딱 보시면 어떤가요? 좀 장단점이 있겠죠? 아무래도

추가적인 메모리 공간을 쓴다는 것도 어떻게 보면 단점이면 단점이다라고 볼 수 있을 것 같구요.

또 링크드 리스트가 너무 길어지면은 탐색하는 데 또 오래 걸릴 수 있겠다 뭐 그런 단점이 또 있을 수도 있겠습니다.

아무튼 이런 식으로 해결을 한다고 보시면 될 것 같아요. 자, 이어서 이제 설명을 드리 방식은 오픈 어드레싱 방식인데요.

오픈 어드레싱 방식에서도 먼저 리니어 프로빙 방식에 대해서 좀 설명을 드리도록 하겠습니다. 일단 앞에서 설명 드렸던 걸 리마인드 한번 하면은 오픈 어드레싱 방식은

추가적인 메모리 공간을 사용하지 않고 이미 확보된 공간만을 가지고 해결하는 방식. 즉 충돌이 발생했다면 인접 바뀌어 있는 공간을 활용한다.

그러한 컨셉이라고 말씀드렸죠. 그중에서도 첫 번째, 리니어 프로빙 방식에 대해서 설명드릴게요.

자, 아 먼저 개념적으로 예를 좀 먼저 살펴보죠. 원래 슈퍼 오션 이었는데 슈퍼 줘야 될 p라고 해 가지고 2

리니어 프로빙, 리니어 프로빙 첫 글자로 땄습니다. 그래서 얘는 어떻게 동작을 하냐면, 기뢰에 의해 슈퍼쇼 4 키를 입력한

그 해시값, 해시값 앞에다가 i를 더하는 거예요. 여기서 i는 뭐냐면 충돌 횟수입니다. 충돌 횟수를 쓰는 건데, 맨 처음에는 충돌이 일어나지 않을 테니까, 왜냐면 일단 계산

부터 해야 충돌이 날지 안 날지 아는 거니까, 맨 처음에는 0이고, 그 다음 1, 2, 3 이렇게 충돌 횟수가 증가한다고

보시면 될 것 같아요. 자, 앞에서 이 예제가 어떻게 된다고 설명을 들었으니까, 이제는 자세히 설명하지 않겠습니다. 63대로 가고 키 밸류는 둘 다 값이 똑같다.

즉 키 102만 펠릿 500, 키가 920이면 밸류도 921 이런 식으로 예제가 된다. 다 이해하고 계실 거고요. 그러면 이제 본격적으로

살펴보도록 하겠습니다. 먼저 자바의 맨 처음에 값을 구한 이 값은 i 값을 0으로 넣었어요. 이 요기에 대입을 하는 거죠. 자바를 먼저 놓고 지금은 충돌이 일어나기 전

맨 처음 회식 값을 계산하기 위한 거니까 i 값이 0으로 넣었을 때의 예시 펑션에 값을 어떤 일이 났어요

그걸 식으로 모듈러 연산을 했더니 또 이렇게 나왔습니다 앞에 이제는 똑같죠 금요 기록하게 됩니다 요기서는 리니어 프로빙 방식이

오픈 해싱이 1 돈이기 때문에 바로 100 이라는 값을 쓰시면 돼요 100 비어 있으니까 써 주면 되죠

두 번째로 920 일에 들어왔고 아직 충돌 전 회식과 서구 하는 타이밍이니까 충돌 전이라서 이 파라미터를 해쉬 펑션에 넣었더니 어떤 12 가 나왔습니다

그리고 이 해쉬 값이 비를 식으로 모듈러 연산 했더니 이렇게 나왔어요 여기에 저장을 하게 되겠죠 그러면은 여기에는 920 일이 저장됩니다

아직까지는 충돌이 일어나지 않았어요 그 다음에 자 506 을 넣었더니 회식 보신 어떤 21 이라는 해쉬 값이 나왔고 예를 10으로 모듈러 연산했더니

일이 나왔습니다. 충돌이 발생했습니다. 이미 백이라는 값이 있어 요금 506을 저장할 수가 없잖아요. 그럼 이제부터 어떻게 되냐면은 플러스 1이에요.

그럼 이제부터 하나하나씩 더 하는 거예요. 찍어 충돌이 한번 났네. 그 일을 더 해요. 그럼 두 번째로 갑니다. 두 번째 인덱스로 가요.

그런데 여기서 921 있어요. 그럼 또 1을 더 해요. 그럼 다음 칸으로 갑니다. 꼭 여기에 갔더니 비어 있네요.

그래서 여기에다가 뭘 쓰냐면은 506이 있습니다. 자, 다음 걸로도 넘어가 볼게요. 다시 이제 200을 넣어요. 회식 펑션 a 백을 어떤 해시 값이 2가

나왔고 10으로 모듈 연산 3rd 또 2가 나왔습니다. 요 길을 가르쳐 줘. 또 충돌이 났어요. 어 충돌이 났으니까 또 해결해야 되겠죠.

920 1이라는 값이 이미 인덱스에 있기 때문에 그 다음 것을 봐요. + 1을 했으니까. 근데 506이 또 있네요. 그럼 또 그 다음 걸로 가봐요.

비어 있습니다. 그래서 이 자리에 뭘 쓰느냐 이제 이 백합 썼어요. 마지막으로 787 넣었더니 어떻게 되는지 한번 봅시다.

787 키 밸류를 넣으니까 폐 식품 신의 먼저 어떤 해시 값이 22가 나왔고 21의 식으로 묻을 예상했던 최후로 또 2가 나왔어요.

또 충돌이 줘 또 충돌이 났습니다. 또 1씩 더 하는 거예요. 일을 다 했더니 아 또 오른쪽이 있네.

또 예를 더 했더니 아 202 있네. 한번 더 이랬더니 또 비어 있어요. 그래서 여기에 787을 쓰는 겁니다.

어떤가요? 어렵지 않죠? 그런데 좀 특징을 보입니다. 어떤 특징을 보이냐 며 는

얘네들 이렇게 모여 있어요. 뭔가 클러스터링이 된 거 같아요. 군집 현상이 발생하게 된 겁니다.

자 어쨌든 이게 5판 어드레싱에 리니어 프로빙 방식이구요 자 바로 또 다음 예제로 넘어갈게요

이번에 높은 어드레싱 방식이 쿼드래틱 프로빙 방식을 설명을 드릴께요 자 쿼드래틱 프로빙 방식은 먼저 이 펑션을 살펴볼게요 여기서 보시면 해

슈퍼 키 4 컷 에티 프레임 방식으로 썼다 그래서 키 값과 충돌 몇번째 충분히 i 값을 놓았으면 실제 구하는 방식은 길의 해쉬 펑션 의 i

스퀘어 를 구해서 더한다 이렇게 이해를 하시면 될것 같습니다 자 여기서 제가 i 스퀘어 라고 그냥 하긴 했지만 아 i 제곱 라고 하긴 했지만 사실에 e 앞에 어떤

상수가 또 있을 수도 있어요 무슨 말이냐면 뭐 이게 지금은 예제를 쉽게 들기 위해서 아 i 제곱

라고 하긴 했지만 모 씨 호 파기 아이 제곱 여기서 이제 씨는 상수가 되는 거고 뭐 이런식으로 편 될 수 있고 좀 더 복잡하게 4 c1 곱하기

아이 제곱 플러스 c 쭉 곱하기 i 뭐 이런 식으로 복잡하게 할 수 있습니다 지금은 커드 지퍼 빙의 예제를

심플하게 간단하게 하기 위해서 그냥 아이 제곱으로 한 거예요 그리고 이외에 4 충전해서 쓰는 아까 설명드렸던 것처럼 0부터 아이가

시작한다는 거 자 그리고 넣어서 이 순서대로 입력이 된다는 것 기억해주시고 자 다시 한번 들어가 볼게요 자 잘 따라오고 계시죠 지금은 오프너 드레싱에 허드레

디퍼 빈 방식입니다 먼저 102 들어갑니다 100에 대해서 해시 함수에 넣었더니 해시 값이 10이고 10으로 모듈 연산을 했더니 1이 나왔습니다

이렇게 들어가죠 100 그 다음도 마찬가지일 거예요 921 해시 함수에 넣어서 11일 해시 값을 뽑아냈고 거기에 10으로

모듈 연산했더니 2가 나왔다 요 비취가 되고 여기에는 920일이 들어가게 됩니다 아직까지 충돌이 나지 않았어요 자 그 다음에 다시 해시 펑션에 506

을 넣었고 해줄까 비리 나왔고 그 11을 10으로 모듈 연산했더니 1 예상했던 일이 나왔습니다 자 충돌이 발생했습니다 충돌이 발생했을 때에 어떻게 통역을 하는 지를 잘

보세요 이전에는 그냥 1씩 더 하게 됐을 때 네 근데 지금이 제일 제곱입니다 처음에 충돌이 나기 전에는 i 값이 0 이었으니까 는 그냥 일이나 왔지만

이제 i 값이 이를 넣어서 계산하며 는 이 해시 값 i 값을 이를 넣었을 때 나이 해시 값이 이젠 12 가 되겠죠

11 에다가 이래도 하니까 이런 제품은 일이니까 12 에 대해서 모듈 연산 10을 했더니 이번에는 일을 가리킵니다

근데 얘가 또 여기 있어요 그러면 또 충돌이 발생할 한 거죠 그러면 이제 어떻게 되냐 이에 제곱을 줘야 되는거 요금 11의 2 제곱 4 11 에다가 4를

더하면 뭐죠 15 입니다 15 를 10으로 모두 려 연설을 하면 뭐가 되죠 그래서 요기에 저장이 됩니다 올해는 우리 저장이 되는 거예요 이해가 되 시조

자, 바로 다음으로 넘어가겠습니다. 이 백을 해쉬 펌킨에 넣었더니 해쉬 값이 2가 나왔고, 10으로 모듈러 연산을 했더니 2가 나왔습니다.

여기죠. 근데 또 충돌이 발생했어요. 충돌이 발생했으면 일단은 충돌 횟수, 첫 번째로 가야 되겠죠. 다 그런 일에...

제곱은 1이고, 그러면 이 값의 의의를 다음에 3이 되고, 3에 대한 10으로의 모듈러 연산을 하면 3입니다. 비어 있죠.

그럼 여기다가 바로 넣으면 되는 거예요. 이 백을 넣겠습니다. 자, 좀 이해하기 편하게 이렇게 볼까요? 아까 506을 넣었을 때의 506...

을 넣었을 때에는 사실 맨 처음에 인덱스가 이를 가르쳤는데 없어서 여기 갔다가 없어서 물론 점프를 했다.

이렇게 됐고, 그 다음에 이제 200을 넣었을 때, 네, 여기 이 에서 충돌이 발생해서 그 다음 3으로 가서 넣었다.

자 이렇게 됐고 자 이제 다시 마지막으로 787 임프 서혜 슈팡 신의 넣었더니 22가 나왔어요 이해 식감이 11 힘으로 모듈 예언서 했더니 또 2가 나왔습니다

그러면 다시 또 충돌이 된 거죠 그러면 충돌을 발생했으니 이제 커 드레텍 포기는 방식으로 해보면

일단은 1회 제곱은 1이니까 22에다가 1회 더하면 23이 되고 23을 10으로 모듈러 연산을 하면 3입니다 3으로 갔어요 근데 3에 미백이 자리를 차고 있잖아요 그럼 다시 이에

제곱으로 해쉬 값을 더 해야 됩니다 그럼 예 제곱은 4고 22에 4를 더하면 얼마죠 26입니다 26을 모듈러 연산을 하면 은 유기적 욕까지 점토로 하게 되는 겁니다

해시맵의 해시 충돌 해결 방법 (hash map & hash collision 해결)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

해시 충돌 해결 방법을 설명한다.

해시 충돌 해결 방법은 체인 방식과 오픈 어드레싱 방식 두 가지로 나뉜다.

체인 방식은 추가적인 공간을 활용하여 충돌을 해결한다.

체인 방식의 대표적인 방법은 링크드 리스트를 사용하는 것이다.

오픈 어드레싱 방식은 추가적인 공간을 사용하지 않고, 비어있는 인접 공간을 활용한다.

해시맵의 내부 구현 방식과 예제에서 사용할 키-밸류 쌍의 특징을 설명한다.

링크드 리스트를 이용한 체인 방식으로 해시 충돌을 해결하는 과정을 예제를 통해 보여준다.

키 100, 921, 506 등을 순차적으로 해시맵에 추가하며 충돌 발생 시 링크드 리스트를 활용하는 방법을 설명한다.

충돌 발생 시 새로운 노드를 링크드 리스트의 헤드에 추가하는 이유를 설명한다.

체인 방식의 장단점을 간략하게 언급한다.

오픈 어드레싱 방식: 리니어 프로빙

오픈 어드레싱 방식의 개념과 리니어 프로빙 방식의 동작 원리를 설명한다.

리니어 프로빙은 충돌 발생 시 해시 값에 충돌 횟수(i)를 더하여 빈 공간을 찾는 방식이다.

리니어 프로빙 방식을 사용하여 키 100, 921, 506, 200, 787을 해시맵에 추가하는 과정을 예제로 보여준다.

리니어 프로빙 방식의 단점으로 클러스터링 현상을 지적한다.

오픈 어드레싱 방식: 쿼드래틱 프로빙

쿼드래틱 프로빙 방식은 해시 값에 충돌 횟수의 제곱을 더하여 빈 공간을 찾는 방식이다.

쿼드래틱 프로빙 방식을 사용하여 키 100, 921, 506, 200, 787을 해시맵에 추가하는 과정을 예제로 보여준다.

쿼드래틱 프로빙은 리니어 프로빙에 비해 클러스터링 현상이 덜 발생하고, 충돌 해결을 위한 이동 횟수가 상대적으로 적다.

오픈 어드레싱 방식: 더블 해싱

더블 해싱은 충돌 발생 시 다른 해시 함수를 사용하여 빈 공간을 찾는 방식이다.

더블 해싱은 동일한 해시 값을 생성하는 서로 다른 키 값의 문제를 해결한다.

더블 해싱에서 두 번째 해시 함수의 결과값은 해시맵의 크기와 서로소여야 한다.

오픈 어드레싱 방식의 주의점 및 삭제 처리

오픈 어드레싱에서 키 삭제 시 발생할 수 있는 문제점을 설명한다.

삭제된 키의 위치를 '삭제' 표시로 남겨 다음 탐색 시 확인하도록 하는 방법을 설명한다.

삭제 시 삭제 위치의 다음 키들을 앞으로 당겨 공간을 재활용하는 방법을 설명한다.

JDK 7까지는 링크드 리스트(체인 방식)를 사용했고, JDK 8부터는 링크드 리스트와 레드 블랙 트리를 혼용한다.

충돌 횟수가 임계치를 넘으면 링크드 리스트를 레드 블랙 트리로 변경하여 성능을 향상시킨다.

JDK 8의 변경으로 인해 해시 충돌 처리 성능이 향상되었다.