Data Structure - Hash Table (1)

1. 해쉬 테이블(Hash Table)

• Hash Table은 Key와 Value 한 쌍으로 저장하는 데이터 구조를 갖고 있다. 
• Key를 이용하여 원하는 data(value)를 바로 찾을 수 있기에 검색속도가 빠르다는 장점이 있다. 
• 파이썬의 Dictionary가 해쉬 테이블이고 그렇기에 파이썬에서는 별도로 해쉬테이블을 구현할 필요가 없다.
  ex) dic = {"name":"Raphael", "job":"developer"}   

 

[알아야 하는 용어]

• 해쉬(Hash): 임의 값을 고정된 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값에 대응하는 value를 갖고 있는 저장공간으로, 키 값을 기반으로 해시함수를 통해 직접 접근이 가능한 데이터 구조
• 해시 함수(Hash/Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value)/해쉬 주소(Hash Address): Key를 해시 함수로 연산하여 나온 결과값으로, Key에 대응하는 value의 저장공간에 대한 주소값을 의미한다. 이를 기반으로 해쉬 테이블에서 데이터(value)의 위치를 일관성있게 찾을 수 있다.
  - 쉽게 말해서, hash값은 배열의 index역할을 하는 것이다. 그러므로 절대로 중복되면 안된다.
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key 값을 추출할 수 있는 별도 함수도 존재할 수 있다.

[Hash Table이 작동하는 순서] 

---

2. 간단한 Hash 구현 

 

1) 초간단 Hash함수 만들기 

 

2) Hash함수 점검하기 

 

3) Hash Table에 데이터 저장하기 

---

3. Hash Table의 장단점 및 주요 용도

• 장점
  1) 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  
  2) 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움.
  - 특정 데이터가 이미 있는지 없는지 검증하기가 쉽다.
  
  

• 단점
  1) 일반적으로 저장공간이 더 많이 필요하다.(해시테이블에 낭비되는 저장공간이 존재한다.
  ex) value가 저장되어 있는 hash값이 0,4,5라고 한다면 1,2,3의 공간은 비어있다.  
  
  2) 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
  - 공간을 탐색시간과 맞바꾼다는 뜻은, hash값(key값)의 중복확률을 줄이기 위해 Hash Table의 저장공간을 크게 잡아서라도 Hash Table을 사용한다는 뜻이다. (검색속도가 빠르니 저장 공간을 더 소모해도 사용한다는 뜻)
  
  3) hash값 중복 및 충돌을 해결하기 위한 별도 자료구조가 필요하다. 
  
  

• 주요 용도
  1) 검색이 많이 필요한 경우
  
  2) 저장, 삭제, 읽기가 빈번한 경우
  
  3) 캐쉬 구현시 (중복 확인이 쉽기 때문)
  - 캐시(cache)란, 어떤 웹 페이지를 방문할 때마다 해당 웹 페이지의 모든 정보를 다운(로딩)받는 것은 시간을 많이 소모하기 때문에 고정적인 데이터들을 다운받아 놓고 동적으로 변하는 자료들을 그때마다 서버에서 받아 온다. 이 때, 다운받아 놓은 고정적인 데이터들을 저장하는 장소를 캐시라고 한다. 

---

4. Hash Collision(해시 충돌) 해결 알고리즘 - 좋은 Hash함수 사용하기 

- 해시 충돌이란 해시값(= 키값을 해시함수로 연산해서 나온 값)이 중복되는 것을 말한다. 

- 이 해시 충돌을 해결하는 방법에 대해 알아보자 

 

1) Chaining 기법

- Open Hashing(개방 해싱) 기법 중 하나로, Hash Table 저장공간 이외의 공간을 활용하는 기법이다. 

- 해시충돌이 발생하면 링크드 리스트를 사용하여 데이터를 추가로 뒤에 연결시켜 저장하는 방법이다. 

 

하지만, Hash Table로 인한 저장공간이 더욱 소모되는 상태에서 Chaining기법으로 인해 부가적인 저장공간을 사용해야 한다는 단점을 갖고 있다. 이를 보완한 기법이 Linear Probing 기법이다. 

 

2) Linear Probing 기법

- Close Hashing(폐쇄 해싱) 기법 중 하나로, 해싱충돌이 발생하면 Hash Table의 저장공간 안에서 충돌을 해결하는 기법이다. 

- 다시 말해, 충돌이 발생하면 Hash address를 이용하여 Hash Table의 빈공간을 찾아 저장하는 기법이다. 

- 이 기법을 사용하면 Hash Table의 저장공간 활용도를 높일 수 있다. 

---

5. Chaining 기법 구현해보기 

[기본 구조] 

 

시나리오1) data 변수를 hash 함수에 넣어 key값을 생성한다. 그렇게 생성된 key값을 hash_function 함수에 넣어 Hash address(value의 주소값)를 만든다. 그렇다면 이 Hash address를 중복되게 만들어보자. 

- Key는 Mike, Raphy / Value는 123456, 567890

- 위의 사진에서 보면 알 수 있듯이, data1과 data2는 서로 다른 key값을 갖고 있지만 hash_function 함수를 적용한 결과 동일한 해시값(hash address)을 갖게 된다. 이를 링크드리스트를 이용해 다음과 같이 저장하게 된다.

해시값	value1	value2
0
1
2
3
4
5
6	Mike의 value (123456)	Raphy의 value (567890)

- 하지만, 여기서 문제점은 Mike나 Raphy라는 key를 이용하여 value를 검색해도 결국 동일한 6번 hash address에 저장된 value에 접근하게 되고 결국 어떤 value가 어떤 key에 대응하는지 알 수 없게 된다는 것이다.

 

- 이 문제를 해결하기 위해 Linked List에 get_key함수로 만든 키값을 value와 함께 저장한다. 아래 그림을 참고하자.

해시값	value1	value2
0
1
2
3
4
5
6	1505219110 - 키값123456 - value	1740735022 - 키값 567890 - value

 

- 지금까지의 개념이 이해됐다면 코드로 구현해보자.

 

 

 

a) 데이터를 저장하는 메소드

- 위의 코드를 간략하게 설명하겠습니다. 예를 들어, 기본값이 0인 hash table을 생성해보자. (아래 사진 참고) 

 

- hash table의 어떤 저장공간에 처음 value을 저장한다면 추후에 발생할 충돌을 대비하여 key값과 그에 대응하는 value를 쌍으로하는 리스트를 저장하고, hash table의 어떤 저장공간에 0이 아닌 다른 값이 이미 저장되어 있다면 append를 통해 리스트를 삽입한다.(아래 사진 참고)

최초로 저장하는 경우 

해당 저장 공간에 이미 다른 값이 있는 경우

 

Hash Table에 저장된 리스트가 작동하는 원리

b) Hash Table의 데이터를 읽는 메소드

 

c) 검사하기