[자료구조]해시테이블 (HashTable)이란?

*해시테이블이란?

연관배열 구조를 이용해 키에 결과 값을 저장하는 자료구조 

 = 키(key)와 값(value)이 1:1로 연관 되어 있는 자료구조

 

아래와 같은 기능을 지원

- 키와 값을 저장

- 주어진 key로 value를 얻음

- 주어진 key의 value 삭제

- 주어진 key의 value를 새로운 값으로 교체

 

 

구조

- key는 해시함수를 통해 hash로 변경되고, hash는 value와 매칭되어 저장소에 저장됨

 

해시테이블의 단점

- 상하 관계가 있거나, 순서가 중요한 데이터의 경우 적합하지 않음

- 공간 효율성이 떨어짐 (미리 저장공간을 확보해 놔야해서)

- 해시 함수의 의존도가 높음

---

해시 함수

- 서로 다른 길이를 가진 key를 일정한 길이의 hash로 바꿔줌

- 어떤 기준으로 바꿔줄 것인가? -> 해쉬함수 알고리즘

 

해시 함수 알고리즘

(1) 나눗셈 법 (Division Method)

- 입력 값 % 테이블의 크기 = 나머지를 주소로 사용 

- 테이블 크기를 절대 넘지 않음

- 테이블의 크기를 소수로 정하는 것이 좋다고 알려져 있음

 

(2)자릿수 접기 (Digit Folding)

- 숫자의 각 자릿수를 더해 해시 값을 만듬

- 문자열을 키로 하는 해시 테이블에 잘 어울림 (ASCII코드 이용)

 

 

---

해시 충돌(Hash Collision)
- 서로 다른 key가 같은 hash가 되는 경우를 해시충돌(hash collision)이라고 함.

- 충돌 확률을 최대한 줄이는 해시함수를 만드는게 중요

해시 충돌 해결법?

 

1)체이닝 (Chaining) 
- 충돌 시 기존에 있던 값에 연결하여 해결

Andrew가 저장될 때 충돌이 일어나 Jack에게 연결시켜줌

 

- 장점 : 

• 한정된 저장소를 효율적으로 사용
• 해시함수 중요성 상대적으로 적어짐
• 상대적으로 적은 메모리

- 단점 : 

• 원하는 값을 찾기 위해 순차 탐색을 해야하는 링크드리스트의 단점 (한 hash에 자료가 계속 연결되면 검색 효율↓)
• 외부 저장공간을 사용해야하고 그에 따른 작업이 필요

- 시간복잡도 : head에 삽입 시 O(1) / tail에 삽입 및 삭제,조회 시 *O(a)~O(n)

*a는 한 hash에 연결된 데이터의 수

 

 

 

2)개방 주소법 (Open Addressing) 

- 충돌 시 비어있는 해시를 찾아 데이터를 저장

 

Andrew가 저장될 때 해시에 Jack이 들어있어 그다음 Hash에 저장

 

- 비어있는 해시를 찾는 규칙은 선형탐색(+n), 제곱탐색(충돌 해시의 제곱을 한 해시에 저장), 이중해시(다른 해시함수를 적용한 해시에 저장) 로 구분할 수 있음

 

- 장점 : 

• 또 다른 저장공간 없이 해시테이블 내에서 저장 및 처리 가능

- 단점 : 

• 해시 함수 성능에 전체 해시 테이블 성능이 좌지우지 됌.
• 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 함

- 시간복잡도 : 삽입, 삭제, 검색 O(1)~O(n)

 

 

 

 

참고사이트 :

https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table해시-해싱-해시테이블-자료구조의-이해-6ijyonph6o

https://luyin.tistory.com/191