TIL_200505(화)- HashTable resize 구현 마지막, socrative 문제 복습

hashtable 구현

어제 hashtable을 구현하는데 그중 _resize 함수를 구현하는 것에 막혀서 더 진행을 못했었다. 그래서 오늘 한 번 작성해 보는 시간을 가졌다.

1. bucket과 tuple을 array 형태로 다시 만들고

2. _insert 함수와 _remove함수에 각각
   사이즈에 따라 _resize함수를 실행시키는 코드를 작성

3. 코드는 아래와 같이 작성했다.

_resize(newLimit) {
    const originStorage =  this._storage;
    
    this._limit = newLimit;
    this._storage = LimitedArray(this._limit);
    this._size = 0;

    for(let i = 0; i < originStorage.length; i++){
       for(let j = 0; j < originStorage[i].length; j++){
         let tuple = originStorage[i][j];
         this.insert(tuple[0], tuple[1]);
       }
    }
}

그러나 resize를 통해 계속 해싱을 못하는 상태가 발생했고, test 통과를 하지 못했다.

그러나 test case 오류에서 _retrieve 즉 값을 return 하는 함수에서 length가 undefined로 뜨는 것을 확인했고, 계속... 계속 고민하다가 답을 얻었다.

위 코드에서 originStorage은 this._storage이기 때문에 객체 형식이고 length를 가져올 수 없다는 게 문제였다. 현재의 limit로 바깥 for문을 돌리고 bucket을 선언하여 originStorage.get(i)을 할당해 주어 코드를 완성하였다.

 _resize(newLimit) {
    const originStorage =  this._storage;
    const originLimit = this._limit;
   
    this._limit = newLimit;
    this._storage = LimitedArray(this._limit);
    this._size = 0;

    for(let i = 0; i < originLimit; i++){
      if(originStorage.get(i)){
        let bucket = originStorage.get(i);

        for(let j = 0; j < bucket.length; j++){
          this.insert(bucket[j][0], bucket[j][1]);
        }
      }
    }
  }

그리고 다른 코드들도 자잘하게 변경하였고, 최종적으로 통과하였다.
정말 오래 걸렸지만 이해를 확실히 할 수 있어서 좋았다...

원래 오늘 하려던 것이 정말 많았지만 ,,,ㅜㅜ
확실히 recursion을 사용하지 못해서 아쉽긴 하지만 그건 내일 recursion 공부하면서 시도해야 할 것 같다.

Linked 함수도 어렵게 구현했는데 다 머릿속에서 없어진 것 같다.. 복습하자

socrative 문제 복습

1. 연결리스트는 데이터의 접근 속도는 배열보다 느리다.
   배열의 접근 시간 복잡도는 O(1)이고,
   연결리스트는 최소 한 번은 리스트를 순회하여야 하므로 O(n)이다.그러나 데이터 삽입 속도는 연결리스트가 빠르다.
   또, 배열보다 메모리를 더 효율적으로 사용할 수 있다. 배열은 js를 제외 하고는 선언할 때 크기도 정해주기 때문에 할당되지 않은 공간이 있지만 연결리스는 아니다.

2. js에서 노드가 5개인 연결 리스트의 모든 노드를 가장 효율적으로 삭제하고 싶을 때 총 몇 번의 연산이 필요할까?
   정답은 한번이다. head의 참조를 끊어 버리면 된다.
   reference
   js메모리용어

3. 해시 테이블과 해시함수
   해시 테이블은 두 개 이상의 값에 하나의 키를 사용할 수 없다.(overwrite) 키와 값은 한 쌍으로 저장된다.
   해시함수는 입력값과 출력값을 1대 1로 매핑하지만 고유한 값으로 만든다는 의미는 아니다. 그리고 해시 함수를 통해 만들어진 출력값은 원래의 입력값으로 되돌릴 수 없다.