试题-假设你用对象来描述客户数据:{ ID（5 digit numeric） Family Name（string） Account Balance（currency） }

题目

假设你用对象来描述客户数据:{ ID（5 digit numeric） Family Name（string） Account Balance（currency） } 如果你有 500,000 条使用该类型实例表示的中国（/中文）客户记录, 那么以下分别使用哪种数据结构可以最快的查找到客户 (1) get IDs from Name ； (2) get Name from ID?

A.(1) Tree with Hash(100 bucket) at leaves(2) Tree with linked list at leaves.

B.(1) Tree with linked list at leaves(2) Array.

C.(1) Tree with linked list at leaves(2) Hash(10,000 buckets)

D.(1) Sort linked list(2) Array.

上一题 下一题

解答

参考答案：B.

Name -> ID 就是 string -> int，字符串最好用 Hash 或 Tree 来索引，不过由于 Name 不是唯一的，一个 Name 可能对应多个 ID，要用 Linked List 做对应过来的结构。所以可以是 Hash + Linked List 或 Tree + Linked List。（Tree 可以用 Trie，复杂度是 O(length(name))，其实 Hash 会更好，理论上复杂度是 O(1)）。
ID -> Name 就是 int(7 digit) -> string，7 位数也就是 1000 w，可以开得下（人家机子好），所以就可以随机查了。

C 0条回复评论

帖子还没人回复快来抢沙发