Hash Tables(Map)

임쿠쿠·2020년 8월 26일
1

Hash Tables

const user = ['kevin', 'korean', 29]

일반적으로 데이터를 저장하기 위해 배열을 사용한다. 하지만 때로는 위와 같이 해당 배열이 정확히 무엇을 나타내는지 이해하기 어렵다.

const user = {
  name: 'kevin',
  homeCountry: 'korean',
  age: 29,
}

이를 해결하기 위해 value에 key를 적용하여 해당 데이터가 무엇을 나타내는지 명확히 표기할 수 있다. 이를 object라 하며, object역시 넓은 의미의 'Hash Table'이다.

Hash Table 구현


  • 많은 언어들이 hash table을 내장하고 있다. ex) object, Dictionary
  • 각각의 데이터는 key를 가지고 있고 key와 value는 연결된다.
  • key는 정렬되어 있지 않다.
  • 검색, 추가, 삭제가 빠르다.
  • hash function을 사용하여 hash table을 만든다.

Hash Table 구현

class Hashtable {
  constructor() {
    this.data = [];
    this.size = 0;
  }

  hash(key) {
    const chars = key.split("");
    const charCodes = chars.map((char) => char.charCodeAt());
    const charCodeSum = charCodes.reduce((acc, cur) => acc + cur);
    return charCodeSum;
  }

  set(key, value) {
    const hash = this.hash(key);

    if (!this.data[hash]) {
      this.data[hash] = [];
    }

    this.data[hash].push([key, value]);
    this.size++;
  }

  get(key) {
    const hash = this.hash(key);

    if (this.data[hash]) {
      for (const item of this.data[hash]) {
        if (item[0] === key) {
          return item;
        }
      }
    }
  }

  keys() {
    const keys = [];

    for (let bucket of this.data) {
      if (bucket) {
        for (let item of bucket) {
          keys.push(item[0]);
        }
      }
    }

    return keys;
  }

  values() {
    const values = [];

    for (let bucket of this.data) {
      if (bucket) {
        for (let item of bucket) {
          values.push(item[1]);
        }
      }
    }

    return values;
  }

  entries() {
    const entries = [];

    for (let bucket of this.data) {
      if (bucket) {
        for (let item of bucket) {
          entries.push(item);
        }
      }
    }

    return entries;
  }
}

const newHashtable = new Hashtable();
//console.log(newHashtable.hash('name'))
//console.log(newHashtable)

newHashtable.set("name", "jsiub");
newHashtable.set("mean", false);
newHashtable.set("age", 30);
//console.log(newHashtable.data)
//console.log(newHashtable.entries())
console.log(newHashtable.get('name'));
console.log(newHashtable.values());
profile
Pay it forward

0개의 댓글