패스트캠퍼스 챌린지 7일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

1월 30일 오늘의 강의

해쉬 테이블 충돌 개선 방법

일반적으로는 해쉬 함수를 재정의하고 해쉬 테이블의 저장공간을 확대해서 충돌을 개선한다.

 

해쉬 함수와 키 생성 함수

기존에 구현했었던 파이썬의 hash() 함수는 실행할 때마다 값이 달라지기 때문에 통일성을 갖기가 어려웠다. 그래서 데이터에 유일한 값으로 변환시키기 위해서 해쉬 함수 중 유명한 함수인 SHA(Secure Hash Algotithm, 안전한 해시 알고리즘)를 사용했다.

 

SHA는 어떠한 데이터라도 유일한 고정된 크기의 고정 값을 리턴해주기 때문에 해쉬 함수로써 유용하게 활용할 수 있다. 특히, 눈사태 효과로 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력해준다. 물론 아주 희박한 경우로 같은 결과 값이 나올 수 있다고 하며, 이럴 경우 충돌이라 표현하고 이러한 충돌이 적은 해쉬 함수일 수록 좋은 해쉬 함수라고 한다.

 

실습 결과

 

실습은 해쉬 함수 SHA-1와 Linear Probing 기법을 사용해서 진행했다. 실제로 데이터들은 해쉬 함수를 통해 고유 값으로 변환되어 idx 키로 적용했고, 각 값에 따라 리스트에 저장된 것을 확인할 수 있다.

 

해쉬 테이블의 시간 복잡도

해쉬 테이블의 경우 일반적으로는 O(1)이 소요되는데 저장되는 값이 계속 충돌되는 최악의 경우에는 O(N)이 소요된다. 하지만 이러한 해쉬 테이블의 경우 일반적인 경우를 기대하고 만들기에 시간 복잡도는 O(1)로 표현할 수 있다고 한다.

이와 반면에 배열에서는 데이터를 저장하고 검색하는 과정에서 첫 인덱스부터 시작되기 때문에 O(N)이 발생한다.

 

https://bit.ly/37BpXiC

 

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

 

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