해시 테이블보다 스플레이 트리의 장점은 무엇입니까?

Question

스레딩 트리가 캐싱에 사용 되었기 때문에 효율적인 캐싱을 원할 때 HashTable에 비해 Splay Tree의 장점은 무엇인가 궁금합니다.

언제 해시 테이블보다 스플레이 트리를 선호해야합니까?

BST보다 더 특수화 된 사례라고 생각합니다. BST vs Hashtable 답변에 연결하지 마십시오.

Answer 1

효율성에 따라 실제로 의미가 달라집니다.

데이터 구조에 의해 소비되는 저장 공간/공간에 있으면 그것들은 동일합니다. 다른 한편, 우리가 시간 복잡성에 관해 이야기 할 때, 그것은 여전히 ​​당신의 데이터 구조가 어떻게 사용되고 있는지에 달려 있습니다.

사용자가 매우 비슷한 데이터 (매번 관련된 데이터)에 액세스하는 방식으로 데이터 구조를 사용하면, 최악의 경우가 O (log n) 주위를 돌고 있기 때문에 스플레이 트리를 사용하여 캐싱이 잘됩니다. 해시 테이블은 O (n)의 최악의 경우를가집니다.

해시 테이블이 실제로 작동하지 않는 경우는 해시가 3 개 미만의 버킷에 저장되거나 1 개의 버킷 또는 체인 또는 스레드가 악화되는 경우입니다. 나는 당신이 데이터에 접근하려고 할 때 어떤 일이 일어날 지 상상할 수 있다고 생각한다.

하지만 일반적으로 캐싱의 경우 O (1)의 평균 시간 복잡성을 갖고 있으므로 해시 테이블은 매우 잘 작동합니다.

당신도이 방법으로 생각할 수 있습니다. 원하는 데이터가 "가장 최근"/ "가장 많이 액세스 된"데이터에 빠르게 액세스 할 수 있도록하려는 경우 스레 드 트리 작업을 고려할 수 있습니다. 그러나 데이터 구조가 다른 종류의 데이터에 쉽게 액세스 할 수있게하려면 해시 테이블을 사용하는 것이 좋습니다.

당신은 유스 케이스와 잘 작동하도록 버킷에 사용할 좋은 해시 함수, 테이블 크기 및 데이터 구조를 선택하는 것이 매우 중요하다는 것을 알고 싶을 것입니다. 두 사람은 또한 :

이 정말 내 의견에 근거 그래서 나는 희망을 내가 도움이 일할 수있는 결합 사실

! 그것은 정말 매우 얕은 비교입니다, 나는 당신이 캐싱과 오리지널 비교를 할 때 어떻게 작동 하는지를 구글에 제안합니다! 명성!