hashTable

Hash Table

해시 테이블은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조이다.

• 연관배열 구조 : 키 1개와 값 1개가 1:1로 연관되어 있는 자료구조이다.

Hash Table 구조

키는 해시함수를 통해 해시로 변경되고 해시는 값과 매칭되어 저장소에 저장된다.

• 키(key)

  • 고유한 값으로 해시 함수의 input이 된다.
  • 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 높일 수 있다.

• 해시함수(Hash Function)

  • 키를 해시로 바꿔주는 역할을 한다.
  • 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영하게 해준다.
  • 서로 다른키가 같은 해시가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌 확률을 최대한 줄이기 위한 함수를 만드는 것이 중요하다
• 해시(Hash) : 해시 함수의 결과물이다, 저장소(bucket)에서 값과 매칭되어 저장된다.
• 값(value) : 저장소에(bucket)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

Mehod

키와 값이 주어졌을때, 아래와 같은 기능을 사용할 수 있다.

• 저장 : 해시함수의 결과로 나온 해시와 값을 저장소에 넣는다.
• 검색 : 해시함수의 결과로 나온 해시에 매칭되는 값을 찾는다
• 제거 : 해시함수의 결과로 나온 해시에 매칭되는 값을 제거한다.

Hash table 동작 원리

1. 키를 해쉬함수에 넣는다
2. 해쉬함수는 키를 특정 해시로 변경해준다.
3. 특정 해시에 값을 넣는다
4. 앞으로 해당키가 해쉬함수에 들어가면 항상 같은 해시로 변환되어 해시와 매칭되는 값을 리턴한다

예시)

dog를 넣으면 happy가 나와야할때 해쉬테이블의 기능

1. dog를 해쉬함수에 넣으면
2. dog는 1(hash)로 변경된다.
3. Array의 1번 인덱스에 happy를 넣는다
4. 항상 dog를 넣으면 해쉬함수는 1(hash)로 변경해준다.
5. Array는 index 1과 매칭되는 값을 반환한다.

Hash Function 특징

1. 항상 내가 가진 Array 길이 안의 값만 반환할 수 있음 ( 0 to length - 1 )
2. 특정 키를 넣었을때 항상 같은 값(hash)이 나와야함
3. 어떠한 저장도 할 수 없음, 그때그때 값을 주면 내뱉을 수 있어야함(기억하는게 아님)

충돌 - 하나의 Hash가 여러개의 값을 가질 경우

출처 : 코드스테이츠

예시

• storage에 값을 직접 넣지 않고, buckets(배열 또는 연결리스트로 구현)을 넣어 두개 이상의 튜플을 넣을 수 있도록 만든다.

    0:  [{ Brenden: Eich }]
    1:  [{ Steven: Tyler }]
    2:  [{ Dr.: Sunshine }, { Alan: Turing }]
    3:  [{ Mr.: Doob }]
    4:
    5:  [{ George: Harrison }, { John: Resig }]

array가 계속 늘어난다면?

• Hash Tables Resizing

  • Hash Table이 25% ~ 75%가 차있을때 제일 효과적로 운영됨
  • 25% 이하 : length / 2
  • 75% 이상 : length * 2

• 코드로 구현 한다면? => 참고

  1. 변경된 사이즈의 스토리지를 새로 생성

     • 해시 테이블의 스토리지 사이즈를 직접 조절하는 것이 아니라 스토리지를 새로 생성해야함

  2. 기존에 있던 스토리지에 저장되있던 값들을 전부 다시 해싱해서 새 스토리지에 넣어준다.

     • 스토리지의 사이즈가 리사이징 되었기 때문에 다시 해싱해야함
  3. 1,2번 작업이 끝난후 기존에 있던 스토리지에 새 스토리지 값을 할당해준다.(리사이징된 스토리지와 바꿔치기)

Hash Table이 O(n) Time Complexity를 가지는 경우

• 해시테이블이 커질때

  • 해시테이블을 키워준 후에 모든 요소를 해싱을 다시 해주어야함
• 해싱된 모든 키가 동일한 버킷에 담길때

해시테이블의 장점

1. 키를 가지고 빠르게 value에 접근하고 조작할 수 있다

   • ex) 주소록 저장(이름, 전화번호의 매칭을 사용해 데이터를 처리)

해시테이블의 단점

1. 순서가 있는 배열에는 어울리지 않는다.
2. 상하관계가 있거나, 순서가 중요한 데이터의 경우 Hash Table은 어울리지 않다. 순서와 상관없이 key만을 가지고 hash를 찾아 저장하기 때문이다.
3. 공간 효율성이 떨어진다.
4. 데이터가 저장되기 전에 미리 저장공간을 확보해 놓아야 한다. 공간이 부족하거나 아예 채워지지 않은 경우가 생길 가능성이 있다.

💁‍♀️ 참고블로그