[알고리즘(Algorithm)] 6. 해시테이블(HashTable)

 

* 해시(Hash)

---

 : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값.

   이를 이용하여 특정 위치에 값을 저장하거나 찾을 수 있다. 

 

    => '무언가를 잘게 쪼갠 후, 결과물을 생성하는 과정'    (Hash)

 

 

 

---

 

* 해시함수(Hash Function)

---

: 임의의 길이를 가진 데이터를 입력받아 고정된 길이의 값(해시값)을 출력하는 함수

 

💡 해시 함수에 의해 반환되는 값은
 해시 값(Hash Value) / 해시 코드(Hash Code) / 다이제스트(Digst) / 해시(Hash)라고 한다.

 

 

 

---

 

 

# 해시 테이블(HashTable)

---

: (Key, Value)로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 것이 특징이다. 

=> 내부적으로 배열(버킷, Bucket)을 사용하여 데이터를 저장하기 때문!

 

 

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 색인(index)를 생성하고,

이 index를 활용하여 값을 저장하거나 검색한다.

이때, 실제 값이 저장되는 장소를 버킷(Bucket) 또는 슬롯(slot)이라 한다.

 

 

 

이러한 해시 테이블은 파이썬(Python)의 딕셔너리(Dictionary)와 유사하다.

💡 Python,  < Dictionary >
"이름" = "홍길동", "나이" = "20" ...
위와 같은 방식으로 사람에 대한 정보를 나타낼 수 있다. 
이처럼 대응 관계를 나타내는 자료형이 바로 파이썬의 '딕셔너리(Dictionary)'이다.

 

 

Key - Value 예시

menu = {"apple":1000, "melon":5000, "grape":8000 }

 

위처럼 '과일 - 가격' 형태로 Key - Value를 설정한다고 하였을 때,

"grape"의 찾고자 한다면,

Key가 "grape"인 것에 접근하여 Value를 확인하면 되기에 시간 복잡도는 O(1)이 된다. 

 

💡 시간복잡도 O(1)은, 충돌이 일어나지 않는 이상적인 상황이다.
    (반대로, 충돌이 발생하여 최악인 상황은 O(N)이 된다.)

          시간복잡도 더 알기 = > https://01-study-for-me.tistory.com/19 

 

 

 

---

 

 

 

# 해시(Hash)값이 충돌하는 경우 (Hash Collision)

---

만약 "melon"이 저장된 테이블에, 

"grape"를 추가하였을 때, 똑같은 인덱스로 Key - Values가 잡힌다면? 

 

이때는 인덱스가 덮어 씌워지며 '충돌'이 일어난다.

 

 

이러한 충돌을 해결하기 위해 2개의 방법을 사용한다. 

   (1) 분리연결법(Separate Chaining)

   (2) 개방 주소법(Open Addressing)

[ 참고 : https://mangkyu.tistory.com/102 ]

 

 

 

 

---

 

 

# 해시테이블의 시간복잡도

---

 

 

​	최선 👍​	최악 👎​	배열​	연결리스트​
탐색​	O(1)​	O(n)​	O(1)​	O(n)​
삽입​	O(1)​	O(n)​	O(n)​	O(1)​
삭제​	O(1)​	O(n)​	O(n)​	O(1)​

 

* 👍 최선(충돌이 일어나지 않은, 일반적인 경우)

        = > 시간복잡도 O(1)

 

* 👎 최악(해시 충돌이 일어난 경우)

        = > 시간복잡도 O(n)

 

 

 

 

---

 

 

 # 해시 테이블의 장점

---

- 관계를 모형화할 수 있다.

- 중복을 피할 수 있다. (중복을 피하는 설계로 가장 이상적이다.)

 

- 서버에 작업을 시키지 않고 자료를 캐싱(Chaching)할 수 있다.

 

 

💡 캐싱(Chaching)
 읽기(Read) / 로드(LoaD) 등의 작업을 수행할 때,
 데이터나 값을 미리 복사해 임시 장소에 저장하여, 기존 데이터보다 더 빠르게 액세스할 수 있도록 하는 방법.

 

 

 

 

 

 

* 참고 *

[자료구조] 해시(Hash)란 무엇인가

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