为什么哈希图比Trie地图好？ [英] Why are hash maps better than trie maps?

问题描述

通过trie map我的意思是一个关联数组，其中有效负载存储在特里中，而不是哈希表。

By trie map I mean an associative array, where the payloads are stored in a trie instead of a hash table.

当我使用散列图/表时，我使用的键通常是字符串。一些基于地图的地图上的哈希映射有什么优点？我已经读到一个哈希映射更快 - 但是在我看来，一致的哈希函数将必须检查（char）数组的每个元素的最终哈希 - 迭代数组一次。在一个特里，你将同样必须遍历数组一次。

When I'm using a hash map/table, the keys I use are typically strings. What are the advantages of a hash map over some trie based map? I have read that a hash map is faster - but it seems to me that a consistent hash functions would have to check each element of the (char) array for the final hash - iterating over the array once. In a trie you would similarly have to iterate over the array just once.

在我看来，当编码小对象时，这会使用更多的内存（即使你只允许键中的小写字母字符，它是26个指针节点，并且通常是每个键的多个节点），但是在正面方面，您不必担心调整大小。为什么哈希图是如此常见，但我从来没有看过一个特技地图？

It does seem to me that this would use a lot more memory when encoding small objects (even if you only allow lower case alpha characters in the keys, it's 26 pointers per node and often multiple nodes per key), but on the plus side you never have to worry about resizing. Why is it that hash maps are so common, but I've never seen a trie map?

推荐答案

哈希贴图更常见比trie地图因为它们更通用：它们可以被做成任何可以散列的对象，而一个trie在序列上工作。哈希表在通用实现中也具有更好的参考地位，因为它们将元素紧密地存储在一起。

Hash maps are more common than trie maps because they are more generic: they can be made to work on any object that is hashable, while a trie works on sequences. Hash tables also have better locality of reference in common implementations because they store elements close together.

（严格地说，每个对象都是一系列位，将需要用户将其对象序列化，然后将其存储在特里（trie）中。与定义自定义散列函数相比，这是非常不方便的。）

(Strictly speaking, every object is a sequence of bits, but then a generic trie would require the user to serialize their object before storing it in the trie. That's pretty inconvenient compared to defining custom hash functions.)

这篇关于为什么哈希图比Trie地图好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！