Hash Table

key value 로 된 data를 지정한 크기의 bukets 안에 hash 주소로 data를 저장하는 자료구조이다.

다양한 언어에서 다양한 모습으로 존재한다. JS에서는 object라 할 수 있겠다.

insert , delete, look up 에서 O(1)의 시간 복잡도를 가진다.

하지만 정해진 크기를 넘어선 값을 저장하거나 우연히 hash값이 같아지면 1개의 주소에 이여져 2개 이상의 값이 들어갈 수도 있다.

이때는 look up의 시간 복잡도가 O(n)으로 상승할 수도 있다.

그리고 hash 주소는 random하게 지정되기에 내가 넣는 값이 순서대로 저장되지 않는다. 그래서 각 data의 key를 불러오는 작업을 하면 table 전체를 둘러보며 찾아야하기 때문에 이때는 속도가 느려진다.

Hash Table code

hash Table을 간략히 코드로 옮기면 다음과 같다.

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }
// hash 키 만들기
  _hash(key) {
    let hash = 0;
    for (let i =0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }

  set(key, value) {
    let address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }

  get(key){
    const address = this._hash(key);
    const currentBucket = this.data[address]
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++){
        if(currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    }
    return undefined;
  }
}

Exercise

first recurring character

주어진 배열에서 첫번째로 반복되는 값을 찾아라

Given an array = [2,5,1,2,3,5,1,2,4]:
It should return 2

Given an array = [2,1,1,2,3,5,1,2,4]:
It should return 1

Given an array = [2,3,4,5]:
It should return undefined

주의 : 단순히 for loop 중첩으로 문제를 해결하려하면 2번째 경우 return 값이 2 가 나올 수 있다. 이점에 유의해서 풀어야한다.

정답
Hash table을 이용하면 다음과 같이 풀 수 있다.

function firstRecurringCharacter(input) {
  let map = {};
  for (let i = 0; i < input.length; i++) {
    if (map[input[i]] !== undefined) {
      return input[i]
    } else {
      map[input[i]] = i;
    }
  }
  return undefined
}

참고
Udemy " Master the Coding Interview: Data Structures + Algorithms " - Zero To Mastery