2월달부터 시작한 SSAFY CS스터디, 아래의 링크를 토대로 OS관련 테크인터뷰 항목에 대한 질문을 정리하며 공부했다.
어느덧 목차 3번의 Network까지 왔으니 전진과 동시에 복습도 필요할 때다.
참고: GitHub - VSFe/Tech-Interview
Keywords
: Hash자료구조, Hash함수 충돌, 해시값 충돌, 해시값충돌 처리, Double Hashing
📢 키워드별 설명
1️⃣ Hash 자료구조에 대하여
Hash의 대표 특징
🍊: Hash자료구조가 어떤 특징을 갖고 있었나?
- 어떤 입력값에도 항상 고정된 길이의 해시값을 출력한다 (ft. 모듈러연산)
- 입력 값의 아주 일부만 변경되더라도 전혀 다른 값을 출력한다
- 출력된 결과값을 통해 입력값을 유추할 수 없다
Hash관련 용어
🍊: 자주 나올 용어들을 미리 파악하자
Hash Function, Home address, Hash Table, Bucket, Slot, Collision, Synonym, Overflow.. 정도가 있었지만 HashTable, Bucket, Slot까지만 알아도 후의 내용을 보는데 무리는 없다
| Hash Table 해시 테이블 |
해시 함수가 키값을 생성할 때 참조하는 테이블 |
| Bucket 버킷 |
하나의 주소를 갖는 파일 한 구역 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수가 됨 |
| Slot 슬롯 |
한 개의 레코드를 저장할 수 있는 공간 한 버킷 안에 여러개의 슬롯 존재 |
Hash의 3가지 성질
🍊: 이론적으로 다음과 같은 성질이 있음을 짚고가자
| 제 1역상 저항성 | 1. 주어진 output값으로 원래의 input을 알아내기 어려워야 함 2. y(해시값)으로부터, h(x) = y를 만족하는 x가 찾기 불가능할 것 |
| 제 2역상 저항성 | 1. 동일한 output을 가지는 input이외의 input’을 찾기 어려워야 함 2. h(x) = h(x’), x ≠ x’ 를 만족하는 x’를 찾는 것이 불가능할 것 |
| 충돌 저항성 | 1. 서로 다른 입력 값을 해시했을 때 같은 output을 나오기 어려워야 함 2. h(x)가 주어졌을 때, 동일한 y값을 내는 (x, x’)쌍을 찾기 어려울 것 3. h(x) = h(x’)를 만족하는 x, x’를 찾는 것이 불가능할 것 |
HashMap(=Hash Table)
- Key-Value 형태
HashMap의 내부구현
1. Array를 통하여 구현됨
: 배열이 크기와 상관없이 데이터에 상수 시간으로 접근 가능한 특징을 이용하기 위함
2. Array에 저장하기 위해 Key의 Hash를 구함
: Key의 Hash를 구하는 방법이 바로 HashFunction
3. Key의 hash값이 구해지면, 배열 사이즈에 맞도록 modular(%)된 값을 index로 사용함
: array[ hf(key) % M] = value (M: HashMap Size)
2️⃣ Hash 함수의 충돌에 대하여
일반적인 해시 충돌의 개념
: 서로 다른 key들이나 같은 hash를 가지는 경우
- Key1 ≠ key2, hf(key1) == hf(key2)
HashMap에서의 해시 충돌
: hashFunction만으로는 충돌이 되지 않으나, 매핑을 위한 어떤 모듈러 연산시의 값이 동일함
: 즉, 키와 해시결과값 뿐만 아니라 모듈러연산과정(%M) 까지를 충돌의 한 부분으로 인식해야 함
- hf(key1) ≠ hf(key2), hf(key1) % M == hf(key2) % M
🍊 위의 두 가지의 의미가 혼재에서 사용되므로, 이 경우를 인지하고 있을 것
충돌이 일어나는 원인
- 구현상의 어려움 존재
- 1️⃣ 에서의 Hash 3가지의 성질을 구현하기 어렵다
- 해시 자체가 저러한 성질을 구현해냈다고 쳐도, 모듈러 연산에서 다시 문제가 발생한다
- Key의 사이즈와 HashMap사이즈의 불일치
- 무한한 가짓수의 입력값(key)을 넣고 싶지만, 유한한 가짓수의 출력값이 생성됨 (ft. 비둘기집원리)
- 따라서, 이러한 충돌률이 낮은 함수가 좋은 해시함수가 됨
- HashMap사이즈 자체의 확정짓기 어려움 존재
- 개발자가 HashMap의 사이즈를 일단 예상하여 그 크기의 Max를 잡아야 함
- 그 크기를 과도하게 잡는다면 비용의 낭비가 발생하고, 그 크기가 부족하다면 이 또한 문제가 될 것임
- 정확한 예측이라는 것 자체가 어려움
- 한 2년 전 기준으로 대충의 크기를 잡고 그 크기가 넣을 것 같으면 크기를 증가시키고 그랬음
3️⃣ 해시값 충돌에 대한 일반적인 처리에 대하여
🍊 해시값 충돌에 대한 처리기법으로는 크게 OpenAddressing, SeparateChaining 두 가지 방법이 있다
직관적인 사진부터 보자
⛳ Separate Chaining
- 해시테이블의 크기를 유연하게 만듦, 추가적인 공간으로 해결
- LinkedList를 이용함
SC 동작과정
1. Key도 Value도 100인 데이터가 있다
해시함수 결과: hf(100) = 1
모듈러 연산 결과: hf(100) %10 = 1 // size를 맞추기 위한 모듈러 연산
해당 결과를 가리키는 bucket을 찾아감
2. 그 100데이터 노드를 가리키는 포인터가 들어간다
해당 Bucket의 Slock에는 실제 데이터 100을 넣는 게 아니다
3. 만약, 다음과 같이 모듈러 연산 이후에 같은 위치를 가리키는 충돌이 일어났다고 치자
4. LInkedList를 이용해 연결 노드로 집어넣으면 된다
a. 이때, 100의 뒷자리 꼬리에 넣는 게 아니라 Head에 넣는다
b. Head에 넣어야 Add연산 작용이 빠르기 때문이다
5. 이 방법으로 예측되는 결과
a. 추가적인 메모리 공간을 쓴다는 것이 낭비일 수 있다
b. LinkedList가 너무 길어지면 탐색하는데에 오래걸릴 수 있다
(1). 시간 복잡도 분석
최악의 경우 : O(n)
평균 적인 경우 : O(α) (α : 버킷당 평균 요소의 개수)
⛳ Open Addressing
:해시테이블의 크기는 고정해놓음, 인접한 비어있는 공간(Bucket)으로 해결
: ft. Linear Probing, Quadratic Probing, Double Hashing
OA동작방식 - Linear Probing.ver
- 충돌에 따른 인접공간의 접근방식을 갖고 있다
(hf_lp(key, i) = hf(key) + i, i=충돌횟수(0, 1, 2. …))
일단은, 첫 수행시에는 i=0테고 이번에는 테이블에 바로 value을 집어넣는다
2. 아까처럼 모듈러 연산까지 마쳤더니 충돌이 일어나는 케이스를 생각해보자
이때는 충돌횟수만큼 자리를 옮겨 적당한 자리를 찾게 된다
3. 특징은 다음과 같다
a. 이렇게 순번이 차례로 넘어가니, 직선형 구조로 데이터가 쌓여가게 된다 (그래서 linear)
b. 이들은, 만약 hf(key)의 값이 갖게 나오므로 인한 충돌 발생시, 계속i에 대한 같은 수행이 일어난다
OA동작방식 - Double Hashing
: hf_dh(key, i) = hf(key) + i * 2nd_hf(key)
- 2nd_hf(key)의 값이 map의 사이즈와 서로소여야 한다는 점을 전제조건으로 함
- 그렇지 않으면 한번도 접근하지 못하는 공간(bucket)이 발생하는 비효율이 나타난다
- 충돌이 일어났을때, 단순히 + i, + i^2 등의 연산이 아니라 전혀 별개의 hash Function을 사용하여 사용공간을 넓게 쓰겠다라는 의미
- 앞서 수행했던 방식들은 자신에게 알맞은 자리를 찾기위해서 앞에서도 했엇을 i의 연산이 반복된다, 이를 줄이기 위하여 사용된다
OA동작방식의 단점
- 중간 연결고리 역할을 하는 key가 삭제된다면 이미 있는 값도 없다고 판단할 수 있다 (다시생각해보자, OA방식은 이미 존재하는 키들을 집어넣는 방식을 결정한다)
- 원래 세번째 자리에는 506이 있었다
- 506을 삭제 했다고 치자 → 3번 주소에는 빈 공간이 생겼다
- 787에 대한 add연산이 들어왔다고 치자, 787은 이미 table에 있음에도 해당 연산과정에서 3번이 비어있으니 넣고본다
OA동작방식의 해결책
sol1. 삭제가 일어났을 때, 그 공간을 DELETE와 같은 상징적인 형태로 표시하라
- 이 표시를 확인하면 다음 위치도 확인하는 동작을 넣는다 ( Delete를 만나면 무조건 다음 위치를 확인하는 것이 단점)
sol2. 삭제 위치 다음에 open Addressing된 key들을 모두 한 단계씩 땡겨온다
- 이동시키는 추가적인 비용 발생
4️⃣ Java언어에서의 해시 충돌 처리에 대하여
| C++ | 개별체이닝 |
| JAVA | 개별체이닝 |
| GO | 개별체이닝 |
| RUBY | 오픈 어드레싱 |
| PYTHON | 오픈 어드레싱 |
개별체이닝(Separte Chaning)
- 앞의 내용으로 대체