Javascript
Javascript에서 객체와 해시테이블?
kauboy
2020. 9. 25. 23:03
javascript에서 객체는 해시테이블이라는 자료구조이다.
그래서 javascript의 객체가 해시로 작용되었던 것이다.
해시 테이블이란?
이제 key를 인풋할 때 hash function이 메모리 주소를 부여해줘 buckets으로 바로 집어넣어 준다고 한다.
key와 value 값이 주어져
const obj = {'key' : 'value'}아래 obj의 속성은 key 속성값은 value이다
또한 javascript에서 객체의 속성값은 무엇이든 상관이 없다고 한다. 문자, 숫자, 객체 모든 것이 들어갈 수 있다고 한다.
또한 이렇게 시간복잡도 O(1) 이면 이거 쓰지 왜 다른거 쓰냐 하는 말이 있는데, 그 이유는 해시 충돌때문에 효율성이 떨어지기 때문이라고 한다.
이러한 해싱충돌을 다양한 방법으로 해결하지만 완벽한 O(1)은 나오지 않는다고 한다.
- chaining 기법
- open address 기법
- 선형 탐사
- 제곱 탐사
- 이중 해싱
출처: https://dailyheumsi.tistory.com/75 [하나씩 점을 찍어 나가며]
위의 obj가 어떻게 해시테이블에 저장이 되냐
key 값이 해시 테이블의 index로 해싱이 되어 그 자리에 value값이 들어간다.
A라는 배열이 있다고 치자 A[1] 몇번째 인덱스 값을 찾는지 알면 O(1)이 가능하다.
obj에서도 key값이 숫자로 해싱되어 해시테이블에서 O(1)로 작동한다고 생각하면 된다.