Dog foot print

어제 선형탐사 방식을 통하여 해시값 충돌시 해시값을 유효범위까지 늘려 충돌을 우회했다. 그러나 open adress방식을 사용하면 유효범위가 유한하기 때문에 언젠가 충돌이 일어날 수 있었다. 그렇기에 이번에는 chaining 방식을 통해 조금 더 유연한 hash table을 만들어 보겠다. Seperate Chaining Seperate chaining 은 배열에 연결리스트를 넣어서 유한하던 저장공간문제를 해결하는 방식이다. 다만 메모리문제와 탐색시 최악의 시간 복잡도가 O(n)이 된다는 단점도 가지고 있다. Double Linked List function Dictionary(key,value){ return { llink : null, key : key, value : value, rlink : nu..

hash table에 대한 포스팅을 조금 더 찾아봤는데 충돌이 일어날 경우 open adress 방식이나, seperate Chaining 방식으로 해당 충돌을 우회 해야한다고 다들 적어놓았지만 충돌이 일어나 다른 곳에 저장한 후 해당 key로 어떻게 data를 찾는지는 나오지 않았다. 그래서 해시테이블을 직접 만들어 보면 어떨까 싶어 해시테이블 2부를 만들게 되었다. 원시적인 해시테이블 function HashTable(){ let array = []; let size = 20; return { hashFunc(key){ let hashValue = key.length % size; return hashValue; }, add(key,item){ if(array[this.hashFunc(key)] !=..