Data Structure Linked List, HashTable

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

 

1. Linked List

 

연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소, 우리는 이것을 노드(Node) 라고 부릅니다.

노드의 연결로 이루어진 자료 구조입니다.

연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖습니다.

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

다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 갖지 않습니다.

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

 

배열과 유사하다고 보인다면 비교를 해보자.   배열 리스트는 가장 간단한 메모리 데이터 구조이며, 장점으로는 동일한 데이터 타입을 연속적으로 저장할 수 있으며, 간단하고, 사용이 쉬우며 데이터를 참조하기가 쉽다. 단점은 고정된 크기(JS 제외)를 가지고 있어서 배열의 처음이나 원소를 넣고 빼려면 비싼 연산을 빈번하게 해야 한다.   연결 리스트는 일련의 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치하지 않는다. 노드로 구현된 리스트이며, 링크 하나에 4btye 메모리를 차지하며, 더블 링크드일 경우엔 노드 하나에 8 btye의 링크 메모리를 차지한다. 장점은 배열에 비해 데이터의 추가 및 삽입이 용이하며, 배열보다 메모리를 효율적으로 쓸 수 있다. 단점은 특정 위치의 데이터를 검색하기 위해서는 처음부터 끝까지 순회해야 하기 때문에 탐색에 비효율적이다. 따라서 탐색과 정렬을 자주 한다면 배열리스트로 추가와 삭제가 많다면 연결 리스트로 이용하는 것이 좋다.

 

연결 리스트의 특징을 정리하자면 다음과 같다. 연속되는 항목들이 포인트로 연결되어 있으며, 마지막 항목은 Null을 가리키고 있다.(마지막이라 연결한 노드가 없기 때문이다.) 프로그램이 수행되는 동안 크기가 동적으로 커지거나 작아지며, 메모리 공간 낭비가 적지만 포인터 메모리가 필요하다.  배열에 비해 데이터의 추가와 삽입에 용이하며, 단방향(양방향이라도) 순차적으로 탐색하지 않으면 요소에 접근이 불가하기 때문에 탐색 속도가 떨어진다. 데이터를 추가하는 건 객체 할당이며, 링크를 끊어버리면 데이터가 삭제되기 때문에 (JS기준) 만약 head에서 노드를 전체 삭제하고 싶다면 head에 있는 링크를 끊어 버리기만 한다.

 

연결 리스트에는 단일 연결 리스트(Singly-Linked List), 이중 연결 리스트(Doubly-Linked Lsit)등의 종류가 있습니다. 우리가 구현하는 연결 리스트는 어떤 종류의 연결 리스트인가요? 두 종류의 연결 리스트는 어떻게 다른가요?

 

Singly linked list (일방향 연결 리스트) 지금까지 말했던 것이 바로 일방향 연결 리스트다. 일방향 연결 리스트는 노드에 포인터(다음 노드를 가리키는 링크)가 한 개인 연결 리스트이며, 이 리스트의 장점은 노드당 포인터 데이터를 4 btye만 차지해서 이중 연결 리스트보다 데이터를 아낄 수 있다는 점이 있다. 다만 일방향 이기 때문에 현재 노드는 이전 노드로 돌아가는 법을 모르며, 직진의 형태라고 보면 된다.   Doubly linked list(이중 연결 리스트)   노드에 포인터가 두 개 있는 것을 이중 연결 리스트라고하며, 일방향 연결 리스트와 똑같지만 앞서 말한 것처럼 노드에 포인터가 두 개 있다는 점이 다르다, 이 두 개의 포인터는 전과 후를 가리키고 있기 때문에 일방향과는 달리 이전으로 갈 수도, 이후로도 갈 수도 있다. 포인터가 두 개가 생겼으니 데이터도 2배가 되며 8 btye가 된다.   Circular linked list(환형 연결 리스트)   연결 리스트에 있는 헤드와 테일이 붙어져 있어, 원의 모양과 같다고 하여 환형 리스트라고 불린다. 테일의 포인터가 null을 가리키고 있는 것이 아닌 head를 가리키고 있는 것이며, 노드 6번에 있다가 4번으로 가야 된다면, 일방향 리스트는 다시 시작해야 되지만 환형 리스트는 7,8,9,10을 지나 다시 0,1,2,3,4로 갈 수 있는 형식이며 순회할 때 좋은 연결 리스트이다.

 

실제 사례를 연결 리스트로 구현한다고 할 경우, 이에 알맞은 예는 어떤 것들이 있을까요?

[ Linked list real life example - 다양한 예제 ]

 

