20.09.03-TIL : data structure -Stack, Queue, Linked list, Hash table
Stack
- Stack 은 쌓여있는 접시와 같다. 들어올 때 제일 위에 쌓고, 뺄 때 제일 위에서부터 빼고. 따라서 LIFO : Last In, First Out.
- 선형(linear) 자료구조 — 발포 비타민의 패키징을 생각하면 됨.
- push(넣을 때), pop(뺄 때), peek(제일 나중에 집어넣은 데이터 확인) 등의 메소드를 사용할 수 있다.
- 쌓는 구조이기 때문에 stack은 인덱스가 top 의 것 1개만 필요하다.
Queue
- Queue는 말 그대로 줄서는 것과 같다. 새로 오면 맨 끝에 줄을 서고, 나갈 때는 줄 제일 앞에서 부터 나가기. FIFO : First In, First Out.
- 마찬가지로 선형 구조
- 데이터를 넣을 때는 enqueue, 뺄 때는 dequeue
- front 와 rear 가 있기 때문에 인덱스는 2개가 필요하다.
Linked list
자료를 저장하는 방법은 크게 배열과 Linked list가 있으며, 각 자료구조 별 장단점은 아래와 같다.
노드(Node)및 Linked List는 어떻게 구성되어 있나?
Linked list 는 ‘노드'라는 객체로 이루어져 있으며, 노드는 data를 저장할 공간과 다음 주소를 가리키는 공간으로 이루어져 있다. 사용자가 입력하는 정보를 data 영역에 담고, 노드가 추가될 때마다 next address를 이용하여 다음 노드와 연결한다.
연결 리스트는 아래와 같은 구조를 지니고 있으며, 이러한 구조덕에 어떤 임의의 지점에 데이터를 추가/삭제할 경우, 연결 고리만 바꿔주면 되기 때문에 O(1)의 시간 복잡도를 갖는다. 하지만 각 노드는 다음 연결고리의 정보만 가지고 있기 때문에, 어떤 특정 데이터를 검색하고자 하는 경우, 연결 리스트의 처음부터 훑어야 하며, 이는 O(n)(선형) 복잡도를 필요로 한다.
가장 공감이 갔던 실생활 예시
실생활에 사용되는 Linked List 예시 중 가장 단박에 이해가 되었던 것은 음악 playlist. (물론 해당 예시는 double linked list 이긴 하지만) 시작과 끝이 있고, 곡과 곡이 서로를 가리키고 있기 때문에 앞으로건 뒤로건 모두 skip 이동이 가능하고, playlist 중간에 새로운 곡을 삽입할 수도 있다.
Linked List Method
- addToTail(value) : 주어진 값을 연결 리스트의 끝에 추가
- remove(value) : 주어진 값을 찾아 연결 해제(삭제)
- getNodeAt(index) : 주어진 인덱스의 노드를 찾아서 반환. 값이 아니라 노드를 반환해야 한다. 해당 인덱스에 노드가 없다면 undefined를 반환.
- contains(value) : 연결리스트에 주어진 값을 가지는 노드의 존재여부 반환
- indexOf(value) : 주어진 값의 인덱스 반환. 없을 경우 -1 반환.
Hash table
해싱(Hashing)이란?
수많은 데이터를 테이블 형식에 대응(mapping)시켜 저장할수 있도록 만든 데이터 관리 기법. 데이터들을 저장하고 찾을 때 hash function을 이용해 데이터를 효과적으로 저장 및 가져올 수 있다. 가변 크기의 입력값에서 고정된 크기의 출력값을 생성해 내는 과정을 의미한다.
- 입력 길이에 상관없이 항상 고정된 문자열의 길이(해쉬값)를 반환한다. 이러한 특징은 눈사태 효과를 활용할 수 있다.
- 눈사태 효과 : 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.
- 출력된 결과값을 토대로 입력 값을 유추할 수 없다. 왜냐하면 입력값이 조금만 변경되어도 다른 값으로 출력하기 때문에.
- 입력값이 같을 경우 항상 동일한 결과값을 출력한다.따라서 해쉬 함수는 아주 방대한 양의 데이터에서 변경 내용이 있는지 확인할 때는 유용하다. 그 이유는
- 어떤 길이를 입력해도 고정된 길이의 결과값을 출력하고
- 입력값의 아주 일부만 변경되어도 전혀 다른 값이 출력되기 때문에
- 더불어 입력값에 따른 결과값은 항상 동일하다.
- 이러한 특징들 때문에 해쉬 함수는 데이터의 무결성 검증에 유용하다. - 해시 테이블은 키 & 값 쌍을 저장하고 있는 자료구조로, 키를 저장할 때 메모리 공간을 덜 사용할 수 있도록, 키를 “해시함수(Hash function)”라는 함수를 통해 특정 숫자값의 인덱스로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.
Important hashing function characteristic
- 해시 함수는 해시 테이블의 키값을 받아 value가 저장되어 있는 주소를 산출하는 함수.
- array 길이 안의 값만 리턴해야 한다 (0 ~ length-1)
- 같은 입력값에는 늘 같은 출력값을 내보내야 한다.
- 해시 함수는 어떠한 저장도 할 수 없다. 그저 주는 값에 대해 값을 내보낼 뿐.
- 역상 저항성(Preimage) : 주어진 출력값으로 입력값을 알아내기가 거의 불가능하다는 성질. H(x) = y 에서 y을 알아도 x는 모름.
- 제2 역상 저항성 : 어떤 입력값과 동일한 결과값(해쉬값)을 가지는 다른 입력값을 찾을 수 없다. 즉, 어떤 입력값 M1에 대해 M1 not equal M2 인데, H(M1) = H(M2)인 경우의 M2를 찾는 것이 불가능하다는 성질.
- 충돌 저항성 : 동일한 출력값을 갖는 서로 다른 두 입력값을 찾는 것이 거의계산상 불가능하다는 성질. 저항성과 비슷하나, 저항성은 출력값을 아는 상태에서 입력값을 찾지 못한다는 것이고, 충돌 저항성은 출력값을 알든 모르든 특정 결과값을 생성하는 2개의 입력값을 찾는 과정이 불가능하다는 것이다.
해시 충돌(Hash collision) 과 해결 방법
해시 충돌이란, 입력값이 다름에도 불구하고 동일한 값이 출력되는 경우. 보통 입력값은 무한하지만 출력값은 유한하기 때문에 드물지만 발생한다. 때문에 해결 방법으로
- 체이닝(Chaining)
버킷 내에 연결 리스트(linked list)를 할당하여 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식. 상기 Sandra Dee가 이러한 경우에 해당한다.
2. 개방 주소법(Open Addressing)
체이닝은 버켓이 꽉 차더라도 연결리스트로 늘려가기 때문에 주소값은 바뀌지 않는다(closed addressing). 개방 주소법은 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식이며, 대표적으로 3가지가 있다.
- 선형 탐색(Linear Probing) : 충돌 시 다음, 혹음 몇개 건너 뛰어 데이터 삽입
- 제곱 탐색(Quadratic Probing) : 충돌 시 제곱만큼 건너뛴 버켓에 삽입
- 이중 해시(Double Hasing) : 충돌 시 다른 해시 함수를 한번 더 적용한 결과를 이용함
해시 테이블 용어 정리
- Storage : 해시 테이블의 그 ‘테이블’로, 데이터를 저장하는 공간이고 배열이다.
- bucket : collision을 피하기 위해 추가적인 데이터가 들어가는 공간. 이 버켓은 인덱스에 담겨 있고, 버켓 하나에 데이터 한개가 들어간다. 예를 들어 아래 그림에서 cat과 fox는 같은 인덱스 1을 가지고 있기 때문에, 버켓을 따로 만들어서 버켓안에 cat과 fox를 위한 공간을 하나씩 만들어 준다.
- tuple : 순서가 있는 element 들이 담겨있는 저장공간. Tuple은 immutable 해서 추가/삭제/수정이 안됨. 충돌을 피하기 위해 ‘튜플’을 사용. 버켓과 짝꿍으로 연결지어 준 다음 튜플안에 결과값을 넣어 둔다. 튜플은 정확한 결과값을 찾을 수 있도록 각 입력값 별로(collision이 발생하는 경우-fox & cat) reference 를 만들어 두는 것.(내가 못찾는 것인지, tuple은 자료도 잘 없거니와, 있어도 영어라 너무 번역체 같네..)
해시 테이블 메소드 (해시 함수는 따로 필요)
- insert(key, value) : 주어진 키와 값을 저장. 이미 해당 키가 저장되어 있다면 값을 덮어씌움.
- retrieve(key) : 주어진 키에 해당하는 값을 반환. 없다면 undefined 반환
- remove(key) : 주어진 키에 해당하는 값을 삭제하고 값을 반환. 없다면 undefined를 반환.
- _resize(newLimit) : 해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수. 리사이징 후 저장되어있던 값을 전부 다시 해싱해 주어야 한다. 구현 후 HashTable 내부에서 사용하면 된다.
