잠깐! 시작하기 전에

이 글은 wecode 사전 스터디에서 실제 공부하고, 이해한 내용들을 적는 글입니다. 글의 표현과는 달리 어쩌면 실무와는 전혀 상관이 없는 글일 수 있습니다.

또한 해당 글은 다양한 자료들과 작성자 지식이 합성된 글입니다. 따라서 원문의 포스팅들이 틀린 정보이거나, 해당 개념에 대한 작성자의 이해가 부족할 수 있습니다.

설명하듯 적는게 습관이라 권위자 발톱만큼의 향기가 조금은 날 수 있으나, 엄연히 학생입니다. 따라서 하나의 참고자료로 활용하시길 바랍니다.

글의 내용과 다른 정보나 견해의 차이가 있을 수 있습니다.
이럴 때, 해당 부분을 언급하셔서 제가 더 공부할 수 있는 기회를 제공해주시면 감사할 것 같습니다.

Object

드디어 기다리고 기다리던 그 시간이 와버렸습니다. 기본 자료형을 설명하는데에 이렇게나 오랜 시간이 걸릴줄 저는 몰랐네요.

나머지 7가지의 자료형은 상당히 원시적인 개념에 포함됩니다. 따라서 이러한 자료형들은 Primitive type이라고 불리게 되죠.

Primitive type은 오직 한 가지 종류의 data만을 담고 있을 수 있습니다. 그러나 Object는 아닙니다.

아래는 Primitive type의 종류입니다.

• Number : 수
• BigInt : 큰 수
• String : 문자열
• Boolean : 참, 거짓
• undifined : 정의되지 않음
• null : 비어있음
• symbol : 문자열 설명을 포함하고 있는 하나의 key, 기호

그럼 이제 Object에 대해 한 번 생각해봅시다.

Object 이해하기

(1). 구성

객체, Object는 보통 property라는 개념을 통해 구성됩니다.

그렇기에 우린 property가 무엇인지, 어떤 개념인지 우선적으로 알아보아야 합니다.

property는 상당히 중요하고, 공부할 양이 많아 따로 포스팅을 하나 더 하겠습니다.

(2). property( 'key' : value )

Object를 이해하고 넘어가려면 property의 형태에 대해 생각해보아야 합니다. 그리고 어떤 방식으로 자료를 저장하는지, 자료를 활용하는데 얼마나 효율적인지를 고민해봅시다.

먼저 간단한 data property를 생성하는 하나의 코드입니다.

const firstObject = {
  name : 'dongwu', // key : name, value : dongwu(string)
  age : 26 // key : age, value : 26(number)
}

위 코드를 보시면 무엇이 key이고, value인지 이해할 수 있게 됩니다. 또한 value의 값으로는 Js에 존재하는 모든 자료형을 사용할 수 있습니다.

이처럼 key와 value로 나누어 자료를 저장하는 개념의 명칭이 property 입니다.

그렇다면 왜 이런 방법으로 자료를 저장해야만 할까요?

(3). Object - Data structure

Object가 property를 사용하는 이유를 이해하려면 자료를 저장하는 구조에 대해서 알아야 합니다.

이를 통해 새로 등장할 개념인 Hash table을 알아봅시다.

Hash table은 자료를 저장하는 구조이고, 여러분들이 알고 있는 배열, Array 또한 자료를 보관하고 있는 하나의 구조로 볼 수 있습니다.

비유하자면 자료를 꽂는 책꽂이 정도가 됩니다.

또한 Hash table을 이해하기 위해서는 다양한 개념들을 짚고 넘어가야만 합니다.

현재 챕터에서 다룰 얘기는 다음과 같습니다.

• Hash table 구조
• Time complexity(시간복잡도)
• Hash function
• 단점

Hash table 구조 ( 이미지의 출처는 글 하단에 있습니다. )

그림을 보면 익숙한 개념들이 눈에 들어오게 됩니다. 바로 key와 value가 있네요.

우리가 이해하려는 Object의 경우 key와 value를 통해 prop, property를 만들어냅니다. (제 글의 props는 properties입니다.)

하나의 Object 내의 props를 쭉 나열해서 본다면 위 그림과 같은 구조를 이루고 있지 않을까 하는 생각이 들지 않나요?

