Hash Table ( 해시 테이블) 에 대해 알아보기 😤

---

해시 테이블 ?

 

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

---

연관 배열 구조 ( Associative array ) 란 ?

 

키 하나와 값 한대다 1 대 1 로 연관되어 있는 자료 구조이다.

따라서 Key 값을 이용하여 값을 도출 할 수 있다.

 

연관 배열 구조가 지원하는 명령

1. 키 / 값 삽입
2. 키 / 값 확인
3. 키 / 값 수정
4. 키 / 값 삭제 

---

해시 테이블의 구조

---

해시 테이블의 구성 요소

 

• 키
  • 고유한 값이며 해시 함수의 input 이 된다.
  • 다양한 길이의 값이 될 수 있다. 
  • 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
• 해시 함수
  • 키를 해시로 바꿔주는 역할을 한다.
  • 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다.
  • 서로 다른 키가 같은 해시가 되는 경우를 해시 충돌(Hash Collision)이라고 한다.
  • 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
• 해시
  • 해시 함수의 결과물이며, 저장소(bucket, slot)에서 값과 매칭되어 저장된다
• 값
  • 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

---

해시 테이블의 기능 

 

Insertion

해시 테이블에서 자료를 저장하기 위해서는 해시 함수(Hash Fucntion)으로 키(key)를 해시(hash)로 변경해야 한다. 

위의 사진처럼 해시 함수가 input key를 7로 나눈 나머지로 변경해서 출력했을 때, 

키(key)는 ‘76’, 해시(Hash)는 ‘6’이다.

그러면 미리 준비해놓은 0, 1, 2, 3, 4, 5, 6의 저장소(bucket, slot) 중에 

맞는 해시(hash)값을 찾아 해당 값(value)를 저장한다.

해시 함수로 해시를 산출하는 과정에서 

서로 다른 key가 같은 hash로 변경되는 문제가 발생할 수 있는데, 

이는 key 와 value가 1:1로 매칭이 되어야 한다는 규칠을 위배한 것이되므로 

이 문제를 해결하면서 저장되어야 한다. 

이는 해시 충돌(Hash Collision) 이라 한다.

✅ Insertion Big-O

저장 단계의 시간복잡도는 O(1)이다. 

키(key)는 고유하며 해시함수(hash function)의 결과로 나온 해시(hash)와 값(value)를 저장소에 넣으면 되기 때문이다. 

이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만, 최악의 경우 O(n)이 될 수 있다. 

해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문이다.

 

Deletion

저장되어 있는 값을 삭제할 때는 저장소에서 해당 key와 매칭되는 값(value)를 찾아서 삭제하면 된다. 

저장소에는 hash와 value가 함께 저장되어 있으므로 함께 지우면 된다.

✅ Deletion Big-O

삭제 단계의 시간복잡도는 O(1)이다. 

키(key)는 고유하며 해시함수(hash function)의 결과로 나온 해시(hash)에 매칭되는 값(value)를 삭제하면 되기 때문이다. 

이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만, 최악의 경우 O(n)이 될 수 있다. 

해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문이다. 

 

Search 

키(key)로 값(value)를 찾아내는 과정은 Deletion 과정과 비슷하다. 

1.  키로 hash를 구한다. 
2.  hash로 값(value)를 찾는다.

✅ Search Big-O

저장 단계의 시간복잡도는 O(1)이다. 

키(key)는 고유하며 해시함수(hash function)의 결과로 나온 해시(hash)에 매칭되는 값(value)를 찾으면 되기 때문이다. 

이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만, 최악의 경우 O(n)이 될 수 있다. 

해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문이다. 

---

Hash Collision(해시 충돌)

해시테이블은 Insertion, Deletion, Search 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있기 때문에 

자료구조의 효율성 측면에서 매우 우수하다고 볼 수 있다.  

하지만 해시(hash)를 이용한 자료구조 방식에 필연적으로 나타날 수 있는 문제는,

무한한 값 ( 해시테이블에서는 KEY를 의미 ) 을 유한한 값 ( 해시 테이블에서는 Hash를 의미 ) 으로 표현하면서

서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 된다는 것이다.

---

사진 출처 : 위키 백과

---