728x90

여러 이름으로 불리는 Hash 관련 자료구조에 대해 잘 정리해놓은 블로그를 찾아서 이렇게 포스팅한다.

Hash Example

학부때 배웠던 Hash Table에 대한 기억을 끄집어 내고자 검색을 하였고, 
지금 메인으로 사용하는 JavaScript를 더욱 잘 이해하기 위해 아래 내용을 학습하면 더 좋을 것 같았다.

즉, JavaScript의 Object( {} )를 해쉬라고 보면 된다.
key와 value로 구성되어 있어서 찾을 key를 모른다면 순차적으로 검색하는 O(n) 시간복잡도가 되지만,
key를 미리 안다면 바로 직접 item에 접근할 수 있는 O(1)의 빠른 시간복잡도를 갖는 다는게 장점이다.

JavaScript에서는 fibonacci 알고리즘을 풀면서 사용해봤다.
그냥 반복문을 돌려서 문제를 풀 수도 있지만, 매우 큰 수는 시간이 오래 걸리기 때문에 시간 복잡도 때문에 캐시를 사용하면 좋다.
따라서 fibonacci를 풀기 위해 재귀함수를 사용하였고, 재귀를 사용할 때마다 계산하여 나온 결과를 cache object에 저장하였다.
그리고 해당 값이 cache에 존재한다면 값을 다시 계산하지 않고 cache에서 가져다 쓸 수 있게 작성하였다.
이 방법은 크게 다이나믹 프로그래밍(Dynamic Programing)이라고 부르며, 정확하게는 memoize라고 부른다.

👍 출처 https://jwo0816.blog.me/221457342364

 

[알고리즘 끄적끄적 04] Hasing / Hash Table / 해싱 / 해시 테이블

Hashing / Hash Table​해시 테이블 (Hash table) 이란, [키(Key)와 값(Value)]이 하나의 쌍을 이루...

blog.naver.com

 

+ Recent posts