그리고 그림에서 나오는 000, 001, 151, 254 이것들은 무엇을 의미할까요? 그런 것들을 이제 생각해봅시다.

또한 이후 나올 내용을 이해하기 위해서는 Time Complexity라는 개념이 필요하게 됩니다.

시간복잡도 (Time Complexity)

우리가 data를 다루는데에 있어 가장 근본적인 접근은 CRUD 임을 기억해야 합니다.

생성하고, 읽고, 수정하고, 삭제하는 것이죠. 물론 이외에도 ABCD, ACID, 등과 같은 약어도 존재합니다만, 모두 일맥상통합니다.
Data structure의 평가지표인 Search, Insert, Delete 또한 따지고 보면 CRUD에 해당하는 기능을 다른 말로 표현한다고 볼 수 있습니다. 궁금하신 분은 아래 글을 읽어보시면 됩니다.

참고자료 : CRUD란 무엇일까?

이에 특정 자료구조, Data structure를 이용한 CRUD 처리과정 사이에 걸리는 시간을 적어도 개발자는 인지하고 있어야 합니다.

그러나 특정 자료구조에서의 컴퓨터 연산 속도를 s, ms 단위로 기록하는 것은 상당히 비효율적이겠죠.

심지어 하드웨어의 성능과 프로그래밍 언어별로 속도의 차이를 가지기에 기준을 특정 기기와 언어에서의 측정값으로 두는 것은 올바르지 않습니다.

그래서 나온 개념이 시간복잡도, Time Complexity 입니다.

시간복잡도는 하나의 입력이 사용자 원하는 출력, 문제의 해결(PS)까지 거치는 연산과정의 step을 의미합니다. 결코 시간값이 아닙니다.

연산과정이라 함은 다양한 연산자, 또는 함수 혹은 메서드를 거치거나, 기본 수리연산 및 대입이 될 수 있습니다.

중요한 점은 과정의 설계에 따라 시간복잡도 지표가 변화한다는 것을 알고 있어야 합니다.

시간복잡도에 대해 아주 좋은 글을 발견했습니다. 해당 글을 첨부할테니 한 번 읽어보시는 것도 충분히 좋다고 생각합니다.
Big-O, 시간복잡도는 무엇을 의미할까?

그럼 Time complexity와 다음 주제인 Hash function을 통해 Hash table을 좀 더 알아보도록 하겠습니다.

Hash function ( 이미지의 출처는 글 하단에 있습니다. )

예시로 다른 자료를 가져오도록 하겠습니다.

해당 그림에서 우리는 John Smith 라는 key와 '521-1234' value를 저장하고자 합니다. 이는 CRUD에서 C에 해당하는 과정입니다.

자료구조 Big-O 평가에 Create는 대부분 존재하지 않습니다.
그러나 Hash table의 경우 자료 생성 자체에 의미를 부여하고 싶어 개인적으로 추가한 내용입니다. (기존 항목 Search, Insert, Delete)

const obj = { John Smith : '555-1234' } 라는 코드를 입력했을 때, Hash table 방식은 key에 대해 단 한번의 연산(Hash function)을 취합니다.

key 값을 Hash function의 전달인자로 사용하는 것이죠. 이를 통해 Hash table 내에 존재하는 buckets의 index를 결정할수가 있습니다.

또한 해당 index에는 key와 value의 값을 저장하게 됩니다.

index는 배열에서 사용하는 고유한 number입니다.
buckets의 경우 배열구조로 자료를 저장하고, 해당 index를 key로 생성하여 사용하게 됩니다.
즉, 주소의 역할을 하는 숫자로 이해할 수 있습니다.

Hash function의 종류는 다양하고, 사용자의 의지로 이 함수를 변경할수도 있습니다. 예를 들어 prop의 수, 테이블의 길이로 key에 대한 나눗셈 연산을 진행할수도 있습니다.

이를 Division Method 라고 합니다.
나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산합니다.(index = key % 테이블 길이)
테이블의 크기를 소수로 정하고, 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있습니다.

또는 배포된 Hash function을 사용해도 무관합니다. 대표적인 예로는 MD5 Hash generator가 있습니다.

이외에도 다양한 function이 존재합니다만, 종류별로 설명하지는 않겠습니다.

