TL;DR

자료구조 빈출 유형 !!!

• 해시 테이블은 키에 대한 해시 값을 사용해 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 Associate Array.
• 해시 테이블은 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있기 때문에 사용한다.
• 해시 함수에는 Division, Multiplication, Folding, Universal Hashing 등 다양한 방법이 있다.
• 충돌(Collision)을 처리하기 위해 링크드 리스트나 트리를 활용하는 Chaining 기법과 빈 공간에 저장하는 Open Addressing 방법을 사용한다.

해시 테이블

• 해시(hash) : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값

• 해시 함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

• 데이터가 조금만 달라져도 결과가 확연하게 달라져 무결성을 지키는데 도움을 주고,
• 기본적으로 복호화가 불가능해 보안성을 지키는데 도움을 준다.

1. 해시 테이블이란?

• 키(Key)와 값(Value)을 매핑해 둔 데이터 구조
• 키(Key)는 특별한 알고리즘을 이용해 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

• 데이터의 양이 아무리 많아지더라도 이론적으로 해시 변환, 검색, 삭제에 걸리는 시간은 $O(1)$ 로 매우 빠르다.

• 해시 테이블의 기본 개념은 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이다.

  따라서 특이하게도 데이터가 입력되지 않은 여유공간이 많아야 제 성능을 발휘할 수가 있다.

장점

• 데이터 삽입, 삭제, 조회가 빠르다.

• 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.

  (하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능하다.)

단점

• 순서를 보장하지 않아 순서/관계가 있는 목적에는 적합하지 않다.

  (데이터를 정렬된 순서로 접근할 때 비용이 높다.)

• 지역 참조성에 취약하다.

2. 해시 함수

• 고유한 인덱스 값을 설정하는 특별한 알고리즘, Hash Function
• 좋은 해시 함수는 특정 값에 치우치지 않고 해시값을 고르게 만들어낸다.

1) Division Method 나눗셈

• 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 반환
• m은 대게 소수를 사용하고, 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 한다.

2) Multiplication Method 곱셈

• 숫자로 된 키가 $k$이고 $A$는 0과 1 사이의 실수일 때 실수의 곱셈법은 아래와 같이 정의된다.
• $m$이 얼마가 되든 크게 중요하지는 않고 보통 2의 제곱수로 정한다.
• 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 한다.

\[h(k) = (kA mod 1)xm\]

3) Digit Folding 자릿수 접기

• 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR 한 값을 해시값으로 삼기.
• ex) 583924를 각각 자릿수별로 더하면 31 -> 이제 두 자리씩 Folding -> 121

4) Universal hashing 전체 해싱

• 다수의 해시함수를 만들고 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법
• H에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1/m 로 만드려는 것이 목적
• 아래의 특정 해시함수 집합 H는 이를 가능하게 한다고 수학적으로 증명됐다.
  • 해시 테이블의 크기 m : 소수
  • 키값을 r+1 개로 쪼개기 : $k_0, k_1, …, k_r$
  • 0부터 m-1 사이의 정수 가운데 하나를 무작위로 뽑고, 분리된 키값의 개수(r+1)만큼 반복해서 뽑는다. 이를 $a = [a_0, a_1, …, a_r]$로 둔다.
  • 해시 함수 : $h_a(x) = \Sigma_{i=0}^r(a_i k_i mod m)$
  • a가 $m_{r+1}$가지이므로, 해시함수의 집합 H의 요소 수 또한 $m_{r+1}$개이다.

보안과 해시

• 키와 해시값 사이에 직접적인 연관이 없어 해시 값 만으로는 키값을 복원하기 어렵고,
• 해시 함수의 결과물은 고정된 길이의 숫자라 원래의 정보가 손실되어 원본데이터를 알기 어렵다.

5) MD5 (Message-Digest Algorithm)

• 임의의 길이의 값을 입력받아 128 비트의 고정 길이 해시값을 출력하는 알고리즘
• 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다.
• 패스워드 암호화에 많이 사용되고, 패스워드를 MD5로 해시해서 나온 값을 저장해둔다.
• 보안 관련 용도로 쓰는 것을 권장하지 않는다.

6) SHA (Secure Hash Algorithm)

• 미국 국립표준기술연구소에서 표준으로 채택한 암호학적 해시 함수
• 해시 길이에 따라 SHA-256, 384, 512 비트를 선택해 사용할 수 있고, 해시 길이가 길수록 안전하다.
• MD5보다 안전하지만 느리다.

