200905_TIL

Today I learned

• Linked List
• Hash Table

@@ 오늘은 정말 혼돈의 하루였다. 짧은 레슨에 이어서 바로 자료 구조 2탄 Linked List와 Hash Table을 구현에 들어갔다. 쉽게 생각했던 Linked List에서 생각보다 많은 시간을 보냈고, 생각보다 이해가 까다로웠다. 무언가 코드를 구현하는 것보다 방향 설정에 애를 먹고, 사실은 오늘 연결 리스트나 해시 테이블 둘다 개념 정비가 완벽하게 되지 않은 상태에서, 구현 포인트들이 무엇인지 제대로 인지를 못하고 구현하다보니 더욱 힘들었던 것 같다. 그래도 다행인 것은 구현하면서 느낀 이상한 지점들을 찾아보았고, 조금씩 갈피를 잡고, 개념에도 더 다가설 수 있었다는 것이다.

다루지 않았던 포인터 개념도 배우고, checkpoint 시간에 문제도 풀다보니 자료구조 구현에 대한 의미를 비로소 깨달은 느낌이었다.

해시테이블은 결국 오늘 페어시간동안 완료하지 못하고, 월요일 1-2시간 정도 남짓 시간이 있지만, 아무래도 시간이 촉박할 것 같아서 페어분과 상의해서 개인 학습을 조금 진행하기로 했다. 일과 끝나고 저녁시간에 계속 풀어보는데 디버깅과 콘솔을 하도 많이 찍어서 정말 돌다리를 두드리듯 한 계단 한 계단 진행했고, 다행히 오늘이 가기 전에 테스트 케이스를 통과할 수 있었다.

다만 해시 테이블은 연결 리스트보다 더 개념에 다가서기 어려운 것 같아. 사실 버킷과 튜플이 어떤 형태와 어떤 모양으로 꼭 구현이 돼야 하는지 아직도 잘 모르겠다. 일단 구현을 완료했으니, 다른 사람들의 구현 풀이와 방법들 실제 활용 사례에 대해서 좀 더 찾아봐야겠다.
그리고 해시 테이블 구현하면서 편한 방법으로 코드를 짜다보니까 튜플을 따로 구현을 안하고, 버킷이라는 객체에 키와 값을 담았는데, 이렇게 진행해도 되는지 모르겠다. 일단 통과해서 마음이 즐겁긴 한데, 주말동안 연결리스트와 해시테이블 나머지 공부를 해야겠다. (알고리즘, 자료구조 책도 잔뜩 빌려놨다... 다 읽을 수 있을진 모르겠지만, 필요 부분만 차용해서 봐야겠다)

Linked List

• 저장하는 각 데이터 (기본데이터, 배열, 구조체, 클래스)가 데이터 외에 다음과 이전의 데이터를 가리키는 정보를 가지는 자료구조

• 그 크기가 동적이다.

• 여러개의 노드들로 이루어져있다.

• 각각의 노드는 (데이터) + ( 다음 노드가 뭔지 알려주는 주소 )를 갖고 있다.

• length, head 프로퍼티를 갖고 있다. (프로퍼티)

• 또한 새로운 데이터 추가, 데이터의 위치를 찾기, 데이터 제거 기능을 갖고 있다. (메소드)

• 어떤 임의 점에 데이터 추가와 삭제를 할 경우 O(1) (상수 시간)의 시간 복잡도를 갖는다.

• 추가 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다르다.

• 연결 리스트의 각 노드는 인덱스를 갖지 않는다.

• 삽입과 삭제를 할 땐 전체 데이터의 변동은 없고, 앞 , 뒤 연관된 데이터만 변동하면 된다. 그래서 연결리스트는 중간에 넣거나, 지우는 과정을 빠르게 수행할 수 있다. 그러나 특정 데이터를 찾는 것은 포인터를 따라 이동해야 하므로 성능이 떨어진다.

  특정 데이터를 연결 리스트에서 검색하고자 할 경우, 처음부터 전체 연결 리스트를 훑어야 한다. 이는 O(n)의 복잡도를 필요로 한다.

  데이터의 변화가 많은 상황이라면 연결 리스트를 사용하는 것이 현명하다.

• 컴퓨터 내부에서 사용할 수 있는 자료 구조는 리스트와 연결 리스트 방식 외에는 없다. 다른 자료구조는 이 두가지를 이용하여 구현한 것이다.

• 스택이나 큐를 연결 리스트 외에 리스트 방식을 이용하여 구현할 수도 있다. 그러나 연결 리스트 방식을 사용하면 추가, 삭제, 삽입을 했을 때 전체 데이터의 변동이 없어 속도가 빠르다. 그래서 보통 연결 리스트를 사용한다.

