代码之家 › 专栏 › 技术社区 › CodeFusionMobile

比哈希表更好的数据结构来跟踪处理过的记录?

hash data-structures android java

2

CodeFusionMobile · 技术社区 · 15 年前

我正在处理大量的数据库记录,每个记录都有一个唯一的密钥。

由于数据库的性质,我的处理方法可能会遇到同一个键两次,因为它是关系数据库,并且一个记录可能有多个“父”记录。

多次处理记录是浪费宝贵的时间、处理能力、内存和文件大小。因此我需要一种方法来记录我已经处理过的id。

我看过HashTable,因为get和put函数是O(1),而这些是我所需要的惟一函数。然而,实际上有一个(1000+)/Load Factor内存块存储布尔值似乎是浪费内存。另外,我不知道我想要的容量,必须忍受大量的重新编译或分配比我需要更多的内存。

我想我正在寻找一个数据结构,你可以给它添加一个值,如果它已经存在于集合中,它会给你带来某种错误,比如从 put(T value) 方法。

5 回复 | 直到 15 年前

1

4

Mark Storer 15 年前

首先,听起来你想要一套,而不是一张桌子。

其次,如果你想要O(1),你唯一的选择就是哈希集,它有内存开销。如果您愿意使用O(log(n)),那么TreeSet就可以正常工作,无需开销。

第三,如果元素已经存在,set的add(T)将返回false。听起来像你 真正地 想要一套而不是一张桌子。

O(log(n))仍然很快。当然不是O(1),但也不太破旧。你只需要决定(也许在一些测试之后)哪一个适合你。

2

Puce 15 年前

我想你要的是散列集: http://download.oracle.com/javase/6/docs/api/java/util/HashSet.html

3

1

Community Mohan Dere 9 年前

你可以利用 Bloom filter ,而不是hashmap。这是一个概率数据结构。Bloom过滤器的问题是它将给出false+ve。请查看 implementation of bloom filter 。这将是比哈希映射更节省内存和更快的解决方案。

有关Bloom筛选器的详细信息:

4

0

AGrunewald 15 年前

嘿, 因为您使用的是数据库,所以不能只将此信息存储在辅助数据库表或记录中吗?另外,如果您有一个树结构(因为您正在讨论父节点),为什么不使用树遍历算法,该算法标记已处理的节点。看看这些 Breadth First Search/Depth First Search Animations 这些是维基百科上的条目 BFS 和 DFS .

一般来说,我会确保用对象/行跟踪处理标志。而不是单独的数据结构。

5

0

Nate 15 年前

如果结果集的顺序正确,您能把“最后处理的”id保存在内存中吗?这样,您只需检查“当前id”与“最后id”-如果它们不同,则处理掉,否则跳到下一个记录?