---
# System prepended metadata

title: 利用兩個Hash table 建圖

---

# 利用兩個Hash table 建圖
教授上課時提到除了相鄰矩陣跟linked-list外，還有一種利用兩個Hash table 建圖的方法，結合了省空間+檢查邊是否存在只需O(1) time complexity的優點。我從沒聽過這種方法，覺得有趣便嘗試用目前所學知識，使用C++試著實作出來看看，並成功進行插入、刪除、查詢的基本操作。
```C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
    unordered_map<int,unordered_map<int,int>> graph;

    //新增邊
    //time complexity: O(1)
    graph[0][3]=1;
    graph[2][1]=1;

    //刪除邊
    //time complexity: O(1)
    graph[2].erase(1);

    //檢查是否有這條邊
    //time complexity: O(1)
    if(graph.count(0) && graph[0].count(3)) cout<<"have (0,3)"<<endl;
    if(graph.count(2) && graph[2].count(1)) cout<<"have (2,1)"<<endl;
}

```