인프런 워밍업 클럽 3기 CS - 1주차 발자국

최동철 7개월 전

안녕하세요. 저는 3년차 Node.js 백엔드 개발자입니다. 벌써 1주차가 지나가고 있네요... 그동안 걸어온 발자국을 남겨보고자 글을 적게 되었습니다.

클럽을 시작한 계기

부끄럽지만 저는 기본기가 부족한 개발자였습니다. 연차가 쌓여가면서 현업의 다양한 문제를 해결할 때 마다 CS지식의 중요성을 뼈저리게 느끼게 되었고 최근에 동시성에 대해 공부하면서 단순히 구현만 할 수 있는 개발자를 넘어 그 안의 원리를 이해하는 것이 필요하다는 것을 절실하게 느끼게 되었습니다. 그러던 중 인프런에서 주최하는 워밍업 클럽이라는 좋은 프로그램을 접하게 되었고 고민없이 바로 신청하게 되었습니다.

학습 회고

제가 배운 지식들은 다음과 같습니다.

자료구조와 알고리즘에서는 시간복잡도, 배열, 연결리스트, 스택, 큐, 덱, 해시테이블, 셋을 배우게 되었습니다. 자료구조와 알고리즘은 밀접한 관계를 가진다는 것을 알게 되었습니다. 그리고 추상적으로 개념만 알고 있던 내용들을 직접 구현하면서 원리를 이해할 수 있어서 자료구조를 선택할 때 더 나은 결정을 할 수 있게 될거 같습니다.

운영체제에서는 운영체제의 역사, 구조, 하드웨어 구조, 부팅 과정, 인터럽트, 프로그램과 프로세스, 컴파일 과정, CPU 동작 과정, 유니프로그래밍, 멀티프로그래밍, 멀티태스킹, 멀티프로세서, 멀티프로세싱, PCB(Process Control Block), 컨텍스트 스위칭, 프로세스 생성과 종료, 쓰레드, CPU 스케줄링을 배우게 되었습니다. 사실 운영체제가 정말 저에게 필요한 과정이였습니다. 부분적으로 알고있거나 잘 모르고 지나가던 시스템의 내부 동작에 대해 명확하게 이해할 수 있었습니다.

칭찬하고 싶은 점

1주차의 강의와 과제를 밀리지 않고 해냈다는 점 자체를 칭찬하고 싶습니다. 또한 저는 눈으로 강의를 보면서 손으로 필기하고 귀로 목소리를 들으면서 좀 더 학습의 효율을 올리려고 하고 있습니다. 이해가 되지 않는 부분은 이해가 될 때 까지 추가적으로 AI로 자료를 찾아보면서 이해하려고 하였습니다.

아쉬웠던 점

아무래도 직장을 다니면서 남는 시간에 학습해야 했기 때문에 상대적으로 시간이 부족했습니다. 특히 이번주는 일정이 많아 시간을 내기 어려워서 한번에 들을 수 밖에 없었습니다. 일별로 들을 범위가 정해진 것은 복습을 통해 좀 더 내용을 이해할 수 있도록 가이드하는 것인데 그 부분을 챙기지 못했습니다. 그 부분이 아쉽습니다.

보완하고 싶은 점

이번 워밍업 클럽의 우선순위를 높여서 시간을 내서 강의를 들어야 할 거 같습니다. 다음주부터는 알고리즘과 프로세스 동기화, 데드락, 메모리에 대해서 학습하게 되는데 이 내용들이 다 난이도가 있어서 좀 더 시간을 내고자 해야할 것으로 보입니다.

다음주 목표

벌써 다음주가 기대가 됩니다...! 그냥 추상적으로만 알고 넘어갔던 동시성에 대한 문제를 다루는 것으로 보입니다. 단순히 구현만 할 수 있는 개발자를 넘어서 그 원리까지 이해할 수 있는 개발자가 되고자 좀 더 학습에 몰두하는 것이 목표입니다.

미션 해결과정

