[자료구조] 해시 - (2) 구현 - 일반 해시 테이블

2021. 3. 10. 11:52Front-end/자료구조

728x90
반응형
class HashTable {
    constructor() {
      this.storageLimit = 10; // 해시테이블의 용량 한계 설정
      this.table = new Array(this.storageLimit); // 정해진 용량 크기로 해시 테이블을 배열로 만듬
    }
    // 키, 인덱스, 값
  
    // key -> index (키를 가지고 인덱스로 변환해주는 해시 함수)
    Hash(key) {
      let hash = 0;
      for (let i = 0; i < key.length; i++) {
        /* charCodeAt() 메서드는 주어진 인덱스에 대한 
        UTF-16 코드를 나타내는 0부터 65535 사이의 정수 */
        hash += key.charCodeAt(i)
        console.log(`${key[i]} = ${key.charCodeAt(i)}`);
      }
      console.log("hash", hash);
      return hash % this.storageLimit;
    }
  
    // add(키,값)  - 원소를 추가한다.
    add(key, value) {
      const index = this.Hash(key);
      this.table[index] = value;
    }
    //get(key) - 키에 해당하는 원소를 찾아 그 값을 반환한다.
    get(key) {
      const index = this.Hash(key);
      return this.table[index];
    }
    //remove(키) - 키에 해당하는 원소를 찾아 삭제한다.
    remove(key) {
      const index = this.Hash(key);
      delete this.table[index]; // 객체에서 요소를 삭제하는 방법
    }
  }
  
  const hashTable = new HashTable();
  hashTable.add("john", "111222333");
  hashTable.add("dave", "222333444");
  hashTable.add("stella", "333444555");
  hashTable.add("mike", "444555666");
  
  console.log(hashTable.table);
  
  /* [
      <1 empty item>,
      '111222333',
      '444555666',
      <2 empty items>,
      '333444555',
      '222333444',
      <3 empty items>
    ] */

충돌을 해결하지 않은 해시테이블이다.
위의 코드는 다른 키 값에서 해시함수를 거쳐서 같은 해시 값을 도출해낼 수도 있는 일명 '충돌' 경우를 생각하지 않은 코드이다. 다음 게시물에서 충돌을 해결하는 방법을 알아보겠다.

728x90
반응형