[선형] 16. 선형 조사법 해시테이블

in 자료구조 on 선형




1. 선형 조사법 해시테이블 (Linear porbing Hash Table)

선형조사법

  • Hash 충돌이 발생했을 때, 그 다음 주소를 확인하고 비어 있다면 그 자리에 대신 저장하는 해시테이블 기반 자료구조
  • 객체 초기화 / 크기 반환 : LinearHashTable.clear(), LinearHashTable.size()
  • 전체 데이터 반환, 전체 데이터 출력 : LinearHashTable.getBuffer(), LinearHashTable.print()
  • 데이터 추가 / 삭제 / 반환 : LinearHashTable.put(), LinearHashTable.remove(), LinearHashTable.get()



3. 구현하기

기존 Hash Table 과 동일한 부분

// 충돌 빈도를 증가시키기 위해 5로 변겯ㅇ
const HASH_SIZE = 5;

// Element() : key, value 저장을 위한 생성자
function Element(key, value) {
  this.key = key;
  this.value = value;
}

// LinearHashTable() : 생성자
function LinearHashTable() {
  this.table = new Array(HASH_SIZE);
  this.length = 0;
}

//hashCode() : 해시 함수
LinearHashTable.prototype.hashCode = function (key) {
  let hash = 0;
  // loselosehash
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % HASH_SIZE;
};

// clear() : 초기화
LinearHashTable.prototype.clear = function () {
    this.table = new Array(HASH_SIZE);
    this.length = 0;
};

// size() : 크기 변환
LinearHashTable.prototype.size = function () {
    return this.length;
};

// getBuffer() : 데이터 셋 반환
LinearHashTable.prototype.getBuffer = function () {
    let array = [];
    for (let i = 0; i < this.table.length; i++) {
        if (this.table[i]) {
            array.push(this.table[i]);
        }
    }
    return array;
};

// print() : 데이터 셋 출력
LinearHashTable.prototype.print = function () {
    for (let i = 0; i < this.table.length; i++) {
        if (this.table[i]) {
            console.log(`${i} -> ${this.table[i].key} : ${this.table[i].value}`);
        }
    }
};

let lht = new LinearHashTable();
console.log(lht) //LinearHashTable { table: [ <5 empty items> ], length: 0 }



put()

// put() : 데이터 추가
LinearHashTable.prototype.put = function (key, value) {
  // 1. 해당 인덱스 값 존재 여부 확인
  // 2. 비어 있으면 put
  // 3. 비어있지 않다면 next index
  // 4. 다 차있어서 한바퀴 돌면 modular 연산
  // 5. 한바퀴 돌고 시작 index로 다시 돌아오면 멈춤
  let index = this.hashCode(key);
  let startIndex = index;

  console.log(`key: ${key} -> index: ${index}`);

  do {
    if (this.table[index] === undefined) {
      this.table[index] = new Element(key, value);
      this.length++;
      return true;
    }

    index = (index + 1) % HASH_SIZE;
  } while (index !== startIndex);

  return false;
};

let lht = new LinearHashTable();
console.log(lht); //LinearHashTable { table: [ <5 empty items> ], length: 0 }

lht.put("Ana", 150);
lht.put("John", 170);
lht.put("Donnie", 130);
lht.put("Mindy", 140);
console.log(lht.put("Paul", 110)); //true
console.log(lht.put("Sue", 140)); //false
// key: Ana -> index: 2
// key: John -> index: 4
// key: Donnie -> index: 0
// key: Mindy -> index: 3
// key: Paul -> index: 2
// key: Sue -> index: 1

lht.print()
// 0 -> Donnie : 130
// 1 -> Paul : 110
// 2 -> Ana : 150
// 3 -> Mindy : 140
// 4 -> John : 170



get()

// get() : 데이터 조회
LinearHashTable.prototype.get = function (key) {
  // worst case 시 O(1) 이 아닌 O(n)
  let index = this.hashCode(key);
  let startIndex = index;

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

    index = (index + 1) % HASH_SIZE;
  } while (index !== startIndex);

  return undefined;
};

let lht = new LinearHashTable();
console.log(lht); //LinearHashTable { table: [ <5 empty items> ], length: 0 }

lht.put("Ana", 150);
lht.put("John", 170);
lht.put("Donnie", 130);
lht.put("Mindy", 140);
console.log(lht.put("Paul", 110)); //true
console.log(lht.put("Sue", 140)); //false

