해시

연관 배열 구조로 Key, Value가 1:1로 연결되어 있다.
Key를 이용해 Value를 알아낼 수 있다.

해시테이블 구성

• Key

  • 고유한 값, has function의 input값
  • Key 자체로 저장할 경우 Key의 길이가 다양하기에 일정한 길이의 Hash로 변경

• Hash function

  • Key를 일정한 길이의 hash로 변경해주는 함수로 이 과정을 hashing 이라 한다.
  • 서로 다른 Key가 같은 hash값을 갖게 되는 경우를 해시 충돌 이라고 한다.

• Value

  • 저장소(bucket, slot)에 최종적으로 저장되는 값
  • hash와 매칭되어 저장

• Hash table

  • 해시함수를 사용해 Key를 Hash값으로 매핑하고, Hash값으로 데이터를 찾는 자료구조
  • 기본 연산은 삽입, 삭제, 탐색이다.
  
  
  

해시테이블의 장단점

장점

Key, Value의 1:1 매칭으로 삽입, 삭제, 검색 과정에서 모두 O(1)의 시간복잡도를 가진다.

단점

Hash function이 복잡하다면 해시테이블의 연산 속도가 증가한다.

자바스크립트의 객체는 해시일까?

자바스크립트의 객체는 일반적으로 해시 테이블과 비슷한 방식으로 구현된다.
그러나 자바스크립트의 객체는 해시 테이블이라는 한 가지 자료구조만으로는 설명되지 않는 많은 특징들이 있으므로, 객체를 해시라고 부르기에는 비약이 있다.

그 이유에 대해서 알아보자

1. 객체의 다양한 속성 타입 처리 : 자바스크립트의 객체는 단순히 Key, Value로 구성된 것 이 아닌 함수와 메서드를 포함한 다양한 속성 타입을 지원하는 복잡한 자료구조다.

2. 충돌에 대한 처리 방식 차이 : 일반적인 해시 테이블에서는 충동 처리를 위해 연쇄적인 해시 테이블 또는 오픈 어드레싱 방식을 사용하지만 자바스크립트에서는 충돌 처리 방식이 구체적으로 명시되어 있지 않으며, 이는 속성을 다룰 때 예기치 않은 동작이 발생할 수 있는 가능성을 높인다.

따라서 자바스크립트의 객체 === 해시 보다 객체는 해시를 포함하는 개념이라고 하는 것이 맞을 것 같다.