[자료구조] 해시함수(Hash Function) 특징 및 생성자 구현

💡 javascript를 배우면서 해시함수에 대해서 많이 들어봤다. (직접적으로 사용한 적은 아직 없지만.. 😂)
해시함수를 사용하면 속도가 빨라진다는 장점은 알고 있었다!
이번 포스팅을 통해 해시함수를 이용하면 코드에서 어떤 점이 좋아지는지를 직접 코드를 작성해보면서 정리해보려 한다.

 

 

🫠 해시함수(Hash Fuction)란?

> 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
> 해시 함수 특성 
① 압축성 : 다양한 가변 길이의 입력에 대해 고정된 크기의 결과값을 반환하는 성질
② 효율성 : 어떤 입력 값에 대해서도 많은 자원과 시간이 소요되지 않고 처리되는 성질
③ 저항성 : 결과값을 바탕으로 입력 값을 찾는 것이 불가능한 성질(Hashed Text > Plain Text로 변경하는 것이 어려움)

 

 

🫠 해시테이블(Hash Table)이란?

> 해시함수(Hash Function)를 사용하여 평균 O(1) 시간 복잡도로 특정 값을 신속하게 찾는 자료구조 
❗️ But 충돌(Collision)이 발생함

 

 

 

---

🫠 해시테이블 생성자 함수 & 해시함수 구현

const HASH_SIZE = 37; // 상수로 지정하여 자원을 한정하여 구현

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

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

// hashCode() : 해시함수
HashTable.prototype.hashCode = function(key){
  let hash = 0 // index가 될 hash값
  for(let i = 0; i < key.length; i++){
    hash += key.charCodeAt(i) // 문자열이 갖고 있는 실제 내부 값으로 반환해서 hash에 누적
  }
  return hash % HASH_SIZE // HASH_SIZE만큼 모듈러 연산을 통해서 누적된 hash를 바탕으로 37 이내 숫자로 변환
}

👉🏻 해시테이블 생성자 함수(HashTable)와 해시함수(hashCode) 메서드를 구현하였다. 주석 처리를 통해 코드 설명 확인

✅ HASH_SIZE = 37;
💡 hash는 한정적인 자원 하에서 효율적으로 자원을 활용하면서 속도를 최적화하는 방법 중 하나이기 때문에, 상수로 지정하여 자원을 확장해서 구현하였다.

✅ hashCode()에서 사용한 charCodeAt()에 대해 아래 링크에서 간단하게 설명 및 예시를 들었으니 확인 ❗️

https://cyjcyj.tistory.com/38

[javascript] String(문자열) 내에 접근하는 다양한 함수 정리

 

 

 

❗️출력해보자

// 해시테이블 생성
let ht1 = new HashTable()
console.log(ht1) // HashTable { table: [ <37 empty items> ], length: 0 }

// hashCode()를 통해 각각 key에 해당하는 index로 연산하여 hash에 누적
console.log(ht1.hashCode('Ana')) // 13이 index로 활용됨
console.log(ht1.hashCode('Sue')) // 5가 index로 활용됨
console.log(ht1.hashCode('Paul')) // 32가 index로 활용됨

✅ HashTable() 생성자 함수를 통해 ht1에 size = 37인 공간이 생긴 것을 확인할 수 있다. 
✅ 인자값으로 넣은 각각의 key가 13, 5, 32로 반환된 것을 확인할 수 있다.