[자료구조] 해시함수(Hash Function) 충돌(Collision) - 선형조사법(2)

🥹 지난 시간 작성했던 해시함수 충돌에 대한 해결방법인 선형 조사법에 대해 이어서 메서드를 구현해보려고 한다. 
이번 포스팅에서 작성할 메서드는 remove()와 get() ❗️

해시함수 충돌과 해결방법 확인 ⬇️⬇️⬇️

https://cyjcyj.tistory.com/123

[자료구조] 해시함수(Hash Function) 충돌(Collision)과 해결방법(1)

 

 

 

 

---

🫠 선형조사법 해시테이블 get() 메서드 구현

// get() : 데이터 조회
LinearHashTable.prototype.get = function(key){
  let index = this.hashCode(key) // 찾고자 하는 key의 index
  let startIndex = index

  do {
    // 해당 위치에 값이 있고 && 값의 key가 찾는 key와 같다면
    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
}

✅ do-while문 중 if문 && 다음으로 나오는 코드를 넣은 이유는?
👉🏻 충돌 해결을 위해 index + 1을 하며 해시테이블을 순회하며 비어 있는 공간에 데이터를 넣었기 때문이다.

 

 

❗️ 출력해 보자

// 해시테이블 생성
let lht3 = new LinearHashTable()

lht3.put('Ana', 173)
lht3.put('John', 179)
lht3.put('Donnie', 183)
lht3.put('Mindy', 190)
lht3.put('Paul', 168)
/*
key : Ana -> index : 2
key : John -> index : 4
key : Donnie -> index : 0
key : Mindy -> index : 3
key : Paul -> index : 2
*/

// 데이터 조회
console.log(lht3.get('Ana'))
console.log(lht3.get('Paul'))
console.log(lht3.get('Kim'))
/*
173
168
undefined
*/

✅ Ana와 Paul이 충돌하지만, index + 1을 하여 비어있는 공간에 데이터를 추가해 Paul이 1번째 자리에 추가되었다.
✅ get 메서드를 통해 데이터를 조회하고, 해당 값이 출력된 것을 확인할 수 있다. (데이터가 없는 Kim은 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
}

✅ do-while문을 보면 조건이 get() 메서드와 같은 것을 확인할 수 있다.
✅ 해당 데이터를 삭제하기 전에 변수 element에 담아 return 해주었다.

 

 

❗️ 출력해 보자

// 해시테이블 생성
let lht4 = new LinearHashTable()

lht4.put('Ana', 174)
lht4.put('John', 179)
lht4.put('Donnie', 184)
lht4.put('Mindy', 190)
lht4.put('Paul', 168)
/*
key : Ana -> index : 2
key : John -> index : 4
key : Donnie -> index : 0
key : Mindy -> index : 3
key : Paul -> index : 2
*/

// 데이터 삭제
console.log(lht4.remove('Ana')) // Element { key: 'Ana', value: 174 }
// 데이터 조회
console.log(lht4.get('Paul')) // 168

// 데이터 삭제 후, 바로 조회
console.log(lht4.remove('Paul')) // Element { key: 'Paul', value: 168 }
console.log(lht4.get('Paul')) // undefined

// 사이즈 확인을 통해 데이터 삭제 확인
console.log(lht4.size()) // 3

// 해시테이블 출력
console.log(lht4)
/*
LinearHashTable {
  table: [
    Element { key: 'Donnie', value: 184 },
    <2 empty items>, // 비어있음을 확인할 수 있다.
    Element { key: 'Mindy', value: 190 },
    Element { key: 'John', value: 179 }
  ],
  length: 3
}
*/

✅ size() 메서드 반환 결과는 3이며, 이는 Ana와 Paul의 값을 삭제했기 때문임을 알 수 있다.

 

 

 

😂 다음 포스팅에서는 해시함수 충돌의 또 다른 해결방법인 '체이닝 해시테이블'에 대해서 다뤄보고자 한다. 

파이팅~~ 🙌🏻