Hash Table, Graph
1. Hash Table
내부적으로 배열로 구현되어있다. key, value와 같이 한 쌍으로 데이터를 저장하며, key는 특정한 Hash Function에의해 결정된다. 각각의 데이터는 고유한 key를 가지고 있기 때문에, 일반적으로 탐색 시간은 O(1)만큼의 시간이 소요된다. 하지만, Hash Function이 다른 데이터에대해서 고유한 키 값이 아닌 중복되는 키값을 도출해낼 경우, 충돌이 발생하게되기 때문에 항상 탐색에대한 시간복잡도가 O(1)은 아니다. (Python에서 Dictionary, JAVA에서 Hashmap으로 구현되어있음)
1-1) Hash Function
데이터에대해서 고유한 Key값을 만들어주는 함수이다. 데이터 일부만을 사용하는것이 아닌 데이터 전체를 Hash Function에 파라미터로 넘긴 후 반환된 값을 Key로 사용하는것이 충돌을 일으킬 확률을 낮춰준다.
아무리 많은 데이터를 넣어도 항상 고유한 Key값을 보장하는 Hash Function은 존재하지 않으므로, 충돌이 일어난다고 가정을 한 후 충돌을 어떻게 해결할지를 생각하는게 가장 좋은 방법이다.
1-2)Resolve Conflict
위와같은 충돌 현상을 해결하는 방법에는 두가지가 있다.
Open Address
해시 충돌이 발생하면, 다른 해시 버킷을 찾아 삽입하는 방식. 다른 해시 버킷을 찾는 방법에도 세가지가 있다.
Linear Probing : 순차적으로 탐색해 빈 해시 버킷을 찾아낸다.
Qudratic Probing : 2차 함수를 이용해 탐색 할 위치를 찾는다. ex) H를 Hash값이라고 할 때, H + 1^2, H + 2^2와 같은 형태
Double Hashing Probing : 2차 해시 함수를 두어, 첫번째 해시 함수에서 충돌이 발생하면 2차 해시 함수를 이용해 Key값을 재설정한다.
Seperate Chaining
Key값이 1개의 데이터를 저장하는것이 아니라, 1개의 Linked List나 Tree를 저장하는 방식. 해시 충돌이 일어나면 해당 Key값에 할당된 Linked List나 Tree에 데이터를 추가한다.
Linked List 방식은 구현이 쉽고 삽입, 삭제도 쉽지만 데이터의 개수가 늘어날 수록 삽입, 삭제에대한 시간복잡도가 Tree형식에비해 크기 때문에 성능상 손해를 볼 수 있다.
Tree 방식은 Linked List 방식에비해 빠르지만, 구현이 비교적 어렵고 메모리를 많이 사용하게 되므로 데이터 개수가 많을 경우에 유리하다.
적절한 데이터의 개수 -> 6개 이하 : Linked List, 8개 이상 : Tree
Seperate Chaining 방식에서는 보조 해시 함수도 사용하는데, key의 해시 값을 변형하여 해시 충돌 가능성을 줄여준다.(2차 해시 함수)
Open Address 방식이 데이터를 연속적으로 저장하게되므로 Seperate Chaining 방식보다 비교적 빠르지만, 가용 해시 버킷의 수가 훨씬 빨리 줄어들게 되므로 테이블을 자주 확장하게 된다. 데이터의 개수가 적다면 Open Address, 데이터의 개수가 많다면 Seperate Chaining을 이용하는것이 좋다. (앞으로 추가될 데이터의 수도 생각하보면 될듯하다.)
1-3) Hash bucket Resize
해시 버킷이 할당되어가면, 점점 충돌이 발생 할 확률이 늘어나게 된다. 그래서 충분한 수의 해시 버킷들이 할당되게되면 해시 버킷의 수를 두배로 늘리게 된다. 적정한 할당률은 75%이다. 이 할당률을 load factor라고 함.(0.75)
2. Graph
정점(Vertex), 간선(Edge)의 집합.
2-1) Directed graph, Undirected graph
Directed graph는 간선에 방향성이 있는 그래프이고, Undirected graph는 간선에 방향성이 없는 그래프이다.
각 정점에 연결된 간선의 수를 Degree라고 하는데, Directed graph는 정점에서 뻗어나가는 간선과, 정점으로 들어오는 간선 총 두 경우가 존재하므로 Outdegree, Indegree 두 Degree를 갖고있음.
추가적으로 Edge에 가중치가 들어있는 가중치 그래프라는 개념도 있음.
2-2) adjacency matrix vs adjacency list
그래프의 구현 방식에는 정방 행렬을 사용하는 인접 행렬(adjacency matrix), 연결 리스트를 사용하는 인접 리스트(adjacency list)가 있다.
정점의 개수를 V이고 간선의 개수를 E라고 할 때, 인접 행렬은 0과 1로 이루어진 배열들로 구현되므로 정점의 연결관계를 시간복잡도 O(1)만에 알 수 있지만, 인접 리스트는 정점을 먼저 찾은 후 리스트에 접근해야하므로 각 상황마다 다르겠지만 연결관계를 구하려면 인접 행렬 방식에비해 더 많은 시간을 소요한다.
ex )
adjacency list 방식, undirected graph
3과 4가 연결되어있는지 탐색
vertice, edges (ArrayList<ArrayList<Integer>>) : ((1, 2, 3, 4), (0), (0, 3, 4), (0, 2, 4), (0, 2, 3))
첫번째 index : 0, 1, 2, 3, 4(vertices)
두번째 index : Edges
총 vertices의 개수 : 0, 1, 2, 3, 4
3과 4가 연결되어있는지 알기 위해서는 3이나 4에대한 인접리스트중 하나만 탐색하면 된다.
Hashmap을 이용해서 연결 리스트처럼 구현 할 경우, Hashmap에 value값을 ArrayList 형식으로 저장한다면 최악의 상황에서 O(E) 시간만에 연결관계를 알 수 있다.
어떻게 구현하나에 따라서 달라질듯하다.
2-3) 그래프 탐색
DFS(Depth First Search) vs BFS(Breadth First Search)
DFS
Stack을 이용해 구현한다. 갈 수 있는 마지막 정점에 도달했음에도 아직 탐색 할 정점이 존재한다면 다시 돌아가야하기 때문이다.(LIFO)
BFS
Queue를 이용해 구현한다. 주로 최단 경로를 구할 때 사용되며, 목적지가 정해져있을 경우 최단경로이기는 하나 구한 경로의 도착지가 해당 목적지가 아닐 수 있기 때문에 주의해서 구현해야한다.