Linked List, Hash Table

자료구조 - 연결 리스트 (Linked List)

 

https://www.slideshare.net/choong83/ss-60914337 이미지

연결 리스트는 '노드' 라는 객체로 이루어져있다. 연결리스트에서 노드는 Data와 Next adress로 구성되어있다. (데이터와 주소는 한 세트) 입력하는 데이터를 담고 노가 추가될 때 마다 Next adress를 이용하여 다음 노드와 연결한다.

 

https://www.slideshare.net/choong83/ss-60914337 이미지

 

각 노드에 다음 주소를 저장함으로써 다음 노드를 탐색할 수 있다. (한개의 포인터로 다음 주소를 가르킨다.) 첫번째 서있는 사람이 머리부분 (haed) 마지막에 서있는 사람이 꼬리부분 (tail)이다. 꼬리부분(tail)인 마지막 노드는 위와같이 다음 주소가 Null이라면 마지막 노드라고 할 수 있다. 다음 저장되는 주소가 없으니까 null 인 것이다.

 

위와같이 한 방향으로 연결되어지는 구조가 단순 연결 리스트(Singly linked list)이다.

 

배열과 유사한 형태를 지니고 있지만, 링크라는 것으로 차이가 있다.

 

• 배열 (자바스크립트의 배열을 말하는 것이 아니다.) : 메모리 데이터 구조.
  장점) 동일한 데이터 타입을 연속으로 저장 가능. 간단하고 참조하기 쉬움.
  단점) 중간에 추가 삭제가 어려움.
• 연결리스트 : 배열처럼 차례대로 저장하지만 연속적으로 위치하지는 않음.
  장점) 배열에 비해 데이터 추가 삭제가 쉬움. 메모리의 효율적인 사용 가능.
  단점) 데이터를 탐색하려면 처음부터 끝까지 순회해야해서 비효율적.

 

위와같이 단순 연결 리스트 말고도 이중연결리스트(Doubly linked list) 환형 연결 리스트(Circular linked list)가 있다.

 

이중 연결 리스트 : 노드에 포인터가 2개있는 리스트. 포인터가 전과 후를 가르키기 때문에 앞뒤로 이동 가능.

환형 연결 리스트 : 연결 리스트의 헤드와 테일이 이어져있어 마치 원형의 모양과 같다고 해서 환형 리스트라고 불린다. 단순 연결 리스트에서는 tail의 포인터는 null을 가르키고 있지만, 환형 연결 리스트는 tail은 head를 가르키고 있다.

 

일상 생활 속 연결 리스트 예시

 

유튜브 뮤직 플레이어

 

위와같이 음악 플레이를 보면 연결 리스트를 사용하는 것을 볼 수 있다. 앞, 뒤로 이동 가능하고 반복 재생이 가능하다.

 

자료구조 - Hash Table

 

해시 테이블이란? 연관배열 구조를 이용하여 키(Key)에 결과 값(Value)를 저장하는 자료구조.

연관배열 구조란? 키와 값이 1:1로 연관되어 있는 자료구조.

해싱이란? 해싱은 가변 크기의 입력값에서 고정된 크기의 출력값을 생성해내는 과정을 말한다. 모든 해시함수가 암호 방식을 사용하는 것은 아니지만, 비트코인으로 유명한 암호화폐의 핵심에는 이런 해시함수의 암호 방식을 사용한다. 비트코인은 데이터의 무결성과 보안성으로 유명하다. 

해시함수와 암호 해시함수는 '결정론적'이다. 이게 무슨 말이냐면, 입력값이 변하지 않는 이상 해싱 알고리즘은 언제나 동일한 출력값을 가져온다는 것이다. 입력값에서 출력값을 생성하는것을 매우 쉽지만, 반대는 매우 어렵다. 입력값을 찾기 어려운 해싱 알고리즘일수록 더욱 안전하다고 볼 수 있다.

 

이렇게 암호화 기술을 사용하는 암호 해시 함수를 되돌리려면, 해당 출력값이 생성될 때까지 수많은 시행착오를 거치며 알아내야한다. 그러나, 다른 입력값이 동일한 출력값을 생성하는 '충돌'이 발생할 가능성도 있다.

암호 해시 함수가 안전한 것으로 간주되려면 그래서 아래와같은 3가지 속성이 필요하다.

 

• 충돌 저항성 : 출력값으로 동일한 해시를 출력하는 서로 다른 두 입력값을 찾는 것이 거의 불가능함.
• 역상 저항성 : 해시 함수를 되돌리는 것이 거의 불가능함. (주어진 출력값에서 입력값을 찾는것)
• 제2 역상 저항성 : 특정한 입력값과 충돌하는 어떠한 두번째 입력값을 찾는 것이 거의 불가능함.

Hash table의 구조. (출저: https://velog.io/@riceintheramen/hash-Table)

 

• 키(Key) : 고유한 값. 해시 함수에 들어감.
• 스토리지(Storage) : 해시 테이블의 테이블. 저장 공간이자 배열.
• 해시함수(Hash Function) : 키를 해시로 바꾸어주는 역할.
• 해시(Hash): 해시 함수의 결과물. 저장소에 값과 매칭되어 저장됨.
  
• 버킷(Bucket) : 데이터가 들어갈 공간.
  
• 튜플(Tuple) : 데이터들을 담고 있는 곳, 수정, 추가, 삭제 불가(읽기전용)

해시테이블 메소드

• insert : 키와 값을 해시 테이블에 넣어줌.
• retireve : 키를 넣었을 때 값이 나옴.
• remove : 해당 데이터 삭제.
• _resize : 25~75%의 효율을 유지할 수 있도록 배열의 사이즈를 줄이거나 키움.

 

해시테이블에 저장, 검색, 삭제 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있기 때문에 자료구조로 매우 우수하다고 볼 수 있다. 하지만, 무한한 값(Key)을 유한한 Value(Hash)로 표현하면서 서로 다른 유한한 값이 동일한 출력 값을 가지게 된다. Key는 무한정 입력 할 수 있지만 값은 유한함으로 필연적으로 충돌이 일어날 수 밖에 없는데, 이러한 충돌 현상을 hash collision이라고 한다.

이러한 충돌 현상(hash collision)을 해결하기 위해서는 Separate Chaining(Chaining), Open Adressing의 방법이 있다. 

 

• Separate Chaining(Chaining) : 충돌이 일어나면 해당 값을 기존의 값과 연결시키는 방법. 동일한 주소값인 A에서 A`가 생겨난다고 생각하면 된다.
  장점) 저장소를 효율적으로 사용할 수 있다. 상대적으로 적은 메모리를 쓴다.
  단점) 한 자료들이 계속 A`, A``...이런식으로 연결(쏠림 현상)되면 검색 효율이 낮아진다. 외부 저장공간을 사용해야한다.
• Open Adressing : 총돌이 일어날 시 비어있는 해시를 찾아 데이터에 저장하는 기법이다. 키와 값 1:1 매칭 형태가 유지된다.
  장점) 다른 저장 공간 없이 해시테이블 내에서 데이터 저장 및 처리 가능.
  단점) 해시함수의 성능에따라 전체 해시테이블 성능이 좌지우지됨. 데이터의 길이가 늘어나게 되면 그에 해당하는 저장소가 필요함.