Uma vez que as árvores splay são usadas para armazenamento em cache, fiquei me perguntando quais são as vantagens do Splay Tree sobre o HashTable quando quero armazenar em cache de forma eficiente?
Quando devo preferir splay tree over hash table?
Eu acho que é um caso mais especializado do que o BST, por favor não ligar para a resposta BST vs Hashtable.
Respostas:
2 para resposta № 1Isso realmente depende do que você entende por eficiência.
Se é sobre o armazenamento / espaço consumido pelos dadosestrutura, eles seriam os mesmos. Por outro lado, quando falamos de complexidade de tempo, ainda dependeria de como sua estrutura de dados está sendo usada.
Se seus usuários disserem, use sua estrutura de dadosDe uma forma que eles estarão acessando dados muito semelhantes (dados relacionados toda vez), o cache usando a árvore splay seria ótimo, já que seu pior caso gira em torno de O (log n), enquanto um hashtable tem o pior caso de O (n).
Uma instância em que uma tabela de hash funcionaria realmenteruim é quando seus hashes são armazenados em menos de 3 baldes ou pior apenas 1 balde ou corrente ou linha. Eu suponho que você poderia imaginar o que acontece quando você tenta acessar os dados.
mas, em geral, quando se trata de cache, a tabela Hash funcionaria muito bem, já que tem uma complexidade média de tempo de O (1).
você também pode pensar desta maneira. Se o que você quer é fazer com que sua estrutura de dados acesse os dados "mais recentes" / "mais acessados" mais rapidamente, você pode considerar trabalhar com árvores splay. mas se você quiser que sua estrutura de dados seja capaz de acessar diferentes tipos de dados com facilidade, convém considerar o uso da tabela de hash.
Além disso, você gostaria de observar que é muito importante ter certeza de escolher uma boa função de hash, tamanho da tabela e estrutura de dados para usar em um bucket para que ela funcione bem com o caso de uso.
De fato, combinar os dois também poderia funcionar :)
Isso é realmente baseado apenas na minha opinião, então eu esperoEu ajudei! É realmente uma comparação muito superficial, sugiro que você apenas google como funciona tanto quando se trata de cache e faça sua própria comparação! Kudos!