search - Merkle Patricia Tree (Ethereum) 和 Hashtable，哪个搜索速度更快？

Question

目标:

我想实现一个函数，它有一个输入序列“X1,...,Xn”并输出一个有序列表“Xp,..,Xq”，其中所有元素都是不同但有序的。

要求:

• 对于序列“X1,...,Xn”中的每个 Xi，它都是一个 256 位长的字符串。
• 输入序列“X1,...,Xn”可能有相同的元素，这意味着可能存在两个元素Xi和Xj满足Xi=Xj。
• 对于“X1,...,Xn”序列中的相同元素，只输出有序列表中的一个元素。
• 函数的速度应该尽可能快。在功能上使用多少存储量并不重要。
• 序列“X1,...,Xn”的大小为n，n为不超过10000的数。

我的想法:

• 我使用数组来存储最初为空的序列。

• 输入Xi时，首先搜索Hashtable，判断Xi是否已经在上面的数组中。如果是，就放弃它。如果不是，则将 Xi 添加到 Hashtable 和 Array。

• 如果输入序列“X1,...,Xn”的所有元素，我对数组进行排序并输出。

问题:

• 还有 Merkle Patricia 树(以太坊)和 Hashtable，哪一个我应该选择吗？
• 对于 Merkle Patricia Tree (Ethereum) 和 Hashtable，哪个搜索速度更快？
• 或者有没有更好的数据结构来满足这个功能？

Answer 1

如果你想要最快的查找，没有什么能比哈希表更好，但哈希表不适合排序。 merkle patricia trie 允许我们验证大型数据集中的数据完整性。 “Patricia”代表“检索以字母数字编码的信息的实用算法”。由于区 block 链包含敏感的金融交易，因此“默克尔树”在区 block 链中被大量使用。在您的问题中，您担心数据完整性，因为输入是有序的，并且序列中的每个输入可能相同或可能包含相似的元素。这听起来像是 merkle-patricia tree

的完美用例