[Javascript] Hash 란?

해시가 무엇인가요? 🧐

개발자들은 원하는 데이터를 조금이라도 더 빠르게 찾기 위해서 수많은 탐색 알고리즘을 연구하고 있습니다. 하지만, 그 데이터가 어디에 있는지 정확하게 안다면, 데이터를 탐색할 필요가 없습니다. 바로 찾아가면 되니까요! 이것을 가능하게 하는 것이 "해시"입니다.  해시를 활용한다면 찾고 싶은 데이터가 어디에 저장되어있는지 바로 알 수 있습니다. 어떻게 가능할까요?

 

 

해시함수 : myHashFunction
고정된 길이의 값을 반환하는 함수입니다. myHashFunction은 어떤 인자를 입력받아도 0부터 6 사이의 값을 반환해요.

해시 : myHash
해시함수의 반환값입니다.

해시 테이블 : myHashTable
해시를 key로 사용하는 자료구조입니다. myHashTable이 사용하는 해시 함수는 0부터 6 사이의 7개의 값을 반환해요. 따라서 myHashTable의 크기는 7입니다.

 

const HASH_SIZE = 7

const myHashFunction = (value: number) => {

  return value % HASH_SIZE
  
}


// 1. 고정된 길이의 hashTable 생성
const myHashTable = Array.from({length: HASH_SIZE})

// 2. 저장하고싶은 데이터
const value = 10234

// 3. 해시함수로 구한 데이터의 해시값 
const myHash = myHashFunction(value)

// 4. 해시값을 인덱스로 사용
myHashTable[myHash] = value

 

해시 함수와 해시 테이블을 사용하는 예시를 간략하게 작성해봤어요. 어떤 위치에 저장될지는 저장하고 싶은 데이터에 따라 결정되기 때문에 어디에 있는지 탐색할 필요 없이, 해시 함수를 통해 해시값을 알아내면 바로 접근이 합니다! 이는 O(1)의 시간 복잡도로 탐색, 수정, 삽입 등을 가능하게 해요. 또한, 어느 정도의 공간을 사용할지 예측 가능하기 때문에 일반 배열을 사용할 때 보다 공간 효율성이 높습니다. 

 

---

 

해시를 사용할 때 주의해야 할 점 ⚠️

앞서 말했듯이, myHashTable의 크기는 7입니다. 고정된 크기는 공간 효율성을 높여주지만, 반대로 최대 7개의 데이터밖에 저장을 하지 못한다는 의미이기도 해요. 따라서 저장할 데이터가 7개보다 많을 경우 데이터 충돌이 발생할 수 있습니다. 이를 해시 충돌이라고 불러요.

 

const HASH_SIZE = 7

const myHashFunction = (value: number) => {

  return value % HASH_SIZE
  
}


const myHashTable = Array.from({length: HASH_SIZE})

const value1 = 10235

const value2 = 29

const myHash1 = myHashFunciton(value1) // 1

const myHash2 = myHashFunction(value2) // 1


myHashTable[myHash1] = value1

myHashTable[myHash2] = value2 // 충돌! value1의 값이 유실되었어요.

 

 

value1과 value2는 완전히 다른 값이지만, 해시 함수를 거치면  동일한 해시가 반환됩니다. 따라서 value2의 해시를 그대로 사용한다면, 이전에 저장된 value1의 정보는 사라져요. 데이터가 손상된 것이죠. 그렇기 때문에 해시 충돌이 최대한 발생하지 않도록 공간을 넉넉하게 준비하고, 해시값을 넓게 분포시킬 수 있는 해시 함수를 만드는 것이 중요합니다. 😉  

 

 

사실 해시값을 아무리 길고 복잡하게 잘 만들어도, 해시 충돌로부터 완전히 자유로울 수는 없어요. 때문에 해시충돌이 발생했을 때를 대비하기 위한 안전장치가 필요합니다. 아래에 첨부한 글에서 해시에 대한 부가적인 설명과 해시 충돌을 해결할 수 있는 여러 방법들을 깔끔하게 소개하고 있으니, 궁금하신 분들은 아래의 글을 통해 추가 학습하시길 권해드려요! 👍🏻

 

 

JavaScript와 함께 해시테이블을 파헤쳐보자