알고리즘 +11

해쉬 테이블

시간 복잡도 O(1)

같은 해쉬에 중첩될 경우 (collison) 이라고 부르는 이 경우가

많을 경우 최대 시간 복잡도가 O(n) 까지 증가할 수 있다

해결 방법 : 하나의 배열을 또 만들어서 둘 다 저장함, 이땐 선형 검색 O(n)

항상 O(1)의 시간복잡도를 가진건 아니지만 일반적인 기준을 생각했을 때

시간복잡도는 O(1) 이라고 할 수 있음

좋은 해쉬 코드

해쉬 함수의 알고리즘은 입력 받은 키를 가지고
얼마나 골고루 잘 분배를 하냐에 따라 결정이 된다.

즉 중첩되는 경우가 얼마나 적은지에 따라에 나뉜다.

충돌(collison)

때로 서로 다른 키 값으로 동일한 해쉬 코드를 만들어 내기도 한다.

키 값은 문자열에 그 가지 수가 무한이지만

해쉬 코드는 정수개 밖에 제공을 못하기 때문이다.

또 해쉬 코드는 다른데 인덱스로 환산을 할 때 같은 배열에 들어갈 경우.

Linked List

충돌이 생기는 경우를 대비해서 배열에 바로 저장하는 것이 아니고

배열 안에 Linked List 를 선언하고 데이터가 배열에 할당 될 때 마다

데이터를 추가한다.

그리고 검색 요청이 들어왔을때마다 검색할 키를 해쉬함수를 통해서 해쉬 코드로 만들고 ,

인덱스로 환산해서 해당 배열의 리스트를 돌면서 내가 찾는 데이터를 가져오는 것이다.

보고 정리한 영상

너무 좋은 영상이라 올려두지만 문제 시 삭제하겠습니다 !!_!!

느낀 점

문제 수로 때려박는건 그 알고리즘을 이해하고
어떻게 쓰는지를 알고 난 뒤인거 같다.