java如何只在4位中存储09范围内的整数，并在HashMap中使用相同的键？

Question

我被要求提出一个解决方案，其中你有一个文件，其中每行代表一个10位数的电话号码，我们需要告诉你一个给定的10位数的电话号码是否存在于文件中

我提出了Trie数据结构，其中每个子元素都是一个整数作为键，Trie作为值的映射

class Trie{

   boolean isEnd;
   Map<Integer, Trie> map = new HashMap<>();
}

我也可以使用int[]arr来存储孩子们

因为我们只有0-9之间的数字，所以我们只能将这些数字存储在4位中。为什么要将“int”或整数作为数据类型。如何在这里减少内存

我们如何在映射或数组中存储这些数字，但不使用int，因为这样会浪费大量内存

此外，还有比Trie更好的解决方案吗

Answer 1

如果你想提高内存效率，我会建议不要使用trie，并推荐一种不同的数据结构。据我所知，你只对回答“我以前见过这个电话号码吗？”虽然可以通过将电话号码视为字符串并将其全部放入trie中来实现这一点，但您不会利用尝试旨在支持的操作（快速前缀搜索、按排序顺序检索元素等），因此您将为不使用的东西付费

此外，让我们考虑一下trie的空间使用情况。即使每个电话号码都有一个很长的公共前缀，trie中的每个节点都需要空间来存储其子指针。如果每个节点只存储一个（64位）指针，则使用的空间量与存储10位电话号码的空间量相同（适合64位整数）。如果电话号码没有长的共享前缀，那么无论哈希表键有多大，每个号码都可能存储10个指针，这是一个巨大的空间爆炸

不要把东西扔进一个特里，我只想用一个简单的香草哈希表。毕竟，哈希表经过专门优化，只支持成员资格查询和成员资格查询。对电话号码进行哈希运算应该不会太糟糕，因为它们可以被压缩成64位整数，并使用各种简单的哈希技术进行哈希运算。这让您可以控制要进行何种时间/空间权衡（较大的表大小会增加内存并减少时间，较小的表会增加时间并减少内存）