[바미] Obejct와 Map의 시간복잡도는 항상 O(1)일까? (feat. JS & Node)

들어가기전에..

회사에서 진행하고 있는 프로젝트 내에서 Front 또는 클라이언트로 부터 query 또는 body로부터 파라미터를 받아오게 되는데 이에 따라 Validation 검사 처리를 개발하고 있던 중이였습니다.

 

그 파라미터를 체크하는 로직은 아래와 같은데

const locations = ['body', 'query'];
const params = req[location];

Object.keys(params).forEach(key => {
  const rule = validation[key];
...
}

validation이라는 Object안에 Validation체크를 할 수 있도록 만들고,  Validation 체크 조건에 걸리면 router단에서 API를 종료시키는 구조로 구현했는데 이 중에서 const rule = validation[key];에서 가져오는 데이터는 항상 O(1)의 시간 복잡도 만큼 가지고 올까? 라는 의문과 함께 '항상  HashMap은 O(1)의 시간복잡도로 데이터를 가져올까?'라는 의문이 들어 찾아본 내용을 정리하고자 합니다.

 

---

도입부

아시다시피 JavaScript 또는 Node.js에서의 HashMap과 비슷한 자료 구조는 Object 또는 Map입니다.

일반적으로 해시맵(HashMap)의 주요 작업(검색, 삽입, 삭제)의 평균 시간 복잡도는 O(1)입니다. 이는 키를 해시 함수로 변환하여 바로 데이터를 찾기 때문이죠.

 

하지만 이러한 자료 구조에서의 시간 복잡도는 특정 조건에 따라 달라질 수 있다는 것을 알게 되었습니다.

---

Object

Object는 키-값 쌍을 저장하는 구조로, 키는 기본적으로 문자열이나 Symbol입니다. 키 검색, 삽입, 삭제는 해시 테이블처럼 평균적으로 O(1) 시간이 걸리게 되죠.

 

하지만 키가 충돌하는 경우(같은 해시값을 가지는 경우) 성능이 저하 될 수 있는데 이러한 충돌이 발생하게 될 때 최악의 경우 O(n) 시간이 걸릴 수 있게 됩니다.

Map

Map은 ES6에서 도입되었고, 모든 종류의 값을 키로 사용할 수 있다는 특징이 있습니다.

물론 Map도 내부적으로 해시 테이블을 사용하기 때문에 평균적으로 O(1) 시간이 걸리게 됩니다만, Object와 마찬가지로 해시 충돌이 빈번하게 발생하게 되면 Map 역시 O(N)의 시간 복잡도가 걸리게 됩니다.

 

따라서 해시 충돌이나 해시 테이블의 내부 구조에 따라 성능이 달라지기 때문에 항상 O(1)의 시간복잡도를 갖지 않다는 것이죠.

---

해시 충돌은 무엇인가?

해시 충돌(hash collision)은 해시 함수가 다른 입력값에 대해 같은 해시 값을 생성할 때 발생하는 상황을 말합니다.

 

여기서 해시 함수는 데이터를 일정한 크기의 값으로 변환하는 함수입니다.  해시 함수는 보통 아주 큰 데이터나 여러 다른 데이터를 고정된 크기의 숫자나 문자열로 바꿔주는 역할을 하죠.

 

예를 들어, "apple", "banana", "carrot" 같은 문자열이 있을 때, 이 문자열들을 숫자로 변환해서 해시 테이블의 인덱스로 사용하려고 한다고 가정해볼게요.

• apple의 해시 함수 결과(해시 값)은 123.
• banana의 해시 함수 결과(해시 값)은 456.
• carrot의 해시 함수 결과(해시 값)은 789.

이렇게 문자열이 숫자로 변환되면, 이 숫자를 배열의 인덱스처럼 사용하기 때문에 O(1)의 시간 복잡도를 갖게 되는 것인데요.

 

문제는 해시 함수가 항상 다른 입력값에 대해 서로 다른 해시 값을 반환하는 것이 아니라는 데 있어요.

 

해시 함수는 유한한 크기의 해시 값을 반환해요(32비트 정수라면 최대 4,294,967,295개의 서로 다른 해시 값만 가능). 하지만 입력값(문자열, 숫자 등)은 이론적으로 무한할 수 있기 때문에 두 개의 서로 다른 입력값이 같은 해시 값을 반환할 수도 있는 것이죠.

이런 상황을 해시 충돌이라고 합니다.

---

결론

JavaScript에서 Object와 Map을 해시맵처럼 사용할 때, 내부 해시 키가 충돌하지 않는다면 일반적으로 O(1) 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있다는 것을 알았습니다.

하지만 해시 충돌이 발생하면, 그 충돌을 처리하는 방식에 따라 최악의 경우 O(n) 시간이 걸릴 수 있다는 점을 기억해야 하죠.

따라서 Object나 Map의 사용 시 평균적으로는 O(1) 성능을 기대할 수 있지만 항상 O(1) 시간이 보장되는 것은 아니였다는 것을 알게 되었습니다.

같이 보면 좋은 글

[바미] 해시 충돌 처리 방법