Linear Probing 방식은 해시 충돌을 처리합니다. 해시 테이블에 key 삽입 혹은 삭제 행위를 하였을 때, 어떻게 해시 충돌을 처리하는지 확인해볼 것입니다. 전체 코드를 확인한다면 링크로 이동해주세요.
삽입
삽입 테스트에 사용할 key 배열은 다음과 같습니다.
const keys = ["강호동", "김현성", "강형욱", "유재석", "서장훈", "민경훈"];
for (const key of keys) {
hashTable.add(key);
}해시 함수는 다음과 같습니다.
HashTable.prototype.getBucketIdx = function (str) {
let sum = 0;
for (let i = 0; i < str.length; i++) {
sum += str.charCodeAt(i);
}
return sum % this.size;
};각 key들이 해시 함수를 거쳐 도출된 해시 테이블 인덱스는 다음과 같습니다.
[4, 5, 5, 5, 3, 5]해시 충돌이 발생하면 Linear Probing 방식을 통해 빈 공간을 찾습니다.
HashTable.prototype.getEmptyBucketIdx = function (idx) {
let top = idx - 1;
let bottom = idx + 1;
while (top > -1) {
if (this.table[top]) {
top -= 1;
continue;
}
return top;
}
while (bottom < this.size) {
if (this.table[bottom]) {
bottom += 1;
continue;
}
return bottom;
}
};빈 공간에 key를 삽입합니다.
HashTable.prototype.add = function (key) {
const idx = this.getBucketIdx(key);
if (!this.table[idx]) {
this.table[idx] = new BucketNode(key);
return;
}
...
const node = new BucketNode(key);
const emptyIdx = this.getEmptyBucketIdx(idx);
console.log(
`KEY(${key}) HASH COLLISION AT ${idx}. FOUND EMPTY IDX AT ${emptyIdx}.`
);
this.table[emptyIdx] = node;
let prev = null;
let existed = this.table[idx];
while (existed) {
prev = existed;
existed = existed.next;
}
prev.next = node;
};삽입 테스트 결과
-
KEY(강호동) 삽입 시, 결과는 다음과 같습니다.
HashTable { table: [ null, null, null, null, BucketNode { val: '강호동', next: null }, null ], size: 6 } -
KEY(김현성) 삽입 시, 결과는 다음과 같습니다.
HashTable { table: [ null, null, null, null, BucketNode { val: '강호동', next: null }, BucketNode { val: '김현성', next: null } ], size: 6 } -
KEY(강형욱) 삽입 시, 결과는 다음과 같습니다.
KEY(강형욱) HASH COLLISION AT 5. FOUND EMPTY IDX AT 3.로그와 함께 다른 공간에 삽입되었습니다.HashTable { table: [ null, null, null, BucketNode { val: '강형욱', next: null }, BucketNode { val: '강호동', next: null }, BucketNode { val: '김현성', next: [BucketNode] } ], size: 6 } -
KEY(유재석) 삽입 시, 결과는 다음과 같습니다.
KEY(유재석) HASH COLLISION AT 5. FOUND EMPTY IDX AT 2.로그와 함께 다른 공간에 삽입되었습니다.HashTable { table: [ null, null, BucketNode { val: '유재석', next: null }, BucketNode { val: '강형욱', next: [BucketNode] }, BucketNode { val: '강호동', next: null }, BucketNode { val: '김현성', next: [BucketNode] } ], size: 6 } -
KEY(서장훈) 삽입 시, 결과는 다음과 같습니다.
KEY(서장훈) HASH COLLISION AT 3. FOUND EMPTY IDX AT 1.로그와 함께 다른 공간에 삽입되었습니다.HashTable { table: [ null, BucketNode { val: '서장훈', next: null }, BucketNode { val: '유재석', next: [BucketNode] }, BucketNode { val: '강형욱', next: [BucketNode] }, BucketNode { val: '강호동', next: null }, BucketNode { val: '김현성', next: [BucketNode] } ], size: 6 } -
마지막으로 KEY(민경훈) 삽입 시, 결과는 다음과 같습니다.
KEY(민경훈) HASH COLLISION AT 5. FOUND EMPTY IDX AT 0.로그와 함께 다른 공간에 삽입되었습니다.HashTable { table: [ BucketNode { val: '민경훈', next: null }, BucketNode { val: '서장훈', next: [BucketNode] }, BucketNode { val: '유재석', next: [BucketNode] }, BucketNode { val: '강형욱', next: [BucketNode] }, BucketNode { val: '강호동', next: null }, BucketNode { val: '김현성', next: [BucketNode] } ], size: 6 }
삭제
key 삭제 후, 동일한 key를 재삽입 해볼 것입니다.
hashTable.remove("김현성");
hashTable.add("김현성");삭제 시, 노드 간 연결이 끊어지지 않기 위해 기록을 해둡니다.
HashTable.prototype.remove = function (key) {
const idx = this.getBucketIdx(key);
this.table[idx].val = "DELETED";
};삭제 테스트 결과
-
KEY(김현성) 삭제 시, 결과는 다음과 같습니다.
HashTable { table: [ BucketNode { val: '민경훈', next: null }, BucketNode { val: '서장훈', next: [BucketNode] }, BucketNode { val: '유재석', next: [BucketNode] }, BucketNode { val: '강형욱', next: [BucketNode] }, BucketNode { val: '강호동', next: null }, BucketNode { val: 'DELETED', next: [BucketNode] } ], size: 6 } -
KEY(김현성)을 다시 삽입 시, 결과는 다음과 같습니다.
HashTable { table: [ BucketNode { val: '민경훈', next: null }, BucketNode { val: '서장훈', next: [BucketNode] }, BucketNode { val: '유재석', next: [BucketNode] }, BucketNode { val: '강형욱', next: [BucketNode] }, BucketNode { val: '강호동', next: null }, BucketNode { val: '김현성', next: [BucketNode] } ], size: 6 }
전체 코드
function BucketNode(val) {
this.val = val;
this.next = null;
}
function HashTable(size) {
this.table = Array.from({ length: size }).fill(null);
this.size = size;
}
HashTable.prototype.getBucketIdx = function (str) {
let sum = 0;
for (let i = 0; i < str.length; i++) {
sum += str.charCodeAt(i);
}
return sum % this.size;
};
HashTable.prototype.getEmptyBucketIdx = function (idx) {
let top = idx - 1;
let bottom = idx + 1;
while (top > -1) {
if (this.table[top]) {
top -= 1;
continue;
}
return top;
}
while (bottom < this.size) {
if (this.table[bottom]) {
bottom += 1;
continue;
}
return bottom;
}
};
HashTable.prototype.add = function (key) {
const idx = this.getBucketIdx(key);
if (!this.table[idx]) {
this.table[idx] = new BucketNode(key);
return;
}
if (this.table[idx].val === "DELETED") {
this.table[idx].val = key;
return;
}
const node = new BucketNode(key);
const emptyIdx = this.getEmptyBucketIdx(idx);
console.log(
`KEY(${key}) HASH COLLISION AT ${idx}. FOUND EMPTY IDX AT ${emptyIdx}.`
);
this.table[emptyIdx] = node;
let prev = null;
let existed = this.table[idx];
while (existed) {
prev = existed;
existed = existed.next;
}
prev.next = node;
};
HashTable.prototype.remove = function (key) {
const idx = this.getBucketIdx(key);
this.table[idx].val = "DELETED";
};
module.exports = HashTable;