우선 운영체제의 경우 강의에 나온 내용들을 이해했다면 충분히 답을 할 수 있는 질문이였다고 생각합니다. 따라서 운영체제는 언급하지 않고 자료구조와 알고리즘의 미션에 대해서만 이야기 하도록 하겠습니다.

 

  1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.

    우선 학생 정보가 어떤 특징을 가지고 있는지에 대해 고민하였습니다. 학생 정보는 출석번호를 통해 접근하고 그 안의 데이터는 읽기, 삽입 삭제의 성능이 어느정도 준수해야 한다고 생각했습니다. 다른 자료구조로 구현을 하게 되면 학생의 정보가 많아지게 되는 경우 전학을 가거나 오게 되는 경우 O(n)의 성능을 가지게 되고 이는 성능상 문제가 된다고 생각하였습니다. 따라서 공간을 많이 사용한다는 단점을 감수하고 해시테이블을 선택하게 되었습니다.

  2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.

    주문이 들어온 순서대로 처리가 된다는 부분에 좀 더 집중하였습니다. 그리고 이런 요구사항을 쉽게 구현할 수 있는 자료구조는 큐라고 생각하였습니다. 큐에 처리해야하는 주문 데이터가 들어오면 주문 순서에 따라 순차적으로 처리가 될 것으로 예상했습니다.

  3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.

    이 부분은 우리가 강의 시간에 배운 양방향 연결리스트를 통해 해결할 수 있다고 생각하였습니다. 맨 처음에 데이터를 입력하게 되는 경우 첫 데이터가 head가 되고 계속 데이터를 입력하게 되면 해당 부분이 tail이 되도록 수정하였습니다. 그렇게 수정을 하게 난 후 테스트 결과 정상 동작하는 것을 확인하였습니다.

  4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력



    문제의 힌트를 참고하여 구현하게 되었습니다. return name.charCodeAt(0) % 10; 이렇게 구현하였습니다. 문자열의 첫 문자의 유니코드를 가져와 그 값을 나눈 나머지를 사용해서 해시 테이블을 구현하는 방식입니다. 하지만 이 방식이 과연 데이터를 골고루 분산을 시키는 코드인지에 대한 의문이 있었습니다. 그래서 실제로는 어떻게 구현을 했을까에 대한 의문점이 생겼습니다. 저는 Node.js를 사용하는 개발자이기에 JS의 Map 자료구조의 특성에 대해 좀 더 조사하게 되었습니다.

Node.js에서의 Map 자료구조의 해시함수 알고리즘

Node.js는 V8 엔진을 기반으로 실행되므로, Node.js에서 Map 자료구조의 해시 함수는 V8 엔진 내부에서 관리되며, Map의 내부 해싱은 V8 엔진의 OrderedHashMap 구현을 따릅니다.

이때 string인지 number인지 object인지에 따라 내부 처리가 다르게 동작합니다. 하나 하나씩 보도록 하겠습니다.

string일 경우

문자열을 키로 사용할 경우, V8은 OneByteStringHasher (ASCII) 또는 TwoByteStringHasher(유니코드) 를 사용하여 해시 값을 계산합니다.

해싱 과정은 문자열을 특정 숫자로 변환(해싱)하고 해시 값을 버킷 인덱스로 변환하여 충돌이 발생하면 체이닝(chaining) 방식 사용합니다.

V8 내부 코드에서 문자열 해싱은 MurmurHash2/3 기반으로 최적화된 버전을 사용합니다.

uint32_t StringHasher::HashSequentialString(const uint8_t* chars, int length, uint32_t seed) {
  uint32_t hash = seed;
  for (int i = 0; i < length; i++) {
    hash = 31 * hash + chars[i]; // 해시 충돌 방지를 위한 가중치 적용
  }
  return hash;
}

number인 경우

이 경우는 크게 두가지로 나뉩니다.

  1. 정수(int32 범위) 키는 그 자체로 해시 값으로 사용됩니다.

  2. 64비트 부동소수점(double) 숫자는 비트 패턴을 XOR 연산하여 32비트 해시 값 생성합니다.

uint32_t NumberToHash(double num) {
  if (num == 0) return 0;
  uint64_t bits = bit_cast<uint64_t>(num); // 비트 변환
  return static_cast<uint32_t>(bits ^ (bits >> 32)); // 상위 비트와 XOR
}

object인 경우

객체를 Map의 키로 사용할 경우, 객체의 메모리 주소를 기반으로 해싱이 이루어집니다. V8 엔진은 객체마다 숨겨진 ID(hidden identity hash) 를 생성하고 이 ID는 객체가 처음 Map의 키로 사용될 때 할당됩니다. 이때 객체가 이동(가비지 컬렉션 등)해도 변하지 않습니다.

객체 해싱 과정은 객체가 처음으로 Map의 키로 사용될 때 V8은 객체에 Hidden Symbol을 할당합니다. 해당 심볼을 기반으로 해시 값을 생성하고 메모리 주소 기반으로 ID를 생성하지만, 가비지 컬렉션이 일어나도 유지되도록 관리합니다.

uint32_t Object::GetOrCreateIdentityHash(Isolate* isolate) {
  if (!HasIdentityHash()) {
    uint32_t hash = GenerateRandomHash(); // 해시 값 생성
    SetIdentityHash(hash);
  }
  return identity_hash_;
}

이상입니다. 지금까지 긴 글을 읽어주셔서 감사합니다.

댓글을 작성해보세요.

채널톡 아이콘