네이버 부스트캠프 베이직 미션#4

굉장한 미션이다 무려 난이도 상이다!

Map이나 Object 등 편하게 가져다쓰던 것들을 배열만 가지고 직접 구현해보는 미션이다.

 

먼저 Map과 HashMap의 차이를 공부해보았다.

자바스크립트 Object,Map,hashMap

한줄요약: HashMap이 좀 더 빠름. 그런데 HashMap은 처음 사이즈만큼 할당. Map은 그때그때 추가가능.

 

학부시절에 다 했던건데... 너무 오랫동안 손을 뗐나...

도무지 감이 안와서 구글링을 하여 자료를 좀 조사해보았다. 아래 블로그 글이 가장 도움이 많이 되었다.

[JS 자료구조] 해시 테이블(Hash Table)

이번 미션4와 내용이 거의 일치한다. 그래서 한번 눈으로만 정독하고 해시함수를 어떻게 만들지 힌트를 얻은 후 개발에 착수하기로 했다.

해쉬값이 충돌 시(키가 다른데 같은 해쉬값이 나왔을때) 문제점 해결방법

1. Separte Chaining(개별 체이닝): 그자리에 이중배열로 해서 넣는거지.

2. Linear Probing(선형 탐색법): 바로 뒤에 비어있는곳에 넣는다. 거기도 차있으면 또 그다음 뒤...

필자는 이 중 1번 방식을 택했다.

 

실수모음

배열이 아닌데 length 값을 얻으려하면 오류가 발생한다.

그리하여 아래와 같이 먼저 체크를 해준 후 반복문을 실행하게 수정하였다.

    	function containsKey(key){
          let hash = Hash(key);
          if (!map[hash]) {
              return false; // 해당 해시 버킷이 비어있다면 키가 존재하지 않음
          }
          for (let i = 0; i < map[hash].length; i++) {
              if (map[hash][i][0] === key) {
                  return true;
              }
          }
          return false;
      }
	

 

 

이전미션까지는 혼자서 해결했는데

이번 미션은 처음으로 거의 정답을 보고 한 것 과 마찬가지 수준으로 인터넷에서 정보를 많이 참고하고 공부하면서 진행했다.

그렇다고 그대로 베끼는 게 아닌 한번 정독을 한 후 구현단계에서는 스스로 삽질을 하며 코딩했기때문에 그래도 얻는게 많은 미션이었다.