[해시 테이블] 직접 주소 테이블

등장 배경 해시 테이블은 사전을 구현하는 효율적인 자료구조이다. 우리는 소프트웨어를 만들때 Search, Delete, Insert등의 기능을 자주 필요로 한다. 이때 연결리스트로 이러한 기능을 구현하면, 최악의 경우 O(n)의 수행시간을 가지게 된다. 해시테이블도 이론상 최악의 경우 O(n)의 수행시간의 갖지만, 실제로 성능은 훨씬 좋다고 한다. 합리적인 가정하에서 O(1)의 평균 수행시간을 갖는다고 한다. 직접 주소 테이블 사전을 구현하는 방법 중 하나이다. 해시 테이블은 '키'와 '데이터' 이 두 가지 요소로 이루어져 있는데, '키'를 테이블의 인덱스에 매칭하는 방법이다. 이 같은 방법에서는 기본적인 사전 연산을 구현하기 쉽다. 또한, 이 연산은 빨라 단지 O(1)의 수행시간만 요구한다. 더 나아가 Hash 구조체에 바로 데이터를 넣는 것이 아니라, 다른 객체의 포인터를 넣어둔다면 불필요한 메모리를 아낄 수 있다. 또한, 살펴보면 Table이 자체의 인덱스를 가지고 있어 따로 ...

원문링크 : [해시 테이블] 직접 주소 테이블