Linked List, Hash Table

1. Linked List

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

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

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

2. Hash Table

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