실제 사례를 연결 리스트로 구현한다고 할 경우에는, 기차 및 지하철의 각 칸마다 연결하는 것을 연결 리스트로 볼 수 있으며, 지하철,기차역을 연결 리스트로 들수있다. 또한 음악을 듣는 플랫폼을 사용할때 다음 곡이나 이전 곡으로 갈수있는것도 포함되며, 포토샵같은 것 지웠다 다시 복구했을때 사용한다고 볼수도있다.

• Linked List
  • 다음과 같은 method를 구현하세요 :
    • addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가합니다.
    • remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다
    • getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
    • contains(value) - 연결 리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
    • indexOf(value) - 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

 

code write - 구현하기 앞서 어떻게 설명을 할지에 대해서 작성을 해보기로 한다.

 

addToTail(value)

1. head와 tail에 참조 연결
   0-1. new를 이용해 node 생성 (let curNode = new Node())
2. 만약 head가 비어 있다면? 첫 연결이기 때문에 head와 tail에 node 참조 연결을 해 준다.
3. 만약 head가 비어 있지 않다면?
   2-1. tail.next에 node 연결
   2-2. tail에 node 연결

getNodeAt(index)

1. 헤드를 변수에 저장한다.
2. 만약, index가 size보다 크다면?
   2-1. undefined에 저장한다.
3. 만약, Index가 size보다 작다면?
   3-1. for문을 돌리는데, i<index로 설정.
   3-2. 1번의 변수를 1번의 변수.next로 설정해서 index까지 도달.
   3-3. 그 index를 리턴.

contains(value)

1. 헤드를 curNode 변수에 저장한다.
2. while문을 설정함. curNode가 있을 때까지.
3. 해당 인덱스와 curNode.value가 같다면 리턴 true.
   3-1. 같지 않다면 curNode = curNode.next
4. 다 돌았음에도 불구하고 없다면 false 리턴.

indexOf(value)

1. 헤드를 curNode 변수에 저장한다.
2. indexCount 변수를 설정.
3. while문을 설정함. curNode가 있을 때까지.
4. 해당 인덱스와 curNode.value가 같다면 인덱스 변수 리턴.
5. 아니라면 인덱스 변수++, curNode = curNode.next
6. 다 돌았음에도 불구하고 없다면 -1 리턴.

remove(value): 해당하는 연결 리스트의 값을 지웁니다.

1. 만약에 헤드가 없다면 undefined 리턴.
   0-1. 만약에 헤드 value와 value가 같다?
   0-2. head는 head.next로 설정. (헤드 없애기)
   0-3. 현재 오브젝트 리턴.
2. head를 prevNode로 설정. (그러니까 0번째)
3. head.next를 curNode로 설정. (그러니까 1번째)
4. while문을 설정함. curNode가 있을 때까지.
5. 만약 curNode.value가 value와 값이 같다?
   4-1. break;
6. 만약 값이 같지 않다?
   5-1. prevNode = curNode
   5-2. curNode = curNode.next (한 칸씩 당겨 줌)
7. (curNode.value 값이 같을 때) prevNode.next = curNode.next
8. size--
9. 오브젝 리턴

remove(value): 해당하는 연결 리스트의 값을 지웁니다.

• size()

1. size를 리턴한다.

 

---

 

2. Hash Table 

해시 테이블(해시 맵이라고도 합니다)은 키, 값 쌍을 저장하고 있는 자료 구조입니다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash function)라는 함수를 통해 특정 숫자 값의 인덱스로 변환합니다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지합니다.

 

What is Hashing?[해싱이라는 용어는 어떻게 정의할수있나? 무엇을 의미?]

 

데이터 관리 기법이며, 가변 크기의 입력값에서 고정된 크기의 출력값을 생성해 내는 과정을 Hashing이라고 한다.

 

Hash table Characteristic

 

내부에 Hash 함수를 가지고 있고, Hash 함수를 통해서 데이터를 분류하여 정수로 만들고, 그 정수는 인덱스의 값이 되어 그곳에 넣어지게 된다. 배열의 크기가 정해져있으며, 유동적일수 없다. 인덱스의 값이 유한하다는 가정 하에 Hash함수를 실행하여서 인덱스 값을 설정하기 때문이다. 출력 값과 입력 값을 1:1로 매핑할 수 있습니다.

 

Hash table에 정의는 어떠한 값을 넣었을 때 정보를 암호화하거나 조금 더 자료를 정리하기 위해서 일련의 값으로 만들어 내는 것을 말한다.

Hash table에 key와 value 값을 넣으면, key를 사용하여 index의 값을 도출하는 함수입니다.

 

Hash table 장점에 대해서

 

