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

✅ 해시함수 충돌 해결방법으로 지난 포스팅에서 '선형조사법'에 대해 다뤘었다. 아래 자료 참고 ⬇️

 

👉🏻 충돌이 생기는 이유

https://cyjcyj.tistory.com/123

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

 

👉🏻 해결방법 '선형조사법'

https://cyjcyj.tistory.com/124

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

 

 

 

---

✅ 이번 포스팅에서는 해시함수 충돌의 또 다른 해결 방법인 '체이닝 해시테이블'에 대해서 정리할 계획이다.

 

 

💡 충돌 해결 방법 

② 체이닝 해시테이블(Chaining Hash Table) : 해시테이블 기반 자료구조

> 연결 리스트를 병합 사용하여 Hash 충돌을 해결

 

🫠 체이닝 해시테이블의 다양한 메서드 구현 

const HASH_SIZE = 37

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

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

// hashCode() : 해시 함수
ChainingHashTable.prototype.hashCode = function(key){
  let hash = 0

  for(let i = 0; i < key.length; i++){
    hash += key.charCodeAt(i)
  }
  
  return hash % HASH_SIZE // hash에 대한 모듈러를 통해서 HASH_SIZE 이하의 숫자로 반환
}

✅ 체이닝 해시테이블 생성자함수 및 해당 prototype은 앞 포스팅과 많이 반복되기 때문에 따로 설명 ❌

 

 

❗️ 출력해 보자

// ChainingHashTable 생성
let cht1 = new ChainingHashTable()

console.log(cht1) // ChainingHashTable { table: [ <37 empty items> ], length: 0 }

 

 

 

---

🧐 체이닝 해시테이블은 연결리스트를 병합해서 충돌을 해결한다고 했는데, 연결리스트를 어떻게 가져올까?

✅ 아래 링크를 통해 만들었던 LinkedList를 import 해서 가져오면 된다. 

✅ 기존에 작성한 LinkedList의 생성자 함수와 메서드를 사용하기 위해 .mjs 확장명으로 변경 후, 해당 파일 export 해준다.

import { LinkedList } from '../../파일 위치'

// LinkedList와 병합
let ll = new LinkedList()
ll.append(new Element('Ana', 172))

console.log(ll)
/*
LinkedList {
  head: Node { data: Element { key: 'Ana', value: 172 }, next: null },
  length: 1
}
*/

✅ LinkedList를 import해온 뒤, LinkedList의 head에 Element로 준 인자값이 들어가도록 구현하였다. 

 

💛 LinkedList의 append 메서드 해석 링크 ⬇️

https://cyjcyj.tistory.com/97

[자료구조] 선형자료구조 연결리스트(Linked List)에 노드(Node) 추가하기

 

 

 

 

---

🫠 연결리스트와 병합한 체이닝 해시테이블의 메서드를 구현해 보자 

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

// size() : 크기 반환
ChainingHashTable.prototype.size = function(){
  return this.length
}

✅ 초기화, 크기 반환 메서드는 간단하면서도 계속적으로 반복되는 코드이기 때문에 따로 설명하지 ❌

 

 

 

// put() : 데이터 추가
ChainingHashTable.prototype.put = function(key, value){
  let index = this.hashCode(key)
  console.log(`key : ${key} -> index : ${index}`)

  if(this.table[index] === undefined){ // 해당 위치 빈공간일 경우
    this.table[index] = new LinkedList() // LinkedList 생성
  }

  // LinkedList의 append 메서드 사용하여 데이터 추가
  this.table[index].append(new Element(key, value))
  this.length++

  return true
}

✅ 인자값으로 주어지는 key의 해시코드에 해당하는 index가 비어있다면 LinkedList를 생성해 준다.
✅ LinkedList의 메서드인 append를 사용하여 해당 index에 데이터를 추가한 후, 길이를 +1 증가시킨다. 

 

 

 

❗️ 출력해 보자

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

// 데이터 추가
cht2.put('Ana', 173)
cht2.put('Donnie', 183)
cht2.put('Sue', 179)
cht2.put('Jamie', 190)
cht2.put('Paul', 168)
/*
key : Ana -> index : 13
key : Donnie -> index : 13
key : Sue -> index : 5
key : Jamie -> index : 5
key : Paul -> index : 32
*/

// 해시테이블 조회
console.log(cht2)
/*
ChainingHashTable {
  table: [
    <5 empty items>,
    LinkedList { head: [Node], length: 2 }, // LinkedList의 길이: 2 (Sue와 Jamie)
    <7 empty items>,
    LinkedList { head: [Node], length: 2 }, // (Ana와 Donnie)
    <18 empty items>,
    LinkedList { head: [Node], length: 1 },
    <4 empty items>
  ],
  length: 5
}
*/

✅ 출력 결과를 보면 Sue와 Jamie가 index:5의 값으로 같은 위치에 해당하고, Ana와 Donnie가 index:13으로 충돌된 것을 확인할 수 있다.
✅ 하지만 LinkedList를 통해 각 해당 위치에 충돌된 2개의 데이터를 넣어 충돌을 해결하였다.
✅ 데이터가 충돌하여 같은 index에 들어간 Sue와 Jamie, Ana와 Donnie의 LinkedList의 길이가 2인 것을 확인할 수 있다. 

 

 

 

🫠 다음 포스팅에서는 체이닝 해시테이블의 추가/삭제 등 또 다른 메서드를 구현해 보고, 확인해 볼 것이다!