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

❗️ 해시함수를 사용하면 빠른 속도로 특정 값을 신속하게 찾아 성능을 높일 수 있지만, 충돌이 일어날 수 있어 이를 항상 대비하며 사용해야 한다. 충돌이란?! 아래에서 다뤄보고자 한다.

지난 포스팅을 통해 해시함수 메서드를 확인해 보자 ⬇️⬇️⬇️

https://cyjcyj.tistory.com/122

[자료구조] 해시함수(Hash Function) 메서드 구현

 

 

❗️ 충돌(Collision)이 생긴 경우

ex) YJ, SH를 해시함수로 변경한 경우, 둘 다 2로 변경되었다고 가정

--> 해당 2에 YJ가 있어 SH가 공간에 들어오지 못하는 상황이 되거나, 이미 2가 채워져 SH가 있다고 착각하는 등의 경우가 발생

 

👉🏻 저번 포스팅에서 구현한 메서드를 사용하여, 충돌의 예시를 아래와 같이 작성

// hashTable 생성
let ht4 = new HashTable()

ht4.put('Ana', 172)
ht4.put('Donnie', 183)
ht4.put('Sue', 155)
ht4.put('Jamie', 168)
ht4.put('Paul', 180)

console.log('')
/*
HashTable {
  table: [
    <5 empty items>,
    Element { key: 'Sue', value: 155 },
    <7 empty items>,
    Element { key: 'Ana', value: 172 },
    <18 empty items>,
    Element { key: 'Paul', value: 180 },
    <4 empty items>
  ],
  length: 3
}
*/

✅ 실제로 Donnie와 Jamie는 hash 충돌이 일어났으며, put()에서 공간이 undefined가 아닌 경우, false를 return 하기 때문에 데이터가 추가되지 않은 것을 확인할 수 있다.

 

 

 

---

💡 충돌 해결 방법

① 자료구조 확장 > 선형 조사법 해시테이블(Linear probing Hash Table)

- Hash 충돌이 발생했을 때, 그 다음 주소를 확인하고 비어있다면 그 자리에 대신 저장하는 해시테이블 기반 자료구조

 

🫠 선형 조사법 해시테이블의 다양한 메서드 구현

// 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
  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)
    }
  }
}

👉🏻 어디서 많이 본 코드 아닌가? 
바로 지난 시간 포스팅했던 해시함수 메서드 구현에서 작성한 메서드와 똑같다. 
HashTable 생성자 함수에서 LinearHashTable 생성자 함수로 변경된 것 외에 크게 달라진 점은 없기 때문에
따로 설명은 하지 않겠다. (지난 시간에 관련 코드에 대해 설명하였으니 확인 ✅)

 

 

 

---

🫠 선형 조사법 해시테이블의 메서드(put(), get(), remove())

> 이번에 다룰 메서드는 변경된 코드 구현이다.

① put() : 데이터 추가

// put() : 데이터 추가
LinearHashTable.prototype.put = function(key, value){
  let index = this.hashCode(key)
  let startIndex = index // 배열의 공간을 한 바퀴 돌았는지 여부 체크

  console.log(`key : ${key} -> index : ${index}`) // key가 어떻게 변형됐는지 확인

  do{
    if(this.table[index] === undefined){ // 공간이 비어있다는 뜻
      this.table[index] = new Element(key, value)
      this.length++
      return true
    }

    index = (index + 1) % HASH_SIZE // 해당 index가 비어있지 않은 경우, index에 +1 증가
  } while(index !== startIndex) // 처음 위치로 돌아오는 경우에는 false (공간이 없다는 뜻)

  return false
}

👉🏻 코드 설명은 주석 처리 확인
✅ do-while문을 통해 코드를 작성하였으며, while(index !== startIndex)의 조건을 넣어 비어있는 Index의 공간을 찾을 때까지 한 바퀴 돌고, 결국 처음 넣었던 startIndex와 같아진다면 while문을 빠져나오도록 구현하였다.
(즉, 해당 key의 index 값이 이미 담겨져있는 공간이라면 index + 1을 하여 while문을 돌아 빈 공간을 찾는 코드)

 

 

❗️출력해보자

// LinearHashTable 생성
let lht2 = new LinearHashTable()

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

console.log(lht2)
/*

LinearHashTable {
  table: [
    Element { key: 'Donnie', value: 183 },
    <1 empty item>,
    Element { key: 'Ana', value: 172 },
    Element { key: 'Mindy', value: 190 },
    Element { key: 'John', value: 179 }
  ],
  length: 4
}
*/

👉🏻 현재 1번째 자리만 비워진 상태로 총 4개의 데이터가 추가된 것을 확인할 수 있다.
만약 여기서 충돌되는 데이터를 추가한다면?

 

 

❗️Paul 데이터 추가

console.log(lht2.put('Paul', 168))
/*
key : Paul -> index : 2 // Ana와 index가 겹침
true // 비어있는 index를 찾아 아래 주석과 같이 index : 1에 들어간 것을 확인
*/


console.log(lht2)
/*
LinearHashTable {
  table: [
    Element { key: 'Donnie', value: 183 },
    Element { key: 'Paul', value: 168 },
    Element { key: 'Ana', value: 172 },
    Element { key: 'Mindy', value: 190 },
    Element { key: 'John', value: 179 }
  ],
  length: 5
}
*/


console.log(lht2.put('Sue', 163))
/*
key : Sue -> index : 1
false // index가 1이 나왔지만, 이미 공간이 차있기 때문에 추가되지 못하고 false
*/

👉🏻 주석 처리 확인
✅ 새로 추가한 Paul 데이터가 Ana와 충돌되었지만, put() 메서드의 do-while문을 통해 비어있는 index를 찾을 때까지 index + 1을 하여, 현재 비어있던 첫 번째 자리에 데이터가 추가된 것을 확인할 수 있다.
❗️But 이후 추가한 Sue의 index 값이 1이지만, 이미 공간이 꽉 찼기 때문에 false를 리턴하고 데이터가 추가되지 못한 것을 확인할 수 있다.

 

 

🥹 포스팅이 길어져, 다음 포스팅에서 데이터를 조회하는 get() 메서드와 데이터를 삭제하는 remove() 메서드를 구현하고, 출력해 보도록 하겠다. (해시.. 해쉬.. 해시.. 감자..)