hash

1. HashTable 구조

 

해시 테이블은 1 : 1관계인 (key, value) 데이터를 저장하는 자료구조입니다.

 

해시 테이블의 구조는

    1. key

    2. hash function

    3. hash

    4. value

    5. buket 

으로 이루어져 있습니다.

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

key는 해시함수를 통해 해시로 변경되어 value와 매칭되어 bucket에 저장됩니다.

---

2. HashTable 시간 복잡도

 

해시의 특성은 key는 고유하며 hash와 value가 메칭되어 있기 때문에 해시의 시간 복잡도는 다음과 같습니다.

    저장 단계 : O(1)이지만 해시 충돌이 발생하면 O(n)이 될 수도 있습니다.

    삭제 단계 : O(1)이지만 해시 충돌이 발생하면 O(n)이 될 수도 있습니다.

    검색 단계 : O(1)이지만 해시 충돌이 발생하면 O(n)이 될 수도 있습니다.

---

3. 해시 충돌

 

해시의 방식은 무한한 값인 key를 유한한 값인 hash로 표현하면서 mapping이 겹칠 수 있다는 단점이 있습니다.

이를 해쉬충돌이라고 부릅니다. (비둘기집 원리)

 

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

위 그림은 sandra를 해시 테이블에 넣을 때 충돌이 발생했고 chaining 방식으로 해결한 장면입니다.

 

해결방식은 

    1. chaining 

    2. open addressing(개방 주소법)

이 있습니다.

---

4. chaining

 

chaining은 자료 저장시 해시 충돌이 발생하면 linked list를 할당하여 데이터들을 연결하는 방식입니다.  데이터의 주소값은 바뀌지 않습니다.

 

장점 : 

    1. 한정된 bucket을 효율적으로 사용가능

    2. 해시 함수를 선택하는 중요성이 낮음

    3. 상대적으로 적은 메모리 사용(미리 잡을 필요가 없기 때문)

 

단점 :

    1. 한 hash에 자료들이 계속 연결된다면 검색 효율이 낮아짐

    2. 외부 저장 공간을 사용한다

    3. 외부 저장 공간 작업을 추가로 해야 한다.

 

chaining의 시간 복잡도는 다음과 같습니다. 이때 평균적으로 해시 하나당 (key의 수 / bucket의 길이) α개의 키가 들어 있습니다.

    저장 단계 : O(1)이지만 최악의 경우 모든 연결리스트를 지나서 접근해야 되기 때문에 O(n)이 될 수도 있습니다.

    삭제 단계 : hash의 연결리스트를 살펴보아야 해서 O(α)이지만 최악의 경우 한 해시에 모든 자료가 연결되어 있을 수                    있기 때문에 O(n)이 될 수도 있습니다.

    검색 단계 : hash의 연결리스트를 살펴보아야 해서 O(α)이지만 최악의 경우 한 해시에 모든 자료가 연결되어 있을 수                    있기 때문에 O(n)이 될 수도 있습니다.

---

5. 개방 주소법

 

개방 주소법은 다른 bucket에 데이터를 넣는 방식입니다. 넣는 방식은 대표적으로 3가지 방식이 있습니다.

    1. 선형 탐색 : 해시 충돌 시 다음 버켓 혹은 몇 개를 건너뛰어 데이터를 삽입

    2. 제곱 탐색 : 해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입

    3. 이중 해시 : 해시 충돌시 다른 해시 함수를 한 번 더 적용한 결과 사용

 

장점 :

    1. 해시 테이블 내에서 데이터 저장 및 처리 가능

    2. 또 다른 저장공간에서 추가 작업 없음

 

단점 :

    1. 해시 함수의 성능이 전체 해시 테이블의 성능을 지배함

    2. 데이터의 길이가 늘어나면 저장소의 길이도 늘어나야함

 

개방 주소법의 시간 복잡도는 다음과 같습니다.

    저장 삭제 검색 단계 : O(1)이지만 최악의 경우 hash를 찾아가는 과정이 길어질 수 있기 때문에 O(n)이 될 수도 있습니다.

---

c++에서 사용법

 

c++ STL에서 hash table이 정의되어 있습니다.

 

#include<unordered_map>
std::unordered_map<string, int> d;
cout<<d["leo"]<<endl

없는 key를 호출하면 기본 value값이 나옵니다. 이때 기본값은 int이기 때문에 0입니다.

 

d["leo"] = 3;
cout << d["leo"] << endl;

key와 value를 집어넣었기 때문에 3이라는 값이 나옵니다.

 

for (auto& i : d)
    cout << i.first << "-" << i.second << endl;

전체 hash를 참조하는 방법입니다. first는 key, second는 value가 참조됩니다.

 

출처 : 

velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해