[TIL] 230522 - Hash 해시에 대해

 

해시

 

🙋‍♂️관련 문제

in 프로그래머스 

 

완주하지 못한 선수🔥

전화번호 목록🔥🔥

베스트 앨범🔥🔥🔥

 

 

 

 

처음에 인덱스로 풀다가 시간 복잡도에서 시간초과했다.

해시로 풀어야 하는것을 알게 되었다.

 

 

dict 형태로 저장해놓으면 값을 서치할때 빠르게 찾고 비교할 수 있다.

특히 두가지 list 값들을 비교할 때는 O(n^2)이 걸리기 때문에 → a list i개, b list j개 → i*j번 연산

 

 

 

 

 

Q. dictionary가 왜 인덱스보다 빠른지?

1. 검색 속도: 딕셔너리는 해시 테이블을 사용하여 키를 해시 함수로 변환하고 해당 키의 값을 검색합니다. 이 과정은 평균적으로 O(1)의 시간 복잡도를 가지며, 매우 빠른 검색 속도를 제공합니다. 반면에 인덱스를 사용하는 경우, 리스트나 배열을 순차적으로 탐색해야 하므로 O(n)의 시간 복잡도를 가집니다.
2. 유연성: 딕셔너리는 키-값 쌍을 저장하므로, 특정 키를 사용하여 값을 쉽게 검색하거나 수정할 수 있습니다. 이는 인덱스를 사용하는 경우보다 데이터에 접근하는 데 더 편리하고 직관적인 방식을 제공합니다.
3. 데이터 구조: 딕셔너리는 순차적인 인덱스와 달리 키-값 쌍을 저장하므로, 데이터를 보다 의미 있는 방식으로 구조화할 수 있습니다. 이는 코드의 가독성을 높이고 데이터를 조작하는 데 편리성을 제공합니다.

 

 

인덱스는 순차적이라서 O(n)

해시 테이블은 key-value쌍이라서 O(1)

 

 

사전을 찾을 때 인덱스가 책 한장씩 넘기는 것이라면

해시는 ㄱㄴㄷ 목차를 통해 빠르게 찾을 수 있는 것이다.

 

 

 

 

 

cf.

#해시태그

#해시태그가 정확히 무엇인가요? 해시태그 A to Z | 요즘IT (wishket.com)