오늘 스케쥴을 어제 미리 해서 오늘은 시간이 많이 남을거라고 생각했었는데 큰 오산이었다. Hashtable 하나 구현하는데 꼬박 하루를 다 썼다... 만약 어제 Linkedlist를 하지 않았었다면 정말 위험할뻔했다. 먼저 Linkedlist 와 Hashtable을 설명하자면,
1.Linkedlist
Linkedlist(이하 연결리스트)란 자료구조 중 하나인데 나중에 들어올 자료는 지금 들어가 있는 자료의 꼬리를 물고 저장이 된다고 생각하면 된다. 연결리스트는 크게 종류가 있다.
1.단일연결리스트
위 사진과 같이 꼬리에 꼬리를 물고 이어진 데이터를 볼 수 있다. 우리는 한 덩어리의 데이터를 노드라고 부른다. 만약 자료를 참조하고 싶을 때 Head부터 Tail까지 Next를 이용해 하나하나 자료를 비교해 가면서 찾아야하는 단점이 있다. 이는 찾고자 하는 자료가 tail에 가까울수록 연산 횟수가 들어나며, 그만큼 시간도 오래 걸린다. 그러나 장점은 연결리스트의 저장공간측에서 높은 효율을 보여주고 구현방식이 간단하다.
2.이중연결리스트
이중연결리스트는 한 노드가 이전의 노드(previous)와 다음의 노드(next)의 데이터를 갖고있어서 양방향으로 참조가 가능하다. 그만큼 저장공간의 효율성이 떨어지고 구현도 복잡하다. 그러나 이 자료구조의 최대의 장점은 연산을 줄여 참조속도가 굉장히 줄어드는것. Head에서 Tail까지 모든 자료를 하나하나 비교하여 참조하는 단일연결리스트와는 달리 Head에 가까운 것은 Head에서부터 Tail에 가까운 것은 Head에서부터 참조를 하면 된다.
2.HashTable
해시테이블이란 미리 버킷이라는 빈 저장공간을 만들어 놓고 특정 자료를 저장할 때 특정 알고리즘의 해시펑션을 거쳐서 특정 인덱스(해시값)을 부여하여 저장하는 방법이다. 특정 해시값은 특정 자료에만 부합하게 되어있어서 가장 큰 장점은 인덱스 별로 자료가 1:1로 참조할 때 시간을 엄청나게 줄여주는 것. 그러나 비어있는 버킷의 비효율성은 단점으로 작용한다. 그래서 자료의 수에 따라 테이블의 리사이징이 유동적으로 필요하다. 가장 효율적인 사이즈는 자료의 수가 버킷의 수의 75% 이상이면 2배로 리사이징 그리고 자료의 수가 버킷의 수의 25% 이하이면 절반으로 리사이징 하는것이다.
그러나 예외가 하나있다. 바로 해시충돌이다. 만약에 우리가 해시펑션의 알고리즘을 문자열의 첫번째 문자로 특정 해시값을 부여한다면 위 사진을 기준으로 A->0 이기에 ABC AC도 모두 0의 인덱스를 부여 받는다. 그러면 한 해시값에 두개의 자료가 들어가게 되는 것. 해결하기 위해 여러가지 방법이 있지만 간단하게 연결리스트로 해결이 가능하다.
해시충돌이 일어나 해시값과 자료가 1:2로 참조에 소비되는 시간이 늘어 난다.
이러한 단점에도 불구하고 참조속도가 앞의 다른 자료구조에 비해 빠른점과 복잡한 알고리즘의 해시펑션을 가지고 있다면 그 알고리즘을 모르는 사람은 해시값을 해석못하면 자료를 참조하기가 굉장히 어렵고 값을 알더라도 해시값의 연관성을 모르면 다른 자료를 알아내기 어렵다는 점의 보안 장점을 가지고있다.
자바스크립트로 해시테이블을 구현하는건 쉽지가 않았다. 가장 어려웠던 점은 해시테이블의 공간은 제한되어 있었고 그 저장공간을 효율적으로 사용하기 위해 리사이징을 하는 것에서 거의 탈진을 하였다. 그러나 훌륭한 페어 팀원분 덕에 오늘 스케쥴이 끝나기 전에 마칠수 있었다. 내일은 다른 자료구조가 나오는데 난이도 날이 지날수록 난이도 상승이 아주 가파르게 느껴져서 조금 걱정이다. 오늘처럼 열심히 해보자!
