Linked List, Hash Table

Linked List

단일 연결 리스트

이중 연결 리스트

단일 연결 리스트는 노드가 바로 다음 노드 방향으로 단일 연결만을 갖는 구조이다.
때문에 탐색 방향이 한쪽으로 밖에 진행되지 않는다.

이중 연결 리스트는 노드가 앞뒤의 노드와 연결된 구조이다.
양쪽으로 탐색이 가능하기 때문에 탐색의 시작을 처음과 끝 둘 중에 하나로 지정할 수 있다.

연결리스트의 임의의 위치에 노드를 추가하거나 삭제할 때 O(1)의 상수시간만큼의 시간 복잡도를 갖는다.
배열은 추가와 삭제에 대해 O(N)의 선형시간 만큼의 복잡도를 갖는다

연결리스트는 인덱스를 갖지 않는다.
그렇기 때문에 특정 데이터를 리스트에서 조회하고자 할 경우, 처음부터 전체를 확인해야 하며 O(N)의 시간복잡도를 갖는다.

	조회	삽입	삭제
Linked List	O(N)	O(1)	O(1)

Hash Table

152번 인덱스에서 충돌이 일어났다

해시 맵이라고도 하는 해시테이블은 key와 value를 저장하는 자료구조다.

키를 저장할 때에 "해시 함수"라는 함수를 통해 인덱스를 지정한다.
해시 함수는 같은 입력에 대해서 같은 출력값을 보장한다.
하지만, 모든 입력값에 대응할 만큼 인덱스를 보유하고 있지 않기 때문에
다른 입력값에 대해 같은 출력값이 나오는 경우가 있다.
이것을 "해시 충돌"이라고 부른다.

해시 충돌이 일어났을 때 충돌을 핸들링하는 방법은 두가지가 있다.

1. open address

충돌이 발생했을 때 다른 해시 버킷에 데이터를 삽입하는 방식.

충돌시 데이터를 넣을 버킷을 찾는 방식은 세가지가 있다.

1. Linear Probing
   순차적으로 한 칸씩 다음 칸을 탐색하며 비어있는 버킷을 찾을 때 까지 반복.
   비어있는 버킷을 찾으면 값을 삽입.

2. Quadratic Probing
   순차적으로 비어있는 버킷을 찾는것은 동일하나, 탐사 폭이 제곱수로 늘어난다.
   충돌이 일어나면 1^2칸 옮겨서 탐색하고 또 충돌하면 2^2칸 옮겨서 탐색하는 방식을 반복한다.

3. Double Hashing Probing
   하나의 해시 함수에서 충돌이 발생하면 2차 해시 함수를 이용해 새로운 인덱스(버킷)를 할당한다.
   위 두가지 방법에 비해 많은 연산량을 필요로 한다.

2. separate chaining

- 연결리스트를 사용 (Linked List)
각각의 버킷을 연결리스트로 만들어 충돌이 발생하면 해당 버킷에 list로 추가하는 방식.

- 트리를 사용하는 방식 (Red-Black Tree)
기본 알고리즘은 Separate Chaining과 동일하고, 연결 리스트 대신 트리를 사용하는 방식이다.데이터의 개수가 적다면 연결리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문.

Open Address vs Separate Chaining

두 방법 모두 Worst Case에서 O(M)이다. 하지만 Open Adress 방식은 연속된 공간에 데이터를 저장하기 때문에
다른 방식에 비해 캐시 효율이 높다. 따라서 데이터의 개수가 충분히 적다면 Open Adress방식이 성능이 좋다.

그리고 Open Address 방식은 다른 방식에 비해 버킷을 계속해서 사용한다.

따라서 Separate Chaining 방식은 테이블의 확장을 보다 늦출 수 있다.

Separate Chaining 방식을 사용할 때 보조 해시 함수를 사용해서 key의 해시 값(출력값)을 변형하여 충돌 가능성을 줄이기도 한다.

해시 테이블은 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.
(데이터가 전체 크기의 25% ~ 75%를 넘지 않도록 유지)

	조회	삽입	삭제
Hash Table	O(1)	O(1)	O(1)

참고 : k39335.tistory.com/18