JS Linked-list & Hash table

 

 

 

오늘은 자료형의 두 가지 유형

 

Linked-list와 Hash table에 대해 알아보자 

 

 

Linked-list

 

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

 

위키피디아에서는 linked-list를 위와 같이 설명하고 있다. 

 

해석하자면, 링크드 리스트는 데이터요소의 일련의 집합이며 메모리상 물리적 공간에서 물리적으로 순서가 정해져있지는 않다. 대신 각 요소들은 다음 데이터요소를 가르킨다. 

 

무슨 말일까?

 

아래 그림을 보면 이해가 수월해 진다. 

 

 

위와 같이 각 노드는 데이터와 참조(link)를 쌍으로 가진다. 

 

Linked-list 구조의 장점은 순환중 노드의 삽입과 수정이 효율적이라는 것이다.  

 

반면, 접근 시간이 선형적이며(파이프라인화가 힘들다) 랜덤엑세스를 이용한 빠른 접근이 어렵다는 단점이 있다.

 

 

 

 

Hash Table

 

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

 

Hash Table은 뭔가 설명이 장황하다. 

 

겁먹지 말고 우선은 찬찬히 살펴보자. 

 

컴퓨터 공학에서, 헤쉬테이블(헤쉬맵)은 키와 밸류를 매핑할 수 있는 구조를 가진 배열연합과 추상 데이터타입을 실행하는 데이터 구조다. 해쉬테이블은 해쉬 코드라고도 불리는 인텍스를 계산하기 위해 해쉬 함수를 이용하며 인텍스를 통해 버킷 혹은 슬롯 배열에서 원하는 밸류를 찾을 수 있다. 

 

 

음... 이래도 이해가 안되니 그림을 살펴보자. 

 

 

이상적으로는 hash function은 계산결과 각각 유일한 인덱스를 반환해야 한다. 그래야 올바른 값을 찾을 수 있으니까. 

 

하지만 대부분의 hash table 디자인은 불완전한 hash function을 실행한다. 이럴 경우 하나 이상의 키값에 

 

중복된 인덱스값이 발생할 수 있다. 이를 충돌(collisions)라고 부른다. 충돌이 발생하면 적절한 방법으로 해결해야 한다. 

 

 해쉬테이블의 장점으로는 임의의 키-밸류 페어의 삭제와 삽입이 가능하며, 실행비용이 평균적이다. 

 

따라서 search tree 혹은 다른 테이블 구조와 비교했을 때 평균적으로 더 효율적인 탐색이 가능하기 때문에

 

다양한 종류의 소프트웨어에서 사용된다.