[Data Structure] Hash Table, Graph 정리

• Hash Table
  • Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 저장속도를 갖는다
  • 특정한 값을 search 할 때, 고유의 인덱스로 접근하게 되므로 O(1)이다.
  • 그러나 인덱스로 저장되는 key값이 불규칙하다
  • 그러므로 특별한 알고리즘을 사용하여 데이터와 연관된 고유한 숫자를 만들어 이를 인덱스로 사용한다.
  • 그러므로 삽입,삭제(끼어든다는 개념이 없음)에 대해 추가적인 비용이 필요없다
  • Hash Function (=해시 함수, hash method)
    • 해당 함수에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 한다
    • Collision : 서로 다른 두 개의 키가 같은 인덱스로 hashing 되면 같은 곳에 저장할 수 없게 된다.
    • Collision이 일어나지 않은 좋은 hash function이란?
      • 키의 일부분을 참조하지 않고 키 전체를 참조하여 해쉬 값을 만들어내는 함수
        • 키의 특성에 따라 좌지우지됨
      • Collision을 최소화 하는 방향으로 설계 및 Collision에 대한 대응이 더 중요하다 (than 무조건 1:1로 만드는 것 보다)
      • Collision이 자주 일어나면 시간 복잡도가 O(n)이 되어버리므로 배열을 쓰는 것과 다를바가 없다.
    • 충돌 해결 방법
      • Open Address 방식 (개방주소법)
        • 해시 충돌이 발생할 경우, 다른 해시 버킷에 해당 자료를 삽입
        • 최악의 경우, 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치로 되돌아오는 경우
        • 탐색 위치 찾는 방법
          • Linear Probing : 순차적으로 탐색하며 비어있는 버킷을 찾을때 까지 계속 진행된다.
          • Quadratic probing : 2차 함수를 이용해 탐색할 위치를 찾는다.
          • Double hashing probing : 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. (연산량 많음)
      • Separate Chaining 방식 (분리 연결법)
        • Open Address 방식보다 빠름
          • Open Address 의 경우, 해시 버킷을 채운 밀도가 높아질 수 록 Worst case 발생 빈도가 높아짐
          • Separate Chaining 의 경우, 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정 → Worst case 빈도 수 줄이기
        • 구현 방식</aside>
          • Linked List 사용 : 각각의 버킷을 연결 리스트로 만들어 충돌이 발생할 경우 해당 버킷의 리스트에 추가하는 방식
          • RBT 사용 : 연결리스트 대신해 트리를 사용
          Key-value 개수가 6개 or 8개를 기준으로 한다8개 이상 : 트리
        • 7이 없는 이유는 Switching 비용이 너무 많기 때문에 기준을 2 차이로 두고 사용
        • 6개 이하 : 연결리스트
        • <aside> 💡 둘 중 어떤 것을 사용할지 : 하나의 해시 버킷에 할당된 key-value 쌍의 개수가 적을 경우 연결리스트 , 많으면 트리 (트리가 메모리를 더 많이 사용하므로)
      • 그래서 차이점이?
        • Open Address 방식은 연속된 공간에 데이터 저장, SC에 비해 캐시 효율이 높다
        • 데이터의 개수가 적을 경우 Open Address가 성능이 좋음
          
          
          
• Graph
  • 정점과 간선의 집합
  • 트리 또한 그래프이며, 그 중 사이클이 허용되지않는 그래프를 말한다
  • 용어정의
    • Undirected Graph
      • Degree : 각 정점에 연결된 Edge의 개수 Outdegree : 정점으로부터 나가는 간선의 개수 Indegree : 들어오는 간선의 개수
    • Directed Graph
    • Weight Graph : 가중치 정보를 두어 구성한 그래프
    • Sub Graph : 본래 그래프의 일부 정점 및 간선으로 이루어진 그래프
  • 구현 방법
    • 인접 행렬 (adjacent matrix) : 정방 행렬을 사용
      • 해당하는 위치의 값을 통해 간선간의 연결관계를 O(1)로 파악할 수있음
      • 정점 개수와는 무관하게 V^2의 Space Complexity를 가진다.
      • Dense Graph에 사용 : 정점 보다 간선 개수가 더 많은 그래프
    • 인접 리스트 (adjacent list) : 연결 리스트를 사용
      • 간선의 주변 리스트를 모두 확인해야하므로 간선 간의 연결 확인이 오래걸림
      • O(E+V)
      • Sparse Graph에 사용 : 간선 보다 정점이 더 많은 그래프
  • 그래프 탐색 방법
    • DFS - 깊이 우선 탐색
    • BFS - 너비 우선 탐색

 

 

지식 출처

https://www.youtube.com/channel/UCReNwSTQ1RqDZDnG9Qz_gyg/featured

쉬운코드