Linked List
- 연결 리스트는 배열보다 메모리를 더 효율적으로 사용할 수 있습니다.
- 삽입, 제거가 많은 작업 → 연결 리스트가 좋습니다.
- 메모리 랜덤 접근이 많은 작업 → 배열이 좋습니다.
- 단일 연결 리스트에서 무수히 많은 연결 리스트 노드들은 단 1번으로 head의 포인터를 끊는다면 나머지 노드들은 가비지 컬렉터로 없어진다.
- 연결 리스트는 노드가 데이터와 포인터(다음 또는 이전 노드)를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.
- 연결 리스트는 노드들의 중간 지점에 노드를 추가 및 삭제를 할 때 시간 복잡도가 O(1)을 가지는 장점이 있습니다.
- 하지만 특정 위치의 노드를 찾을 때엔 O(n)의 시간 복잡도를 가진다는 단점이 있습니다.
연결 리스트 종류
- 단일 연결 리스트
- 이중 연결 리스트
- 원형 연결 리스트
- 그리고 첫 번째 노드를
head, 마지막 노드를tail라 부릅니다. - 연결 리스트를 실생활에서 볼 수 있는 예는 미디어 플레이어로 들 수 있습니다.
- 이중 연결 리스트로 되어 있다면 이전 미디어나 다음 미디어로 건너 뛸 수 있습니다.
- 해당 노드에 다음 노드를 가르키고 있다면 다음 미디어를 시작할 수 있습니다.
- 미디어를 원하는 곳에 추가할 수 있습니다.
- 원형 연결 리스트를 이용해 head가 tail을 가르키고 있기에 미디어가 끝나지 않고 반복 재생할 수 있습니다.
Hash Table
- 해시는 해시 함수로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하여 얻어지는 값을 말합니다.
- 키와 값을 한 쌍으로 저장할 수 있는 자료구조입니다.
- 해시 맵은 데이터를 가져오거나, 추가 또는 삭제할 때 O(1)이다.
- 그렇기에 양이 많은 데이터가 있는 파일에서 검색이 빠릅니다.
- 키를 저장할 때 메모리 공간을 덜 사용할 수 있도록, 키를 Hash Function을 통해 특정 숫자 값의 인덱스로 변환됩니다.
- 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기로 유지합니다.
- Bucket : key에 해당하는 Value들의 묶음
해시 함수의 특징
- 어떤 값이 들어오더라도 고정된 길이의 해시를 얻습니다.
- 입력 값에 하나라도 예를 들어, 공백이나 온 점 하나가 추가된다면 전혀 다른 해시를 얻습니다.
- 출력된 값을 토대로 입력 값을 유추할 수 없습니다.
Collisions
- 해시 함수가 서로 다른 두 개의 입력 값에 대해 동일한 출력 값을 내는 상황을 의미합니다.
- 이 충돌은 해시 함수의 효율성과 이점을 떨어뜨립니다.
Hash Table Collision Handling
체이닝(Chaining)
- 연결 리스트로 데이터들을 연결하는 방식입니다.
- 체이닝은 버킷이 가득 차더라도 연결 리스트로 계속 연결되기에, 데이터의 주소 값이 바뀌지 않습니다.
개방 주소법(Open Addressing)
-
해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식입니다.
Chaining과 Open Addressing의 장점
Chaining
→ 복잡한 계산식의 필요성이 Open Addressing보다 적습니다.
→ 해시 테이블이 채워질수록, Lookup 성능 저하가 선형적으로 발생합니다.Open Addressing
→ 삽입, 삭제시 오버헤드가 적습니다.
→ 저장할 데이터가 적을 때 좋습니다.
참조
반가워요! 사람을 도우는 웹 개발자로 성장하기! :)