lht.print();
console.log(lht.get("Ana")); //150
console.log(lht.get("John")); //170
console.log(lht.get("Sue")); //undefined



remove()

// remove() : 데이터 삭제
LinearHashTable.prototype.remove = function (key) {
  let index = this.hashCode(key);
  let startIndex = index;

  do {
    if (this.table[index] !== undefined && this.table[index].key === key) {
      let element = this.table[index];
      delete this.table[index];
      this.length--;
      return element;
    }

    index = (index + 1) % HASH_SIZE;
  } while (index !== startIndex);

  return undefined;
};

let lht = new LinearHashTable();
console.log(lht); //LinearHashTable { table: [ <5 empty items> ], length: 0 }

lht.put("Ana", 150);
lht.put("John", 170);
lht.put("Donnie", 130);
lht.put("Mindy", 140);
console.log(lht.put("Paul", 110)); //true
console.log(lht.put("Sue", 140)); //false

lht.print();
// 0 -> Donnie : 130
// 1 -> Paul : 110
// 2 -> Ana : 150
// 3 -> Mindy : 140
// 4 -> John : 170

console.log(lht.get("Paul")); //110
console.log(lht.remove("Paul")); //Element { key: 'Paul', value: 110 }
lht.print();
// 0 -> Donnie : 130
// 2 -> Ana : 150
// 3 -> Mindy : 140
// 4 -> John : 170



3. 문제 - 백신 접종

코로나 백신이 개발되어, 회사는 전 직원들에게 백신 주사를 접종하기로 하였다.
접종의 혼란을 줄이기 위하여, 부스 배정기(Hash 함수)를 사용하여 직원 이름 별로 접종할 부스를 사전에 예약 시켰으나,
몇몇 직원이 오지 않아 남는 부스가 생겨나게 되었다.
코로나 확산을 빠르게 막기 위해, 온 순서대로 부스 배정을 시키고, 사용 중이라면 다음 번호 부스로 배정 시킬 수 있도록 프로그램을 제작하시오.
예를 들어, Alice 1번, Bob은 3번에 배정되었고, 2번 부스가 비어 있는 상황에, 1번으로 배정 받은 다음 대기가 Tom은 2번에 배정되어 백신 주사를 맞게 된다.
입력은 직원들 이름으로 된 배열이 주어지고, 직원 별 주사를 맞을 부스 번호를 기록해 반환한다. (부스 번호 1번부터 시작)

function Element(key, value) {
  this.key = key;
  this.value = value;
}
function HashTable(size) {
  this.size = size;
  this.table = new Array(this.size);
  this.length = 0;
}

HashTable.prototype.hashCode = function (key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.size;
};

HashTable.prototype.put = function (key) {
  let index = this.hashCode(key);
  let startIndex = index;
  do {
    if (this.table[index] === undefined) {
      this.table[index] = new Element(key, true);
      this.length++;
      return true;
    }
    index = (index + 1) % this.size;
  } while (index !== startIndex);
  return false;
};

HashTable.prototype.get = function (key) {
  let index = this.hashCode(key);
  let startIndex = index;

  do {
    if (this.table[index] !== undefined && this.table[index].key === key) {
      return index
    }
    index = (index + 1) % this.size;
  } while (index !== startIndex);

  return undefined;
};

function answer(name) {
  let result = [];
  // 구현
  let ht = new HashTable(name.length);
  for (let i = 0; i<name.length; i++){
      ht.put(name[i])

  }
  for (let i = 0; i<name.length; i++){
    result.push(ht.get(name[i])+1)

}
  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  ["Mana", "Naomi", "Lelia", "Morris", "Madonna"],
  ["Oliver", "Mabel", "Nero", "Rei", "Kara", "Jordan", "Nami"],
  [
    "Ruby",
    "Robin",
    "Jordan",
    "Kori",
    "Rei",
    "Madonna",
    "Justin",
    "Maya",
    "Lakia",
    "Kali",
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i]));
}

// #1[ 2, 1, 3, 4, 5 ]
// #2[
//   3, 6, 7, 2,
//   1, 5, 4
// ]
// #3[
//   9, 7, 8, 6, 10,
//   3, 1, 4, 5,  2
// ]