기술 면접 - 자료구조 (Hash 테이블)

테이블이란

• 저장되는 데이터가 key와 value가 하나의 쌍을 이루는 것
• 테이블에 저장되는 모든 데이터들을 이를 구분하는 키가 있어야 하고, 이 키는 데이터를 구분하는 기준이 되기 때문에 중복이 되어서는 안됨

해쉬 함수

키값이 배열의 인덱스 값으로 사용하기에는 적당하지 않다!
키값의 범위가 매우 넓어서 매우 큰 배열이 필요하다!

• 이 두 가지 문제를 동시에 해결해 주는 것이 해쉬 함수
• 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 수행함

충돌

• 만약 서로 다른 두 개의 키가, 해쉬 함수를 통과하였는데, 그 결과가 같다면 이를 충돌이라고 한다
• 충돌이 많이 일어난다면, O(1)으로 값을 탐색할 수 있는 장점이 없어진다

충돌 문제 해결책

1. Open Addressing

• 해시 충돌이 발생하면, 비어 있는 다른 칸에 저장하는 방식
• 바로 옆이 비어있다면 거기 넣을 수도 있고, 따로 함수를 만들어 다른 곳에 넣을 수도 있다

2. Separate Chaining

Java에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다. Separate Chaining 방식으로는 두 가지 구현 방식이 존재한다.

• 연결 리스트를 사용하는 방식(Linked List)

  각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다. 또 다른 특징으로는, 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.

• Tree 를 사용하는 방식 (Red-Black Tree)

  기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 개수가 적다면 링크드 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터 개수가 적을 때 Worst Case 를 살펴보면 트리와 링크드 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 링크드 리스트를 사용한다.

해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다. 그래서 HashMap 은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있음