[자료구조] 해시함수(Hash Function) 충돌(Collision) - 체이닝 해시테이블(2)

👉🏻 체이닝 해시테이블 정의 및 LinkedList 연결 링크 ⬇️⬇️⬇️

https://cyjcyj.tistory.com/135

[자료구조] 해시함수(Hash Function) 충돌(Collision) - 체이닝 해시테이블(1)

 

 

 

 

---

💚 지난 포스팅에 이어서 체이닝 해시테이블 메서드에 대해서 알아보자

👉🏻 print() 메서드

// print() : 데이터 셋 출력
ChainingHashTable.prototype.print = function(){
  for(let i = 0; i < this.table.length; i++){
    if(this.table[i]){
      let current = this.table[i].head
      process.stdout.write(`#${i}`) // #을 통해 현재 index로 출력

      do{
        process.stdout.write(` -> ${current.data.key} : ${current.data.value}`)
        current = current.next
      } while(current) // null일 경우 false로 형변환이 되면서 while문 종료 or 계속 순환

      console.log('')
    }
  }
}

✅ do-while문을 통해 한 번은 실행되도록 작성
✅ 해당 위치에 데이터가 있을 경우, while문을 돌면서 출력 

 

 

❗️ 출력해 보자

// 체이닝 해시테이블 생성
let cht3 = new ChainingHashTable()

// put 메서드로 데이터 추가
cht3.put('Ana', 173)
cht3.put('Donnie', 183)
cht3.put('Sue', 179)
cht3.put('Jamie', 190)
cht3.put('Paul', 168)

/*
key : Ana -> index : 13
key : Donnie -> index : 13
key : Sue -> index : 5
key : Jamie -> index : 5
key : Paul -> index : 32
*/

// print 메서드로 출력
cht3.print()
/*
#5 -> Sue : 179 -> Jamie : 190
#13 -> Ana : 173 -> Donnie : 183
#32 -> Paul : 168
*/

✅ cht3.print() 출력 결과를 보면 index가 겹친 Sue와 Jamie가 #5에 들어가 있고, 
Ana와 Donnie가 #13에 들어가 있는 것을 확인할 수 있다.

 

 

 

👉🏻 getBuffer() 메서드

// getBuffer() : 데이터 셋 반환
ChainingHashTable.prototype.getBuffer = function(){
  let array = [] // 복사 값 담을 임시공간

  for(let i = 0; i < this.table.length; i++){
    if(this.table[i]){ // 값이 있을 경우, 해당 위치에 LinkedList가 존재
      let current = this.table[i].head

      do{ // LinkedList 존재 > data 존재 > 바로 push
        array.push(current.data)
        current = current.next
      } while(current) // current가 null일 경우 false
    }
  }

  return array
}

✅ getBuffer는 for문을 통해 this.table[i]의 값이 true일 경우, do-while문이 실행
✅ 만약 this.table[i]의 값이 존재한다면 LinkedList가 존재한다는 의미. LinkedList가 존재한다면 data가 존재한다는 의미
✅ 임시 저장 공간인 array에 해당 data push(복사)

 

 

❗️ 출력해 보자

console.log(cht3.getBuffer())
/*
[
  Element { key: 'Sue', value: 179 },
  Element { key: 'Jamie', value: 190 },
  Element { key: 'Ana', value: 173 },
  Element { key: 'Donnie', value: 183 },
  Element { key: 'Paul', value: 168 }
]
*/

✅ 임시 배열에 cht3의 데이터가 모두 복사된 것을 확인할 수 있다.

 

 

 

👉🏻 get() 메서드

// get() : 데이터 조회
ChainingHashTable.prototype.get = function(key){
  let index = this.hashCode(key)

  // 해당 index에 값 유무 확인(Linkedlist가 존재), isEmpty()를 사용하여 LinkedList 내에 값이 있는지 확인 
  if(this.table[index] !== undefined && !this.table[index].isEmpty()){
    let current = this.table[index].head

    do{
      if(current.data.key === key){
        return current.data.value
      }
      current = current.next
    } while(current)
  }
}

✅ get() 메서드를 사용할 때, this.table[index]가 있는지 파악하고, isEmpty()로도 확인해야 한다. 
LinkedList의 유무만 파악한 후, data를 넣으려고 시도하다가 LinkedList에 data가 없을 수도 있기 때문. 
✅ while문을 돌다가 해당 key가 current.data.key와 같을 경우, return 

 

 

❗️ 출력해 보자

// 체이닝 해시테이블 생성
let cht4 = new ChainingHashTable()

// 데이터 추가
cht4.put('Ana', 174)
cht4.put('Donnie', 184) // collision
cht4.put('Sue', 179)
cht4.put('Jamie', 190) // collision
cht4.put('Paul', 168)

console.log(cht4.get('Ana')) // 174
console.log(cht4.get('Donnie')) // 184
console.log(cht4.get('Kim')) // undefined

✅ get()을 이용해서 key의 index 값이 반환된 것을 확인할 수 있다. 

 

 

 

👉🏻 remove() 메서드

// remove() : 데이터 삭제
ChainingHashTable.prototype.remove = function(key){
  let index = this.hashCode(key)
  let element = undefined // 삭제되는 데이터 반환을 위한 공간

  if(this.table[index] !== undefined){
    let current = this.table[index].head

    do{
      if(current.data.key === key){
        element = current.data // 삭제 전 data 할당
        this.table[index].remove(current.data) // LinkedList의 remove() 메서드 사용
        this.length--

        if(this.table[index].isEmpty()){ // 해당 데이터 삭제 후, LinkedList가 빈 공간일 경우
          delete this.table[index] // LinkedList도 삭제
        }
      }
      current = current.next
    } while(current)
  }

  return element
}

✅ remove 메서드
이는 LinkedList의 remove() 메서드에 해당하며, 코드 동작은 간단하게 (prev.next -> current.next)이다.
(prev - current - current.next)로 연결되어 있는 리스트에서 current를 제외한 (p -> c.n)으로 가는 원리
✅ 삭제 후, this.length-- 해주는 것 잊지 말기!

 

 

 

 

---

💡 체이닝 해시테이블을 통해 해시함수 충돌을 해결하는 방법을 알아보고 실습해봤다.

연결리스트가 그나마 익숙해서 선형조사법보다는 체이닝 해시테이블로 충돌을 해결하는 것이 더 보기 편한 것 같다.