제가 생각하는 공부는 암기방식의 공부가 아니니, 하단부 출처를 통해 글을 읽어보시면 될 것 같습니다.

중요한 것은 Hash table에서 자료를 저장, 보관, Create(Initialization) 할 때 단 한 번의 Hash function 만을 거친다는 점입니다.

또한 저장 방식에서 배열구조와 흡사하게 index를 활용한다는 것은 Read(자료구조 기준 Search)과정에서 속도가 굉장히 빠르다는 장점을 가지게 됩니다.

index를 활용한 배열 내 element search의 경우 해당 요소에 즉각적으로 접근이 가능합니다.
배열에 대하여 : Nomad Coders
index를 모를 때 배열의 Search 속도는...

이를 설명해주는 것이 바로 Time complexity, 시간복잡도입니다.

해당 과정에서 Hash table은 평균 O(1)의 시간복잡도를 갖습니다. 이 때, 1은 연산의 step 수를 의미하고, O는 Big-O 지표를 의미합니다.

실제 Big-O 표기에서는 상수항을 무시하지만, 입력과 무관하게 절대적인 step만을 가지는 경우 Constant로 표현합니다.

즉, 어떠한 입력을 가지더라도 Hash table은 문제해결(CRUD or SID)에 평균적으로 한 번의 Hash function 연산만을 요구한다는 뜻이 됩니다.

Hash function의 특징

1. 해당 자료의 보안을 담당합니다.

   단방향 : 임의로 생성된 output만을 보고 input을 예상할 수 없게 해주는 특성을 가지고 있습니다.

2. 동일한 Hash function을 사용하는 경우

   idempotent : input인 key가 동일하면 output은 언제나 동일합니다.

   예를 들어 '김동우' 라는 input이 MD5 generator를 거치면 불변의 값인
   '8d49285f744f2a2b71fd24593d49fe18' 인 output을 생성합니다.

단점?

이렇게 좋은 Hash Table만을 사용하지 않는 이유이며, 이번 글의 마지막이 될 것 같습니다.

단점은 여러가지가 있겠지만, 가장 큰 단점이 존재합니다.

Hash table의 장점인 O(1)의 시간복잡도가 늘 언제나 그렇지는 않다는 점이죠.

다시 처음의 그림을 가져오겠습니다.

해당 그림에서 볼 경우 John Smith와 Sandra Dee의 경우 같은 Hash값을 가지게 되고, 이에 한 메모리 주소에서 두 Data를 관리하게 됩니다.

이럴 경우 Hash 충돌이라는 표현을 사용하는데, 충돌의 가장 큰 문제는 시간복잡도가 변한다는 점에 있습니다.

Hash table의 가장 큰 장점인 시간복잡도가 오히려 퇴색되고 마는 것이죠.

동일한 Hash 주소를 보유한 keys에 해당하는 시간복잡도는 O(n/k), k는 테이블의 길이(buckets 요소들의 수), 상수항 k를 무시하면 O(n)이 되어버립니다.

O(n)의 시간복잡도는 입력에 영향을 받는 선형 시간복잡도로 이해할 수 있으며, 입력에 대해 단일 for문을 통한 연산의 결과를 출력할 경우 O(n)의 시간복잡도를 가집니다.

따라서 이해를 위해 내부적으로 배열을 형성한다고는 했으나, 배열과 가장 큰 차이점이 되는 점이 바로 이 부분입니다.

배열의 경우 하나의 배열이 차지하는 메모리의 주소를 나열해보면 배열의 구조와 동일한 stack의 형태가 됩니다. 열차와 같이 요소들끼리의 메모리 주소가 붙어있음을 알 수 있죠.

이러한 경우 메모리의 할당은 요소(element)별로 이루어져있어 메모리 충돌을 야기하지는 않습니다.

물론 그럼에도 인덱스를 활용하지 않는 배열의 Search(R), Insert(U), Delete(D)는 최악에 가까운 시간복잡도를 자랑합니다.

이러한 단점을 극복하는 방법에 대해서는 다양하게 존재합니다. 이에 링크를 첨부하겠습니다.

seperate chaining

그럼 이번 글은 여기서 마치도록 하겠습니다.

참고자료

Hash table -1- Object 자료형 참고
Hash table -2- Object 자료형 참고
Js Object
Big O
Big O 2
MD5
separate chaining