Linear Probing 방식 Hash Table을 구현 - javascript

구현 코드

class HashTable {
   constructor(size = 10) {
      this.size = size;
      this.table = new Array(size);
   }

   hash(key) {
      return key.length % this.size;
   }

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

      if (this.table[index] === undefined) {
         this.table[index] = { key, value };
         return;
      }

      // 충돌이 발생하면 다음 빈 인덱스 조회
      for (let i = index + 1; i < this.size; i++) {
         if (this.table[i] === undefined) {
            this.table[i] = { key, value };
            return;
         }
      }
      // 빈 인덱스를 찾을 수 없으면 삽입 실패
      console.error('삽입을 실패.');
   }
}
const hashTable = new HashTable(10);

hashTable.insert('apple', '사과');
hashTable.insert('banana', '바나나');
hashTable.insert('orange', '오렌지');
console.log(hashTable);

HashTable 클래스를 생성하고, 생성자를 통해 size를 초기화하고 

hashtable의 데이터를 넣을 배열 사이즈도 초기화된다.
(default value : 10)

 

hash 메서드를 통해 데이터 key를 받으면 해당 키의 길이와 배열의 사이즈로

나머지 연산을 수행해 key의 인덱스 번호를 리턴한다.

ex) key: apple, size: 10 -> 인덱스는 5가 됨.
insert 메서드를 통해 key와 value를 받아 실질적인 데이터 삽입을 한다.

위의 hash 메서드를 통해 인덱스 번호를 받고, 해시테이블의 주소에 접근해 비어있으면 데이터를 삽입하고 리턴한다.
만약 데이터가 이미 있는 인덱스라면, index를 1 증가시키고 배열 사이즈만큼 반복문을 순회한다.
이때, 해시테이블이 비어져있는지 확인하고 비어져있으면 데이터를 삽입하고 리턴한다.

만약 주어진 사이즈에 비어져 있는 인덱스가 없다면 삽입을 실패한다.

 

해당 방식은 인덱스를 구하기 위해 key.length % this.size로 연산을 했지만, 해당 방식으로 하게 되면,

비교적 충돌이 쉽게 발생해 다음 주소로 데이터를 넣어야 하는 경우가 많이 발생한다.

이를 보완하기 위해 key의 길이가 아닌 아스키코드 값으로 연산을 하면 조금 더 충돌이 덜 발생하는 방법으로 구현이 가능하다.