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

<학습일기>

6-3. 빈번한 충돌을 개선하는 기법

 - 해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대

 - ex) 만약 슬롯이 8개일때, 50%이상에 데이터를 저장해야 한다면 2배의 슬롯을 정의한다.

  - hash_table = list([None for i in rangen(16)])

  - def hash_function(key):

        return key % 16:

*참고) 해쉬 함수와 키 생성 함수

- 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음

- 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해쉬 알고리즘)

 - 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

7. 시간 복잡도

- 일반적인 경우(Collision이 없는 경우)는 O(1)

- 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)

 - 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)이라고 말할 수 있음.

* 검색에서 해쉬 테이블의 사용 예

- 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)

- 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

 

 

---

<수강인증>

강의 수강

실습

 

---

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

https://bit.ly/37BpXiC

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

 

#패스트캠퍼스 #패캠챌린지 #직장인인강 #직장인자기계발 #패스트캠퍼스후기

#알고리즘기술면접완전정복올인원패키지Online