3. 충돌 처리 알고리즘

• 해시 테이블은 해시 함수에 의해 정해지는 Index가 중복될 수 있다는 문제가 존재한다.

• 위와 같은 상황을 충돌(Collision)이라고 한다.
• Collision이 많아질 수록 검색에 필요한 시간 복잡도가 $O(1)$에서 $O(N)$에 가까워진다.

☝️ 여기서 잠깐!

충돌 처리 알고리즘이 왜 필요할까?

해시 함수를 무조건 1:1 로 만드는 것은 Array와 다를바 없고 메모리를 너무 많이 차지하게 된다. 따라서 Collision 을 최소화 하는 방향을 설계하고, 발생하는 Collision에 대비해 어떻게 대응할 것인가를 정하는 것이 더 중요하다.

1. Separate Chaining - 분리 연결법

• Linked List를 이용하는 방식

• 각 Index에 데이터를 저장하는 Linked List에 대한 포인터를 가지고, 충돌이 발생하면 그 Index가 가리키고 있는 Linked List에 노드를 추가한다.

• 데이터를 저장하는 구조는 Linked List만 사용하진 않는다.

  • Java8의 Hashmap의 경우 Index 노드가 6개 이하일 경우에는 Linked List를,
  • 8개 이상으로 늘어날 때는 Self-Balancing Binary Search Tree 구조로 데이터 저장 구조를 바꾼다.

  ☝️ 여기서 잠깐! WHY?

  Tree는 Linked List보다 메모리 사용량이 많고 데이터 개수가 적을 때 Tree와 Linked List의 Worst case 수행 시간 차이 비교가 의미없기 때문이다. 그러나 데이터 개수가 많아지면 Tree가 더 높은 성능을 보이게 된다.

  해시 함수 값이 균등분포일 때 Linked List에서는 get() 메소드의 기댓값은 E(N/M) 이고, Tree에서의 get() 메소드의 기댓값은 E(log N/M) 이므로 데이터의 개수가 일정 이상일 때에는 Linked List 대신 Tree를 사용하는 것이 성능상 이점이 있다.

  (해시 테이블의 크기 m, 실제 사용하는 키 개수 n)

  ✌️ 여기서 잠깐!

  왜 기준이 6개, 8개인가?

  변경에 소요되는 비용을 줄이기 위해서다. 기준을 6개, 7개로 두게 된다면 하나의 값이 추가되면 자료구조를 변경해야 한다. 그리고 바로 하나의 값이 삭제되면 또 다시 자료구조를 변경해야 한다. 이런 Switching 비용 때문에 2개라는 여유를 두고 기준을 잡은 것이다.

  🤟 여기서 잠깐!

  왜 RB트리를 사용할까?

  해시 테이블은 데이터 조회만 많이 일어나는게 아니기 때문에 rotation 같이 밸런스를 유지하기 위해 드는 오버헤드가 크다.

  RB 트리는 느슨하게 균형을 유지하면서 조회, 삽입, 삭제에 평균적으로 좋은 퍼포먼스를 보여주기 때문에 사용한다.

• 장점 : 테이블 확장을 늦출 수 있고, 간단하게 구현 가능.
• 단점 : 동일한 버킷에 chaining 되는 데이터가 많아져서 캐시 효율성 감소한다는 단점
  • 링크드 리스트 사용할 경우 최악의 경우 O(N)
  • 트리 활용의 경우 O(logN) 보장

2. Open Addressing - 개방 주소법

• 추가적인 메모리를 사용하지 않고 Hash Table의 빈 공간을 사용하는 방식

• 여러가지 구현 방식이 있다.

  • Linear Probing : 현재 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 저장 (선형 탐색으로 빈공간 찾기)

  • Quadratic Probing : 해시의 저장 순서 폭을 제곱으로 저장하는 방식

  • Double Hashing : 해시된 값을 한번 더 해싱 (다른 해시 함수 사용)

• 삭제할 경우 충돌에 의해 뒤에 저장된 데이터가 검색되지 않을 수 있다. 이를 방지하기 위해 삭제한 위치에 Dummy Node를 삽입한다.
• 장점 : 추가 메모리를 사용하지 않고 캐시 효율이 높다.
• 단점
  • 검색/삭제 시 Index의 키값이 찾고자 하는 키값이 아니라면 그 다음부터 선형 탐색을 실시해야 한다. (느리다!)
  • 해시 버킷을 채운 밀도가 높아질 수록 Worst Case 발생 빈도가 높아진다.

