算法题高性能数据查找

jiangf

现在我有好几个文本文件，这些文件中一共有几百万条数据。文件中每一行为一条记录，每条记录中都有一个字段作为关键字，可以唯一的标明一条记录。这个关键字由字符('0'-'9','A'-'Z','a'-'z')组成。把这些数据都读入内存中后，要按照这个关键字才查找记录。如何建立索引才使查找在常数时间复杂度内完成。

syncpk99

常数时间只能是hash了

hellioncu

你的关键字定长还是变长，长度多少？

cugb_cat

文件一共多大？放内存应该没问题的

blackuhlan

1.都有关键字了还需要索引？索引不在关键字上？
2.考虑建树查找。
3.如果可以最好还是用数据库，通用性比较好。
4.hash其实很失败。
5.我是乱说的。

yulihua49

原帖由 jiangf 于 2009-7-16 10:25 发表
现在我有好几个文本文件，这些文件中一共有几百万条数据。文件中每一行为一条记录，每条记录中都有一个字段作为关键字，可以唯一的标明一条记录。这个关键字由字符('0'-'9','A'-'Z','a'-'z')组成。把这些数据都 ...

平衡二叉树。

openspace

若是用LS说的平衡树，时间复杂度为O(lgN)，N=O(2^20)

"常数时间复杂度"看起来应该用hash，但是有不知道这些记录会不会发生变化，若是变化的话一冲突复杂度就会提升；若是记录集合不会添加或减少记录，可以用一个Perfect Hashing
没用过，只是知道：当关键字集合是静态的时，Perfect Hash的访问时间复杂度为O(1)；不过看起来好像很复杂

sunyu_bit

对关键字见二级或者三级索引，剩下的在索引表内用折半查找，应该效率还不错，直接hash的话冲突会不较多，恐怕不好解决，当然也可以，此外还可以看看trie树