Hash Table

# Hash Table

 - 키와 값이 1:1로 연결되어 있는 자료구조

 - 키를 저장할 때 해당 키를 특정 인덱스로 변환하는데, 그 함수를 해시 함수(Hash function)라고 함

 - 키 값에 해시함수를 적용해 해당 요소의 값이 저장되어 있는 주소값(인덱스)를 계산해 접근하는데, 이를 해싱(Hashing)이라고 함

 

 

 ## Hash function의 특징

   - 결과값으로 항상 해시테이블 크기 범위에 있는 숫자를 반환 (0부터 전체 길이 -1 까지)

   - 같은 입력값이라면 항상 나오는 결과값의 인덱스도 같아야 함

   - 해시함수는 키나 특정 값을 저장하는 역할을 하지 않고, 단순히 키값을 받아 주소값을 리턴해주는 역할만 함

 

 

 ## Hash Table에서의 용어

   - key :  이 key를 이용해 해시함수가 특정 인덱스를 계산, 고유한 값

   - value :  해당 key와 1:1 매칭되어 있는 값

   - storage :  해시테이블에서 자료를 저장하는 전체 공간을 의미

   - bucket :  각 해시테이블에 인덱스(주소) 별로 존재하는 슬롯

   - tuple :  해시충돌이 일어나는 상황에서 버킷 내부에서 해당 자료들을 연결시켜 저장하는데, 이때 각각의 자료들이 저장되는 버킷 내부의 공간

 

 

 ## 해시충돌

   - 서로 다른 키값을 가진 자료들이 동일한 인덱스를 리턴받아 같은 버킷으로 접근하게 될 때, 해당 자료들의 인덱스값이 중복되어 충돌 문제가 발생

   - 이를 해결하기 위한 방법으로는 크게 Seperate Chaining, Open Addressing 두 가지 방법이 존재

 

  1. Seperate Chaining

   - 충돌이 일어났을 경우, 해당 주소의 버킷에 기존에 들어 있던 자료와 연결시키는 방법

   - 연결 리스트를 이용

   - 장점 :  한정된 공간을 효율적으로 사용할 수 있고, 상대적으로 메모리 사용이 적음

   - 단점 :  같은 버킷에 저장되어야 할 자료들이 많아지면 검색 효율이 떨어짐

 

 

  2. Open Addressing

   - 충돌이 일어났을 경우, 스토리지의 다른 비어 있는 버킷을 찾아 데이터를 저장

   - 장점 :  주소값이 중복되는 자료를 저장하기 위한 다른 저장공간을 생성할 필요가 없음

   - 단점 : 중복되는 인덱스가 많아져 비어 있는 다른 버킷에 저장한다면 해당 자료가 다시 충돌을 일으킬 가능성이 있고, 저장된 항목들의 수가 스토리지 내부의 버킷 수를 초과할 수 없음

 

 

 ## Hash Table의 사용 예시

   - dictionary, map 구조

 

 

 ## Hash Table의 Property

   - limit :  스토리지의 전체 버킷 슬롯 수

   - size :  현재 스토리지에 저장되어 있는 자료들의 갯수

   - storage :  자료들이 저장될 해시테이블 저장공간

 

 

 ## Hash Table의 Method

 

   - insert :  해시 함수를 이용해 키값을 특정 인덱스로 변환한 뒤 해시테이블에 삽입

insert 연산
  1. 키값과 해시함수를 이용해 자료가 저장될 인덱스값을 계산
  2. 해당 인덱스에 이미 자료가 존재하는지 확인
       존재한다면
         이미 존재하는 자료와 삽입하려고 하는 자료의 키값을 비교
           키값이 서로 같다면 삽입하려고 하는 자료로 이미 존재하는 자료를 덮어씀
           다르다면 튜플을 하나 만들어 현재 삽입하려고 하는 자료를 해당 버킷에 저장
       존재하지 않는다면
         해당 인덱스에 자료를 저장
  3. size를 하나 증가
  4. size가 limit의 75% 이상이라면 리사이징
  

 

   - retrieve :  해시 함수를 이용해 변환된 인덱스로 특정 값을 탐색해 찾은 값을 반환

retrive 연산
  1. 키값과 해시함수를 이용해 찾을 자료가 존재한다고 생각되는 인덱스를 계산
  2. 해당 인덱스에 자료가 존재하는지 확인
       존재한다면
         해당 요소를 리턴
       존재하지 않는다면
         undefiend를 리턴
  

 

   - remove :  해시 함수를 이용해 변환된 인덱스로 특정 값을 삭제하고 삭제된 값을 반환

reomve 연산
  1. 키값과 해시함수를 이용해 삭제될 자료의 인덱스값을 계산
  2. 해당 인덱스의 버킷을 순회하며 자료가 존재하는지 확인
       존재한다면
         해당 자료를 제거하고 반환
         size를 하나 감소
         size가 limit의 25% 이하라면 리사이징
       존재하지 않는다면
         undefiend를 리턴
  

 

   - resize :  해시 테이블은 전체 크기의 0.25보다 크고, 0.75보다 작을 때에 가장 효율적으로 운영되기 때문에 해당 범위를 벗어날 때마다 리사이징

resize 연산
  1. limit을 갱신
  2. size, storage를 초기화
  3. 초기화된 storage에 값들을 다시 해싱