해시 테이블2 [Javascript] 해시 충돌의 해결 지난번에 해시 테이블을 구현했지만, 해시 충돌을 해결할 수는 없었습니다. 그래서 이번에는 해시 충돌의 해결 방법을 알아보겠습니다. 1. 첫번째 방법, 선형 탐사법 Linear Probing 여태까지 많은 자료구조와 알고리즘을 하면서 선형이라는 이름이 붙으면 어떻게 하는지 기억하시나요? 바로 하나씩 일일히 순서대로 확인했습니다. 바로 선형 탐사법이 이 방식을 이용해서 빈 테이블의 위치를 찾습니다. 선형 방식의 문제들이 그렇듯이 테이블의 크기가 늘어나면 해시의 빠른 연산속도가 느려진다는 단점을 수반합니다. insertLinearProbing(key, value) { const id = this.hash(key); if(this.table[id]) { let flag = true; for (let i = id.. 2021. 11. 22. [Javascript] 해시테이블 이번에 소개드릴 자료구조는 해시테이블입니다. 그동안 배운 자료구조들에서 탐색이 유용하게 쓰였었는데, 이 해시테이블은 탐색을 잘 할 수 있는 자료구조입니다. 1. 테이블과 해시함수 그리고 해시테이블 우선 테이블(Table)은 key와 value가 한 쌍을 갖고 표에 저장된 자료구조입니다. 단순히 표에 저장했다고 해서 테이블 자료구조가 아니라, key와 value가 쌍을 이루고 저장되어야합니다. 근데 key와 value라고하니 자바스크립트에서 떠오르는 한 가지 구조가 있습니다. 바로 key와 value 쌍을 이룬 연관(혹은 연상) 배열 map이었습니다. 그리고 우리는 이 연관 배열을 해시라고도 한다고 했었습니다. 혹은 집합과 유사한 Set도 해시테이블의 일종이라고 할 수 있습니다. 2021.03.15 - [.. 2021. 11. 22. 이전 1 다음 300x250