hasing된 key를 가지고 배열의 index를 사용하여 검색하기 때문에 추가, 삭제 및 탐색이 아주 쉽고 빠르다. hash 충돌이 없을 때는 O(1)의 상수 시간에 가까워지고, hash 충돌이 많아질수록 O(n)에 가까워진다.

 

Hash table 단점에 대해서

 

Hash 함수를 사용하는 데에 추가적인 연산이 필요하다. hash table의 크기가 유한적이고, hash 함수의 특성상 hash 충돌을 일으킬 수 있다. 적은 데이터를 가지고 hash 충돌을 연결리스트를 사용한다면 캐시 효율이 떨어진다. 

 

Hash 함수는 아주 간단하게부터 시작해서 아주 어렵게도 만들 수 있으며, 아주 간단하게 만든것을 다른 블로그에서 참고하였습니다.

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

 

var hashFunction = function(str, max){
  var hash = 0;
  for(var i = 0; i < str.length; i++){
   hash = (hash <<5) + hash + str.charCodeAt(i);
   hash = hash & hash; // convert to 32bit integer
   hash = Math.abs(hash);
  }
  return hash % max;
};

 

key 인 'apples'과 value 인 '사과는 사각사각해서 싫어'를 해시 테이블에 넣었을 때, hashtable은 hash 함수로 키 값을 보내고, hash 함수는 key.length / 2를 통하여 인덱스의 값을 도출해내며, key 'apples'는 6글자 이므로 3을 받는다. 그 인덱스를 받은 Hash table은 자신의 스토리지의 인덱스 3번에 데이터를 저장하게 된다.

 

magic's box 불리우는 Hash function에 특징은 다음과 같다.

 

array의 크기 안에서 값이 나와야한다. 그 이유는 array 안에 넣을 것이기 때문에 지정된 array를 벗어난 index에 넣을 수 없다.

언제든지 넣었을 때 같은 값이 나와야 한다. 그  이유는 apple이라는 것을 넣었을 때 언제는 t에 가 있고, 언제는 a에 가 있는다면 아주 헷갈리기 때문이다. 그렇기에 같은 값을 넣었을 땐 똑같은 숫자가 나와야 한다.

들어온 key에 대하여 어떠한 저장도 할 수 없다 그 이유는 hash 함수는 인덱스만 도출해내는 공장 같은 것이기 때문에, 어떠한 값도 저장할 수가 없으며, 들어오는 값을 숫자로 바꾸기도하며, 해시 충돌이 일어날 수 있다.

 

only retrun numbers that are within the array bounds ( 0 to length-1) - 항상 내가 가지고 있는 어레이의 크기에서 값이 나와야 한다.

always output the same index value for a given input string and length - 언제든지 넣었을 때 값이 같아야 한다.

Maintain no memory of previously used array locations or input strings - 그때그때 값을 주면 값을 내뱉을 수 있어야 한다.

 

What is 해쉬충돌? [ 왜 이런 문제가 발생? ]

 

문자열은 무한하고 인덱스는 유한합니다. 그렇게 때문에 무한한 문자열을 고유한 인덱스에 담기 어려운데, 그래서 hash 함수에는 한정된 인덱스에 값을 얼마나 골고루 넣을 수 있냐에 대한 알고리즘이 잘 된 것을 아주 높게 평가를 한다고합니다. apple이라는것도 있고 같은 a로는 area, air, airplane 등 여러가지로 시작되는 a가 있을 것이기에 고유한 것으로 가질 수없으며 인덱스를 공유하게 된다. 그래서 a의 인덱스에 apple이라는 data를 담아졌고, air가 들어오면 어떻게 문제를 해결해야하는지 봐야한다. Office hour 때 해결책이 나왔다. 

 

첫번째로는 Open addressing : 다른 여분의 인덱스에 설정하기

선형탐사와 이중 해시가 있으며 선형탐사는 만약 1번 칸이 비어 있다면 2번 칸이 비어 있는지 검사 후에 비어 있다면 2번칸에 넣는 방식이다.

이중해시로는 해시 함수를 2개로 두고, 평소에는 1만 쓰다가 충돌시 2를 써서 새로운 인덱스로 조정하는 것이다.

 

두번째로는 Close addressing : 충돌이 일어나도 해당위치에 저장

버켓과 체이닝이 있으며 충돌이 일어나도 해당 위치에 저장하지만 여러 개를 둘 수 있는 다른 방법을 사용하는 과정이라고 보면된다.

버켓은 배열의 한 요소가 2차원 배열처럼 다시 배열인 경우이다. 그래서 해시 충돌이 일어나게 되면 요소 안의 배열로 쌓이게 된다.

