[알고리즘] 패스트캠퍼스 챌린지 09일차

해쉬테이블 충돌 해결 알고리즘

[Chaining 기법]

• 개방 해슁 또는 Open Hashing 기법 중 하나
• 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

[Linear Probing 기법]

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나
• 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

빈번한 충돌을 개선하는 방법

• 해쉬 함수을 재정의 및 해쉬 테이블 저장공간을 확대
  • ex. 이전 예제에서 hash Func = key % 8 으로 hashMap의 공간의 8칸이었다면, hash Func = key % 16으로 공간을 늘려준다. hashKey가 충돌될 가능성을 줄여줌 > 탐색 시간이 줄어든다!

• 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
  • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능
  • SHA-1 / SHA-256

대박
일할때 앱 로그인 인증키 관련 로직에서 SHA-256 본적있었다.
이렇게 보니 반갑군

시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n) >> 각 hash Key에 저장된 데이터들을 탐색해야하는 경우.

=> 그렇지만 보통 일반적이 경우를 기대하고 해쉬테이블을 구성하기 때문에 시간복잡도는 일반적으로 O(1)이다.

[결론]
원하는 Key -> Hash 함수 -> 해당하는 Hash Key의 Value 리턴 >> O(1)
배열보다 빠르고 좋다.

지금 여기에 정리하면서 강의 봤다.

어제에 이어서 해쉬테이블 내용이 이어짐
해쉬 테이블의 단점 중 "충돌"이 발생할 수 있다는 것이었고, 이를 방지하기 위한 코드가 필요하다.
이를 위한 알고리즘이 어떤게 있는지 공부하는 강의였다.

이해하는데 조금 어려움이 있었다. 강의 반복하고 반복해서 들으면서 내용 이해하느라 조금 시간이 걸렸다!!
사실 아직도 잘 모르겟다
이해했지만 잘 모르겠는 기분... 나중에도 강의 다시 돌려보고 정리한 글도 보고.. 다른 멋진 자료들도 참고 많이 하면서 공부해야겠다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.