• 연결리스트 종류

  • 단일 연결 리스트

  • 이중 연결 리스트

    저장된 각 데이터가 (이전 데이터 주소) + (데이터) + ( 다음 데이터의 주소) 로 이뤄져있다.
    양방향 탐색이 가능하다.
    연결리스트의 뒤로 가기가 불편한 단점을 해결한 연결 리스트
    next 외에 this.prev 를 넣어 이전 노드를 가리킨다.

  • 다중 연결 리스트

  • 환형 연결 리스트

    • 더블 연결 리스트의 양끝이 연결되어있는 구조

• 연결리스트 실제사례

  • 웹 브라우저 히스토리, 뒤로가기 버튼
  • 이중 연결 리스트
    • 뮤직 플레이리스트 되감기, 이전/다음곡 스킵, 다음 곡 재생

Hash Table

• 해쉬테이블은 데이터를 저장할 때, 저장할 위치를 해쉬 함수를 이용하여 생성하고, 생성된 위치에 데이터를 저장하는 방식에서 사용하는 주소 테이블이다.

• 순서 리스트와 연결 리스트 자료구조를 조합하여 사용하며, 데이터에 직접적인 접근이 가능하여, 저장 및 읽기 속도가 빠르다.

• 데이터 베이스에 데이터를 저장할 때 주로 사용하며, 예는 다음과 같다.

  • 데이터를 저장할 때 각 데이터마다 해쉬 함수를 돌리면 배열 항목이 나오게 된다.
  • 데이터를 돌려 나온 숫자 (해쉬값)를 해당숫자 번에 해당하는 배열의 주소에 저장한다.
  • 만약 해쉬함수를 돌려 같은 해시값이 나올 경우 연결리스트로 저장한다.

• hashing
  문자열이 일반적으로 더 짧은 고정 길이 값 또는 원래 문자열을 나타내는 키로 변환하는 것을 말한다

  값을 사용해서 항목을 찾는 것보다 해시 처리된 키로 찾는 것이 더 빠르기 때문에 데이터베이스에서 항목을 인덱싱하고 검색하는 데 사용된다. 또한 암호화 알고리즘에도 사용된다.

• 해시 맵이라고도 한다.

• 연관 배열 구조를 이용하여 값 쌍 값을 저장하고 있는 자료구조

• 연관 배열 구조: 키 1개와 값 1개가 1대1로 연관되어있는 자료 구조

• insert, retrieve(key), remove

• 해시 테이블은 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

• 해시 테이블은 키, 해시함수, 해시, 값, 저장소로 이뤄져있다.

• 해시 테이블의 3가지 특징

  • 항상 갖고 있는 배열의 크기 안의 값만 반환 시킨다.
  • 언제든지 일정한 값에 대한 같은 값이 나와야 한다. (매번 값이 바뀌면 안된다.)
  • 해시 함수는 저장할 수 없다. 값을 내뱉을 뿐이다.

• 해시 테이블의 충돌 해결

  • 배열 안에 배열을 넣는다
    ( 이 경우 입력값에 따른 값을 구분하기 위해, 배열 안 배열엔 튜플 사용하여 0번째 엔 키 1번째 인덱스엔 값을 저장한다 )
  • Separate Chaining : 해시충돌이 발생하면 연결 리스트로 데이터들을 연결하는 방식.
    키 - 값을 함께 저장하고, 연결리스트처럼 포인터가 존재하게 해서, 다음 노드를 가리키도록 한다.
  • Open Addressing : 해시 충돌이 일어나면 다른 버킷에 데이터를 삽입한다.
    해당 버킷에 값이 있어 충돌이 일어나면 다른 빈공간을 찾아 데이터를 삽입한다.
    • 빈 공간을 찾는 방법
      • Linear Probing
      • Quadratic Probing
      • Double Hashing

• storage
  해쉬 테이블을 의미하는 배열

• buckets

  키-값 쌍을 갖고 있는 테이블의 인덱스 배열

• tuples

  각 버킷이 갖고 있는 데이터들

  • 인풋 사이즈가 커질 때 시간 복잡도를 O(1) 으로 유지하는 법

    • hash table resizing

      해시 테이블은 25 % ~ 75 % 사이에 데이터가 차있을 때 가장 효과적이다.
      75%을 넘어서면 데이터 사이즈를 2배로 늘린다.
      25% 아래로 내려가려고 하면 사이즈를 반으로 줄인다.

  • 해시 테이블도 최악의 경우 O(n)의 시간 복잡도를 갖게 된다.

    • 해시 테이블이 커질 때, 키우고 해싱을 다시 해줄 때
      ( 7개의 배열에서 2배 늘어난 배열로 데이터를 옮겨 담을 때)
    • 내가 넣는 모든 키가 같은 버킷 안에 들어갈경우 O(n)이 될 수 있다.
    • 이를 방지하기 위해 해싱 함수를 잘 만들고, 해시 테이블을 늘리고 줄이는 함수 또한 잘 만들어야한다.