[SW 정글 79일차] Project 3 - Hash Table을 쓰네

오늘은 어제 memory menagement 과제를 이해하면서 구현하기 시작했는데 page table를 구현하는데 있어 hash table을 쓰는 것을 알았다.

그래서 한 번 정리하고 넘어가려고 한다.

 

 

 

1. Hash Table이란?

해시 테이블은 (key, value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있는 특징을 가진다.

아래의 그림을 보면 value가 buckets이라는 배열에 저장되고 has function에 의해 key가 인덱스로 변하여 접근하기에 빠른 데이터 검색을 할 수 있는 것이다.

buckets은 실제로 vaule가 저장되는 곳이라고 이해하면 된다.

출처  :https://en.wikipedia.org/wiki/Hash_table

그림에서 보여지는 key와 value를 예시로 사용하여 어떠한 매커니즘으로 구현이 되는지 이해해보자.

먼저, (John Smith, 521-1234)인 데이터를 해시 테이블에 저장한다고 생각해보자.

먼저, index를 구해야하는데 index는 hash_function("John_Smith") % buckets_size연산을 통해 얻을 수 있다.

이렇게 index를 구하면 buckets[index]에 "521-1234"가 저장이 된다.

 

이렇게 데이터들이 하나하나 저장이 되고 조회를 할 때에는 key값을 주면 hash_funcion을 1번만 사용하여 index를 구하고 원하는 value를 구할 수 있다.

 

 

 

 

2. 인덱스가 겹치지 않을까?

위에서 key가 인덱스로 변하는 과정을 보면 많은 데이터들이 들어오면 인덱스가 겹치지 않을까하는 생각이 든다.

실제로 겹칠 가능성은 충분히 존재하고 이를 해시 충돌이라고 부른다.

이러한 해시 충돌을 해결하기 위한 방법으로 분리 연결법(separate Chaining)과 개방 주소법(Open Addressing)이 있다.

 

1) 분리 연결법(separate Chaining)

출처  :https://en.wikipedia.org/wiki/Hash_table

separate chaining이란 동일한 버킷(인덱스가 같음)의 데이터에 대해 추가적인 자료구조(연결리스트, 레드블랙트리 등)를 이용하여 다음 데이터의 주소를 저장하는 것이다.

위 그림을 보면 152번 인덱스에 2개의 데이터가 존재하고 데이터는 마치 연결리스트처럼 이어져 있다.

separate chaining방식의 장점은 해시 테이블의 확장이 필요없고 간단하게 구현할 수 있고 삭제가 편리하다는 장점이 있다.

단점으로는 동일한 인덱스에  chaining되는 데이터들이 많아지면 캐시의 효율성(O(1)로 검색이 가능)이 감소하다는 것이다.

 

 

2) 개방 주소법(Open Addressing)

Open Addressing은 추가적인 메모리를 사용하는 separate chaining과는 다르게 현재 buckets에서 비어있는 공간을 활용하는 방법이다.

Open Addressing을 구현하는 방법은 3가지가 존재한다.

 

1. Linear Probing: 현재 인덱스로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장하는 방식

2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식으로 예를 들면 처음 충돌이 발생했을 때에는 1만큼 이동하고 다음에 충돌이 일어나면 2^n (n=1; n++)씩 칸을 옮기는 것이다.

3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애는 방식이다.

 

---

[오늘의 나는 어땠을까?]

오늘부터 pintos project3 과제를 구현하기 시작했다.

project 1때부터 삐르게 이해하고 구현을 시작하는 동료들이 있는데 그런 동료들을 보면 뒤쳐진다는 생각이 안드는 것은 거짓말이다.

이번에도 빠르게 과제를 파악하고 문제해결을 해나가는 동료들이 있다.

각자의 장단점이 있기는 하겠지만 문제를 파악하고 해결하는 속도가 좋은 능력은 개발자에게 필요한 능력이라고 생각하고 나도 그 능력을 키우고 싶다.

지금은 과제를 구현하기 위한 기본적인 지식을 쌓는 것을 우선시 하여 진행하고 있지만 코드를 이해하고 구현해나가는 능력이 뒤쳐진다는 생각에 걱정이 든다.

 

그래도 내가 정한 방향이니까 일단은 밀고 나간다.

2개월도 채 남지 않은 시점, 지치지 말자.

---

<참고 자료>

https://bcho.tistory.com/1072

https://mangkyu.tistory.com/102