Jun 개발노트

Hash Table

2020-07-23

HashTable

주소변환

  1. Hashing Function(Hashing)

    • 서로 다른 입력 데이터를 일정한 크기로 출력하는 방법
    • 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.
    • 요청하는 키(key)로 해시값(hash value)을 찾는 함수
    • 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다
  2. HashTable

    • 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조
  3. 정리

    • 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고
    • 이 주소에 데이터를 담는 것, 이것이 해시 테이블의 기본 개념이다.
    • 자료구조에서 특정 값을 가장 신속하게 찾는 방법
    • 테이블의 크기로 나누는 해싱함수로 인해 소수로 하는 것이 좋다.

Hashing 종류

  1. Division Method
    • 입력값을 테이블의 크기로 나눈다
      const division = function(key, tableSize) {    
            return key % tableSize
         }
      
  2. Digits Folding
    • 입력값을 자릿수마다 더해서 테이블의 크기로 나눈다.
    const division = function(key, tableSize) {    
          let hashkey = 0
          for(let i = 0; i < key.length; i++) {
                hashkey += key[i]
          }
            return key % tableSize
         }
    
  3. loseloseHashcode
    const loseloseHashcode = function(key) {
        let hash = 0;
        for(let i = 0; i < key.length; i++){
          hash += key.charCodeAt(i)
        }
        return hash % 37 
     }
    
  4. djb2hash
    const digitsFolding = function(key) {
        let hash = 5381 // 임의의 소수, 가장많이 사용되는 소
        for(let i = 0; i < key.length; i++) {
            hash = hash * 33 + key[i].charCodeAt(i)
        }
        return hash % 1013; // 1013 = HashTable의 가질수 있는 크기 보다 더 큰 수의 소수
       
     }
    

Hash collision 해결방법

  1. 체이닝
    • 테이블의 인덱스별로 연결 리스트를 생성해 그 안에 원소를 저장하는 방법, 가장 단순한 방법
    • 단점 : hash테이블외에 추가적인 메모리 소요 필요
    • 각 hash키를 링크드리스트로 연결하여 사용한다.
  2. 선형탐색법
    • 새 원소 추가시 인덱스가 이미 점유된 상태라면 인덱스 + 1씩 증가하여 빈곳에 추가하는 방