Linked List, Hash Table

nahsooyeon·2021년 1월 26일
0

1. Linked List

크기가 동적인 자료 구조
노드(Node)라는 요소로 구성되어있고
노드의 연결로 이루어져있다.

  • head: 연결 리스트의 첫번째 노드
  • tail: 연결 리스트의 마지막 노드

각 노드는 다음 노드로 갈 수 있는 주소값을 가지고 있다.

2. Hash Table

  • 키, 값, 쌍(튜플)을 저장하고 있는 동적 자료 구조(배열)
  • 키를 해쉬 함수(Hash Function)라는 함수를 통해 특정 숫자값의 인덱스로 변환한다.
  • 해시 테이블은 n개의 버켓(bucket)으로 구성되어있으며,
    이 버켓 안에는 키와 값을 담은 튜플(tuple)이 들어있다.
    중복된 인덱스 값을 가진 튜플이 입력될 경우, 같은 인덱스를 가진 버켓에 추가된다.
  • 해시 테이블은 저장된 쌍(튜플)의 개수에 따라 차지하고 있는 메모리를 유동적으로 줄이거나 늘릴 수 있다.
    예를 들어, 해시 테이블에 저장된 튜플의 개수가 bucketNum의 75%를 넘는 경우, 버켓의 수를 2배로 늘리고, 25%보다 작아지는 경우 버켓 개수를 절반으로 줄인다.
  • 버켓의 개수가 변경될 경우, 다시 메모리에 정렬하는 것을 해싱이라고 한다.

0개의 댓글