Hash Table 썸네일형 리스트형 Hash Table과 Direct Addressing Table Hash Table이란? Hash는 영어로 여러가지 뜻을 가지고 있지만 "뒤죽박죽" 이라는 뜻도 가지고 있습니다.실제로 Hash Table은 배열에 충분히 큰 공간을 할당(이 공간을 보통 bucket이라고 부름)하고 해싱함수를 이용하여 배열 index에 일정한 값을 적용하여 검색시간을 획기적으로 줄여 O(1)의 시간을 가집니다. 예를 들면 테이블 인덱스에 들어갈 값을 충분히 큰 소수로 숫자를 나눠줍니다. 그리고 해당 숫자의 인덱스에 값을 매핑시킵니다. 키값을 해시함수에 입력시 해시값이 도출됩니다. 일반적인 배열의 경우 데이터를 중간에 추가, 삭제 하면 배열 데이터를 하나씩 앞으로 옮기거나 뒤로 옮겨야하는데 이런 작업을 수행할시 O(n)이라는 시간적, 공간적 비용이 필요합니다. 반면 Hash Table을.. 더보기 이전 1 다음