두번째로는 체이닝이며 충돌된 값들을 연결 리스트로 연결시켜주는 것이다. 

 

 

hash table에서 다음 용어는 무엇을 의미하는가?

 

storage = array / 사실은 table인 것이다.

hash table의 table인 것이다. data들을 저장하는 공간이고, 배열인것이다.

bucket = storage에 call 리전드를 가지고 있는 것을 말한다.

data가 들어갈 공간을 말하며, 이 bucket은 index에 담겨 있고, data 하나마다 bucket이 들어간다.

tuple = 각각의 버켓을 가지고 있는 것을 tuple이라고 한다.

data들을 담고 있는 곳을 말하며, 이 data는 수정 혹은 추가, 삭제할 수가 없기 때문에 tuple과 같은 첨삭이 불가한 읽기 전용이다.

 

Objects vs Hash Tables에 대하여 

 

the interface of an object as compared to a hash table.

	JavaScript Object	Hash Table
insert	obj['key'] = 'value'	ht.insert('key','value')
retrieve	obj['key']	ht.retrieve('key')
remove	delete obj['key']	ht.delete('key')

 

insert(key, valaue)는 주어진 키와 값을 저장하며, 이미 해당 키가 저장되어 있다면 갚을 덮어 씌우며 해시 테이블에 넣어주는 것이다.

retrieve는 주어진 키를 넣었을 때, 값을 반환하며 나오는 것이다. 없다면 undefined를 반환한다.

remove : 주어진 키에 해당하는 값을 삭제하고 값을 반환하며 없다면 undefined를 반환해야한다.

_resize(newLimit) : 해시 테이블의 스토리지 배열을 newLimit으로 리사 이징하는 함수입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 구현 후 HashTable 내부에서 사용하시면 되며, 25%~75%의 효율을 지킬 수 있도록 배열의 사이즈를 줄이거나 키울수 있다.

 

 

code write - 구현하기 앞서 어떻게 설명을 할지에 대해서 작성을 해보기로 한다.

 

insert

1. obj을 하나 생성한다. (bucket)
2. storage에 해당 index가 없으면 obj[key] = value로 설정하고 값을 스토리지에 넣어 준다.
3. 만약 해당 인덱스가 있다면 storage를 obj으로 할당하고, 그 obj에 key와 value를 넣는다.
4. size에 1을 추가한다.
5. 만약 데이터가 스토리지에 75% 이상 찼다면, 2배로 resizing한다.
6. 스토리지를 리턴한다.

retireve

1. 스토리지에 해당 인덱스가 없다면 undefined를 리턴한다.
2. 스토리지에 해당 인덱스가 있다면 그 인덱스의 키를 리턴한다.

remove

1. 삭제할 값을 변수에 넣는다.
2. 해당 값을 undefined로 만든다.
3. 사이즈를 -1 줄인다.
4. 만약 사이즈를 줄였을 때, 데이터의 비중이 25% 이하라면 절반으로 resizing한다.
5. 1번의 변수를 리턴한다.

_resize

1. 전달인자를 2배 이상 혹은 절감의 limit 길이로 받는다.
2. 현재 스토리지를 oldStorage의 변수로 받는다.
3. 리밋을 변수 리밋으로 할당하고, 현재 스토리지를 새로운 변수 리밋으로 변환시킨다.
4. 반복문을 사용하여 oldStorage의 인덱스의 키가 undifined인 것을 찾아서 딜리트한다.
5. 반복문을 사용하여 oldStorage를 현재의 스토리지에 넣는다. (재귀)

 

 

강의 영상중 영어를 가져와서 설명해주셨을때 썼던 것을 가져와봤습니다.

 

Definition   A Hash Table is a data structure that maintains associations between two data values. The data values being associated are commonly referred to as the key and value. A single instance of Hash Table may store many associations.   A Hash Table has other names too, such as an Associative Array, Dictionary, Map or Hash.

 

hash table resizing   hash tables operate most effectively when the ratio of tuple count to storage array length is between 25% and 75%. when the ratio is:   >75%, double the size of the storage array <25%, half the size of the storage array   Resizing necessitates rehashing every key as it may end up in a different bucket. Remember, the hashing function depends on the storage array size!

 

Dirty Little Secrets   While most of the time insert & remove operations are O(1), the worst case is O(n), This can occur for two reasons:   When a hash table is growing, it resizes itself and every element must be rehashed It is possible for all keys to hash to the same bucket, which becomes a O(n) search for an item   The quality of the hashing algorithm is major factor in how well your tuples will be distributed within your buckets. An algorithm with more entropy will produce superior results.