4. 해시 버킷 동적 확장(Resize)

• 해시 버킷의 개수가 적으면 Collision 으로 인해 성능 손실이 발생한다.

• Key-Value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다.

• 보통 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때다.

  load factor = 0.75

• Resizing은 더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 array에 hash를 다시 계산해서 복사해준다.

(Java) Hash Map

• Hash map은 기존 해시 테이블의 기능을 개선한 신 버전의 해시 테이블
• HashMap은 보조 해시 함수를 사용하기 때문에 Hash Table에 비해 해시 충돌이 덜 발생할 수 있어 성능상 이점이 있다.
  • 보조 해시 함수는 ‘키’의 해시 값을 변형해 해시 충돌 가능성을 줄이기 위한 것
  • HashMap은 먼저 Key 값을 hashcode()라는 메소드를 통해 해시값으로 바꾸고, 이를 버킷 사이즈인 M으로 나눈 나머지가 해시 버킷의 진짜 인덱스가 된다.
• 키에 대한 해시 값을 사용해 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 Associate Array.

Hash Table vs Hash Map

Hash Table	Hash Map
병렬 처리를 할 때 = 동기화 (멀티 스레드)	병럴 처리를 하지 않을 때 (단일 스레드)
Null 값 허용하지 않음	Null 값 허용
상대적으로 느리다	상대적으로 빠르다

질문

직접 주소화 방법을 알고 계시나요? 그 방법이 무엇인지, 장점과 단점을 설명해주세요.

직접 주소화 방법은 입력받은 key 값을 그대로 인덱스로 해 value를 저장하는 방법입니다. 키 값으로 바로 접근하기 때문에 속도가 빠르지만, 공간 효율성이 좋지 않고 키 값이 한정된다는 단점이 있습니다.

(추가) 해당 방법의 단점을 개선한 자료구조는 무엇인가요?

Hash Table 입니다. 해시 테이블은 해시 함수를 이용해 해시 값을 인덱스로 해서 value를 저장합니다. 해시 함수를 사용함으로 지정한 해시 테이블 크기만큼으로 키값이 변환되어 공간을 더 효율적으로 사용할 수 있습니다.

해시가 무엇인지, 시간복잡도는 어떻게 되는지 설명해주세요.

해시는 가변 길의의 데이터를 고정 길이의 데이터로 매핑한 값을 의미하고, 해시 테이블의 해시 변환, 검색, 삭제에 걸리는 시간 복잡도는 이론적으로 O(1)입니다.

하지만 만약 모든 해시 값이 하나로 귀결되는 최악의 경우에는 배열과 마찬가지로 O(N)이 됩니다.

해시테이블은 내부적으로 어떻게 작동하나요?

해시 테이블은 해시 함수를 이용해 입력된 값의 해시 값을 인덱스로 삼아 저장하고, 동적 배열로 구현되어 있어 사이즈를 늘릴 수 있습니다.

좋은 해시함수는 무엇인가요?

해시 함수는 인덱스를 설정하는 함수이므로, 좋은 해시 함수는 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 함수입니다.

아까 해시 테이블의 시간복잡도가 최악의 경우 O(n)이라고 했는데 충돌을 해결할 수 있는 방법은 무엇인가요?

우선 해시 함수를 먼저 점검할 것 같습니다. 해시 함수를 수정해 충돌을 최소화할 수 있는지 확인해보고, 그 다음으로 충돌을 대비하기 위해 Chaining 이나 Open Addressing 방법을 사용할 수 있습니다.

충돌 대비를 위한 Chaining 과 Open Addressing 설명

Chaining은 충돌이 된 경우, 링크드 리스트와 같은 자료구조를 사용해 노드를 추가하는 방식입니다.

Open Addressing은 충돌이 된 경우, 빈 해시 테이블에 저장을 하는 방법입니다. 빈 공간을 찾는 방법에는 linear 하거나, quadratic 하게 하는 등의 방법이 있습니다.

Open Addressing에서 선형 조사법, 이차 조사법의 문제점과 해결방안

선형 조사법과 이차 조사법은 데이터들이 뭉쳐서 저장되는 클러스터링 문제를 야기할 수 있습니다. 이를 해결하기 위해 빈 해시 테이블을 찾을 때 또 다른 해시 함수를 사용해 좀 더 거리의 랜덤성을 부여할 수 있을 것 같습니다.

