Data Structure - Linked List, Hash Table

Linked List 연결 리스트

• 크기가 동적인 자료 구조
• 자료구조를 구성하는 요소 (Node)의 연결로 이루어진다. (배열에서는 element라고 부르고 linked list 에서는 node 라고 한다.)
• 연결 리스트의 어떤 임의의 지점에 데이터의 추가와 삭제 시 O(1) (상수시간) 의 시간 복잡도를 갖는다.
  : 이는 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과 다른점이다.
• 각 노드는 인덱스를 갖지 않는다
  : 그래서 특정 데이터를 연결 리스트에서 검색할 때 처음부터 전체 연결 리스트를 조회해야 하고
  이는 O(n) (선형시간)의 복잡도를 요한다.

 

속성

head : 맨 앞

tail : 맨 뒤

current : 현재 탐색 위치

before : 현재 위치 전

num_of_date : 데이터의 총 갯수

 

메소드

append( ) : 맨 뒤에 노드를 추가한다.

delete( ) : 현재 노드를 삭제한다.

first( ) : 맨 앞의 노드를 탐색한다.

next( ) : 다음 노드를 탐색한다.

 

종류

Singly-Linked List

Doubly-Linked List

Circular Linked List

 

Singly-Linked List (단일 연결 리스트)

각 노드에 데이터 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

• 장점
  • 다이나믹한 사이즈를 가질 수 있다.
  • 데이터의 추가와 삭제가 용이하다.
• 단점
  • 값을 조회할 때 무조건 앞에서부터 차례대로 해야 한다.
  • 노드 외에 포인터를 위한 공간이 필요하다.

Doubly-Linked List (이중 연결 리스트)

포인터 공간이 두 개 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

• 활용 예 : 뒤로가기, 앞으로 가기, 다음곡 재생, 플레이 리스트에 새 노래 저장

Circular Linked List (단순 원형 연결 리스트)

일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

• 활용 예 : PC에서 여러 어플리케이션이 켜져 있는 경우, multiplayer games

 

Linked List 의 장점과 단점

장점

늘어선 노드의 중간 지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다.

 

단점

인덱스를 갖지 않기 때문에 특정 위치의 데이터를 검색해 내는 데에 O(n) 의 시간이 걸린다.

 

 

Hash Table

 = 해시 맵

키, 값 쌍을 저장하고 잇는 자료 구조이다.

 

Hashing

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 과정을 hashing이라고 한다.

이때 매핑 전 원래 데이터의 값을 key, 매핑 후 데이터의 값을 hash value 라고 한다. 

 

해시 함수의 키

key 값을 자연수로 가정한다. 만약 character 이나 string의 형태이면 ASCII table 에 따라 자연수 형태로 변형하여 사용한다.

 

Hash Collision

해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록 키를 해시함수를 통해 특정 숫자값의 인덱스로 변환한다.

그러다보니 동일한 hash value를 가지는 복수의 key가 생겨서 같은 공간에 저장되는 문제가 발생하는데 이를 collision 이라고 한다.

 

• Resolution

이를 해결하기 위해 chaining을 하게 되는데, 각 슬롯을 Linked List 형태로 연결하는 것이다.

이 때 key와 함께 value를 명시해 줌으로써 구분할 수 있다.

 

하지만 최악의 경우, 모든 key가 하나의 슬롯으로 해슁되는 경우 길이가 n인 이중 연결 리스트가 생성된다.

 

 

최악의 경우인 O(n)이 발생하는 이유는 크게 2가지이다.

1. 해시 테이블이 커질 때 
: 해시 테이블이 커지면 rehashing을 해야 하는데 그럼 기존에 있던 것을 두 배로 커진 array에서 rehashing을 해야한다.

 

2. 모든 키(n개)가 하나의 버킷에 들어간 경우 키에 해당하는 값을 찾기 위해 시간복잡도 O(n)이 발생할 수 있다.
     (즉, 최악의 경우 해시테이블은 Linked List 만큼의 시간복잡도 O(n) 이 발생할 수 있다. 그렇게 되면 일반적인 리스트에 저장하는 것과 성능이 동일해질 것)

 

 

 

그렇다면 input 사이즈가 커짐에 따라 어떻게 O(1)의 시간 복잡도를 유지할 수 있을까?

 

 

Hash Table Resizing

해시 테이블을 필요에 따라 메모리 크기를 늘리지만, 가능한 작게 유지한다.

해시 테이블은 tuple 갯수가 storage 크기의 25% - 75% 사이일 때 가장 효율적으로 운영된다. 따라서 tuple의 갯수가

• > 75% 일 때 : storage size를 두 배로 늘리고
• < 25% 일 때 : storage size를 절반으로 줄인다.

용어

storage : 키에 해당하는 값들의 묶음 (the top array level)

bucket : storage에 collision을 갖고 있는 것을

tuple : 각 bucket이 담고 있는 데이터를 tuple이라고 한다. ( index 0은 key, index1은 value)

Hashing : 임의의 길이의 데이터를 해시 함수를 거쳐 고정된 길이의 데이터로 매핑하는 일련의 과정을 말한다.

 

해시 함수의 특징

1. 갖고 있는 배열의 크기 (0 to arr.length-1) 안에서 값이 나와야 한다.
2. 언제든지 일정한 값을 리턴해야 한다.
3. 값을 저장하지 않고 바로바로 반환해야 한다.

좋은 해시 함수

모든 값이 골고루 들어가서 충돌을 최소화하는 함수 (simple uniform hashing)

 

대표적인 해시 함수 modular function (나머지 함수)

key 값으로 m을 나누고 나머지를 이용한다.

  h(k) = k mod m         // mod : modular

 

ex ) k = 100, m = 12  

       h(k) = 100 mod 12 = 4

 

 

*추가 공부할 내용

효율적으로 m을 선택하는 방법

2의 지수승, 2의 지수승 -1 은 좋지 않다.

2의 지수승에 너무 가깝지 않은 소수를 선택하는 것이 좋다.

 

참고 : SKplanet Tacademy 유튜브 채널

 

 

해시테이블에서 값이 저장되는 공간을 어떻게 배열만 이용해서 디자인 할 수 있을까