TIL Linked List & Hash Table

코드스테이츠 45일차

자료 구조 두번째 시간으로 연결 리스트와 해시 테이블에 대해 배우게 되었다.
머리가 터질것 같다...

연결 리스트와 해시 테이블을 나눠서 포스팅을 할까 고민했지만
같이 올리는게 더 나을 것 같다
내일은 또 더 많은 자료구조에 대해 배우게 될 것 같으니 말이다

새로 배운 것들

Linked List(연결 리스트)

연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조이다.

이름에서 알 수 있듯 데이터를 담고있는 노드들이 연결되어있는데
노드의 포인터가 다음이나 이전의 노드와 연결을 담당하게 된다.

연결 리스트의 종류로는 단일 연결 리스트와 이중 연결 리스트등이 있다.

연결 리스트의 특징

• 배열보다 데이터의 삽입, 삭제가 용이하다
• 마지막 포인터는 Null을 가리킨다.
• 프로그램이 수행되는동안 크기가 동적으로 변한다.
• 포인터를 위한 메모리가 필요하다(배열보다 많은 메모리 필요)
• 검색을 할때에 순차적으로 순회하기때문에 시간이 오래 걸린다.

연결 리스트의 종류

• 일방향 연결 리스트

연결 리스트의 일반적인 구조로 위의 설명이 이 구조를
설명하고 있는 것이라고 생각하면 된다.

일방향 연결 리스트의 경우 이중 연결 리스트보다
메모리를 적게 차지하지만 이전 노드로 돌아갈 수 없다는 특징이 있다.

• 이중 연결 리스트

노드에 포인터가 두개 있어 이전 데이터에도 접근할 수 있다.
하지만 포인터가 두개인 만큼 메모리도 두배로 차지한다.

• 원형 연결 리스트

마지막 포인터가 Null을 가리키는것이 아닌 head를 가리킨다.
37에서 99로 가야한다면 다시 처음으로 12부터 가야된다.
데이터를 순회해야될 때 만들면 좋다.

실생활에서의 연결 리스트

우리가 음악을 들을때 다음 곡, 이전 곡 버튼이 연결 리스트로 볼 수 있을 것 같다. 이 외에도 이미지 파일을 볼때 다음 이미지, 이전 이미지 등도 있을 것이고 가장 대표적으로는 지하철 역도 연결리스트로 볼 수 있겠다.

지하철 역 하니 열차도 연결 리스트로 볼 수 있을 것 같다.

연결 리스트의 메소드

insertFirst()

연결 리스트의 맨 앞에 데이터를 추가합니다.

addToTail()

연결 리스트의 마지막에 데이터를 추가합니다.

getNodeAt()

인덱스를 넣었을 때, 그 인덱스가 어떠한 값을 가지고 있는지 반환합니다.

contains()

해당 값이 연결 리스트에 있는지 true와 false로 반환합니다.

indexOf()

해당 값이 어떤 인덱스에 있는지, 인덱스 값과 -1로 반환합니다.

remove()

해당하는 연결 리스트의 값을 지웁니다.

size()

연결 리스트의 사이즈를 반환합니다.

Hash Table(해시 테이블)

연관 배열을 이용하여 키에 결과값을 저장하는 구조이다.
해시 함수를 사용해 index를 버킷이나 슬롯에 배열로 저장한다.

어떠한 키와 값을 넣었을 때 내부적으로 이 데이터를 분류하여
저장된 장소에 키를 넣고, 키를 다시 호출했을 때 값을 반환할 수 있게 하는 것을 해시테이블이라고 한다

해시 테이블의 특징

• 내부에 hash function(해시 함수)를 가지고 있고 해시 함수를 통해 데이터를 분류하여 정수로 만들고 그 정수가 인덱스 값이 되어 데이터가 인덱스 값에 저장이 된다.
• 인덱스 값이 유한하다는 가정 하에 해시 함수를 실행하여
  인덱스 값을 설정하기 때문에 배열의 크기가 유동적이지 않다.

