2020.06.12(금) Sprint 2. Data Structure

Today I Learned

Linked List

• 연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소인 노드의 연결로 이루어진 자료 구조이다.
• Node: value와 next 프로퍼티를 가진다.
• 가져오기: O(n), 추가하기: O(n), 삭제하기: O(n)
• property: head, tail, _size
• method: addToTail(value), remove(value), getNodeAt(index), contains(value), indexOf(value), size()

Hash Table

• 키, 값 쌍을 저장하고 있는 자료 구조이다. (JavaScript에서의 객체와 같다.)
• 메모리 공간을 덜 사용할 수 있도록 키를 Hash Function를 통해 특정 해쉬로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 작은 크기를 유지한다.
• property: storage ,_size, _limit
• method: insert(key, value), retrieve(key), remove(key), _resize(newLimit)

---

Questions

Linked List

• 노드는 어떻게 구성되어 있는가?

  • 노드는 값을 저장하는 value 속성과 다음 노드를 가리키고 있는 next 속성이 있다.

• 연결리스트에서 단일 연결 리스트와 이중 연결 리스트는 어떤 차이가 있는가?

  • 단일 연결 리스트는 next만 존재하여 어떤 노드가 자신을 가리키고 있는지 모르지만, 이중 연결 리스트는 previous 속성이 있어서 자신의 이전 노드와 다음 노드를 모두 알 수 있다.
  • 단일 연결 리스트에선 이전 노드를 모르기 때문에 노드를 remove할 때 시간 복잡도가 O(n)이지만, 이중 연결 리스트는 O(1)의 시간 복잡도를 가진다.

• 실제 사례를 연결 리스트로 구현할 경우, 알맞은 예는 어떠한 것들이 있는가?

  • 브라우저에서 방문한 웹페이지를 담을 자료구조로 사용할 수 있다.
  • 음악 플레이 리스트를 담을 자료구조로 사용할 수 있다.

Hash Table

• 프로그래밍에서 해싱(Hashing)이라는 용어는 어떻게 정의할 수 있는가?

  • 요리에서 hashing은 무언가를 잘게 썰고, 이를 섞는 것을 의미한다. 프로그래밍에서의 해싱도 그와 마찬가지로 해시 함수에 입력된 값을 고유한 인덱스 번호로 반환하여, 해당 인덱스 번호에 값을 저장하는 전체 과정을 의미한다.

• 해시 함수의 세 가지 특징은 무엇인가?

  1. 배열 범위 내 인덱스를 반환해야 한다. (0 ~ array.length - 1)
  2. 동일한 문자열을 입력받았을 경우 항상 동일한 결과를 반환해야 한다.
  3. 별도의 저장공간을 가지면 안 된다.

• 해시 충돌은 무엇인가? 그리고 그것을 해결할 수 있는 방법은 무엇이 있는가?

  • 배열의 크기는 한정되어 있으므로 해시 함수에 다른 입력값이 들어갔지만, 서로 같은 출력값이 나올 수 있다. 이런 상황을 해시 충돌이라고 한다.
  • 해시 함수는 해시 충돌이 발생하지 않도록 구현해야 하며, 해시 충돌이 많아질수록 탐색의 시간 복잡도가 O(n)에 가까워진다.
  • 이를 해결하기 위해 해당 인덱스에 바로 값을 넣는 것이 아니라, 별도의 자료구조(연결 리스트)를 만들어서 해당 리스트에 키와 값을 저장하는 방법으로 해결할 수 있다.

• 해시 테이블에서 다음 용어는 무엇을 의미하는가?

  • storage: 해시 함수로부터 받은 인덱스를 이용하여 값을 저장할 배열
  • bucket: 해시 충돌이 일어날 경우를 대비하여 값 대신 들어갈 자료구조(연결 리스트)
  • tuple: bucket이 가지고 있는 값으로 기존에 저장하고자 하는 key, value 쌍으로 구성되어 있음

• 해시 테이블에서 값이 저장되는 공간을 어떻게 배열만을 이용해서 디자인할 수 있는가?

  • JavaScript에서 배열은 연결 리스트라서 그 크기가 유동적으로 변하지만, 본래 배열은 크기가 고정되어 있다. 저장하고자 하는 데이터가 많아질수록 해시 충돌이 많이 발생하며, tuple의 개수가 많아질수록 탐색에 오랜 시간이 소요될 수 있다. 그러므로, storage인 배열을 resize하여 새로 hashing을 진행함으로써 크기가 고정된 배열으로도 디자인할 수 있다.

---

해시 테이블을 구현할 때 bucket을 무엇으로 구현해야 하는 건지 잘 몰랐어서 객체로 구현해서 제출했지만, 시간날 때 연결 리스트인 배열로 구현을 해봐야겠다.