Data Structure - Hash Table

 Hash Table 

해시 함수를 사용해 key-value 쌍을 저장하고 검색하는 자료구조이다.

• Hash = 해시함수 어떤 데이터를 고정된 길이의 값으로 변환하는 함수를 말한다. 해시 함수를 통해 입력된 데이터를 특정 규칙에 따라 숫자나 문자열로 변환하는 역할을 합니다
• Hash table은 효율적인 탐색을 위한 자료 구조로써 hash함수를 통해 얻은 key-value 쌍의 데이터를 저장하고 검색한다.
• hash 함수에 key값을 넣어 얻은 해시값을 index 위치로 지정하여 데이터 쌍을 저장한다. 배열과 유사한 형태지만 index가 아닌 해시 값을 통해 데이터를 찾는다.
• 저장, 삭제, 검색의 시간복잡도는 O(1)로 데이터를 순차적으로 검색하는 게 아니라 key값으로 한번에 찾아낸다.

 

 Hash Collision ( 해시충돌 ) 

wiki dictionary - hash collision

해시 테이블에서 같은 두 개의 다른 데이터가 동일한 해시 값을 공유할 때 해시 충돌이 발생한다.(wiki)

이를 해결하기 위한 방법은 다음과 같다.

• 체이닝 : 리스트 형태로 연결해 저장
• 오픈 주소법 : 비어있는 다른 슬롯에 저장

 

 JavaScript로 HashTable구현하기 

자바스크립트에서 new Map()객체를 통해 Hash Table 자료구조를 구현할 수 있다.

• new Map()으로 해시 테이블을 초기화한다
• 배열을 돌면서 현재 필요한 값을 계산한 뒤, has메서드로 table에서 필요한 값이 hashTable에 있는지 확인한다. 데이터가 없으면 해당 요소는 hashTable에 set저장한다. 이를 반복하며 해당 값을 찾는다.
• for문을 돌면서 배열의 요소를 확인하므로 시간복잡도는 O(N) for문에서 hashTable에 해당 데이터가 있는지 확인하는 시간복잡도는 O(1) O(N) * O(1) = O(N)

function solution(arr, target) {
  let hashTable = new Map(); 
  for (let i = 0; i < arr.length; i++) {
    let complement = target - arr[i]; 
    if (hashTable.has(complement)) { 
      return true; 
    }
    hashTable.set(arr[i], true); 
  }
  return false; 
}

 

 

---

Reference 

https://overcome-the-limits.tistory.com/9

https://www.educative.io/blog/data-strucutres-hash-table-javascript

https://www.linkedin.com/pulse/demystifying-hash-tables-javascript-key-efficient-data-adjanohoun/