hash funtion(해시 함수)

해시테이블에 키와 값을 넣으면 키를 사용해 인덱스 값을 만들어내는 함수를 말한다.

여기서 키를 해시 함수에 넣고 출력되는 과정을 hashing(해싱)이라고 한다.

이런 해시 함수는 정보를 암호화 하거나 자료를 정리하기 위해 일련의 값으로 만들어 내는 대에 특화되어 있다.

function hashfn(key) {
  let pw = Math.floor(key.length / 2);
  return pw;
}

간단하게 만든 해시 함수

해시 함수의 특징

• 배열의 크기 안에서 값이 나와야 한다
  배열 안에 넣을 것이기 때문에 지정된 배열을 벗어난 인덱스에 넣을 수 없다.
• 똑같은 데이터를 넣었을 때 같은 값이 나와야 한다.
• 해시 함수 내에 어떠한 값도 저장할 수 없다.
• 들어오는 데이터를 숫자로 바꿔준다.
• 해시 충돌이 일어날 수 있다.

해시 충돌이란 문자열로 예를 들었을 경우
'apple'과 'hello'는 문자열로는 다르지만 문자열의 길이는 같기 때문에 해시 함수에서는 해당 문자열을 같은 문자열로 인식해 충돌이 일어나는 현상을 말한다.

해시 충돌을 피하는 방법으로는 크게 두가지가 있다.

• Open addressing: 다른 여분의 인덱스에 저장하기
  선형 탐사: 만약 1번 칸이 비어 있다면 2번칸에 저장하는 방식
  이중 해시: 해시 함수를 2개 만들어 충돌이 일어날경우
  두번째 함수를 사용해 새로운 인덱스로 조정하는 방식

• Close addressing: 충돌이 일어나도 해당 위치에 저장하기
  버켓: 2차원 배열을 만들어 저장하는 방식 충돌이 일어나면 2차원 배열로 쌓이게됨
  체이닝: 충돌된 값들을 연결 리스트로 연결

해시 테이블의 장단점

장점

• 배열에 비해 삭제 및 탐색이 쉽고 빠르다.
• 해시 충돌이 없다면 O(1)의 상수 시간에 가깝고,
  해시 충돌이 많다면 O(n)에 가까워진다.

단점

• 해시 함수를 사용할 때 추가적인 연산이 필요하다.
• 해시 함수 특성상 충돌을 일으킬 수 있다.
• 적은 데이터를 가지고 해시 충돌을 연결 리스트로 만들면
  캐시 효율이 떨어진다.

해시 테이블 안의 데이터가 25% ~ 75% 정도 차 있을 때
효율이 가장 좋기 때문에 저장 공간을 맞추기 위해 resizing 할 수 있다.

다만 해시 테이블을 늘리거너 줄일 땐 그 인덱스에 맞춰
해싱을 다시 해줘야되는 번거로움을 가지고 있다.

해시 테이블의 구조

• keys
  입력받은 데이터를 hash function(해시 함수)를 통해 해싱함

• buckets
  데이터를 저장하는 공간(storage) 여기에 저장된 데이터는 읽기만 가능하다

해시 테이블의 메소드

insert()

키와 값을 해시 테이블에 넣어준다.

retireve()

키를 넣었을 때, 키의 값이 나온다.

remove()

해당 데이터를 삭제한다.

resize()

데이터의 저장 공간을 25% ~ 75%의 효율을 지킬 수 있도록
배열의 사이즈를 줄이거나 키운다.

블로그 작성 시 참고한 문서

Linked List Wikipedia
Hash Table Wikipedia
Linked List Data Structure | JavaScript

알아둬야할 것들

• Graph(그래프)
• Tree(트리)
• BST(이진 탐색 트리)
• Time Complexity(시간 복잡도)