본인이 충돌이 잦은 경우에 해시함수를 사용한다면 어떤 방식으로 해시테이블을 구성할건가요?

만약 해시 테이블이 75% 이상 차 있는 경우라면 테이블 사이즈를 증가해보고, 그래도 문제가 발생한다면 해시 함수를 살펴보거나 해당 데이터를 잘 담을 수 있는 다른 자료 구조가 있는지 찾아볼 것 같습니다.

만약 해시 테이블을 사용해야하는 경우라면 충돌 방지 기법 중 Chaining 을 이진 탐색 트리로 구현해 어떤 경우에도 O(logN) 안에 탐색할 수 있도록 구현할 것 같습니다.

추가 질문 (해시 테이블 외 질문!)

배열과 링크드리스트가 무엇인지 공통점과 차이점을 기준으로 설명해주세요.

배열은 연속된 메모리에 데이터를 저장하는 자료 구조이고, 링크드 리스트는 각 노드가 데이터와 포인터로 구성되어 포인터로 연결되어 있는 자료 구조입니다.

배열과 링크드 리스트 둘 다 데이터를 연속적으로 저장하기 위한 자료 구조입니다. 하지만 배열은 인덱스로 접근이 가능해 탐색이 O(1)로 빠른데 반해 링크드 리스트는 일반적으로 O(N) 시간을 갖습니다.

반면 배열은 크기가 고정적이고 메모리 공간이 낭비되지만 링크드 리스트는 유동적이며 메모리 공간을 낭비하지 않는다는 차이점이 있습니다.

(추가) 배열은 접근 속도가 빠르다고 했는데, 어떻게 그렇게 빠른 접근 속도를 가지나요?

배열은 연속된 메모리에 데이터를 저장하기 때문에 인덱스를 통해서 접근할 수 있어 배열의 특정 위치에 있는 데이터를 한 번에 접근할 수 있습니다.

(추가) 수정할 때 시간복잡도는 어떻게 되나요?

특정 위치의 데이터의 값을 수정한다면 O(1) 이 되고, 삽입과 삭제와 같은 작업이라면 특정 위치에 삽입/삭제 후 나머지 데이터를 뒤로 밀어주거나, 당겨주는 작업이 필요해 일반적으로 O(N) 이 됩니다.

(추가) 배열에서 인덱스 값 어떻게 계산하나요?

int형 배열인 경우에는 4바이트씩 메모리 주소가 떨어지게 되고, 해당 메모리 주소마다 인덱스를 0부터 1씩 증가시켜 계산합니다.

그러면 결국 링크드 리스트는 삽입, 삭제, 탐색 모두에 O(n)의 시간복잡도를 가지게 되는데 왜 굳이 사용하는 걸까요?

배열은 고정된 크기를 갖기 때문에 미리 원소의 개수를 알 수 없을 때 메모리를 효율적으로 사용하기 위해 사용합니다.

(추가) 어떤 경우에 배열을 사용하고 어떤 경우에 링크드 리스트를 사용할까요?

데이터 개수가 정해져있고, 검색이 많이 필요한 경우에는 배열을, 데이터 크기가 정해져 있지 않고 삽입과 삭제가 자주 일어날 때는 링크드 리스트를 사용하면 좋을 것 같습니다.

배열과 링크드 리스트는 각각 메모리의 어떤 영역에 저장될까요? (이어서 메모리 영역 묻기)

배열은 컴파일 단계에서 stack 이나 data영역에 메모리 할당이 일어나고, 링크드 리스트는 런타임에 새로운 노드가 추가될 때마다 heap 영역에서 할당되어 저장됩니다.

만약 동적 배열이라면 heap 영역에 할당될 것입니다.

Priority Queue에 대해서 들어보셨나요? 어떻게 구현하나요?

네, 큐는 먼저 들어온 순서대로 나가는 FIFO 형 자료구조 입니다. 우선순위 큐는 들어온 순서대로가 아닌 우선 순위가 높은 순서대로 나가는 형태의 자료구조입니다.

구현은 완전 이진트리의 일종인 heap으로 구현합니다.

(추가) 왜 그렇게 구현하나요?

최소 힙이나 최대 힙을 사용하면 데이터를 넣는 것만으로도 이미 우선 순위 큐에 맞게 정렬이 되기 때문입니다.

References

• wiki.hash/해시

• Hash-Table
• JaeYeopHan/Interview…/Hash Table
• ratsgo/hash table

• Hash 함수

• CS-자료구조-해시-테이블직