我们需要维护mobileNumber及其在内存中的位置 . 挑战在于我们拥有超过500万用户，并且每个用户的存储位置将像500万条记录的哈希 Map . 要解决此问题，我们必须处理范围
我们给出了电话号码的范围
-
range1 start =“9899123446”end =“9912345678”location =“a”
-
range2 start =“9912345679”end =“9999999999”location =“b”
数字只能属于单个位置 .
我们需要一个数据结构来将这些范围存储在内存中 .
它必须支持两个功能
-
findLocation（整数）它应该返回编号所属的位置名称
-
changeLocation（整数，字符串范围） . 它将Number的位置从旧位置更改为新位置
这完全是在内存设计中 .
我打算使用树结构，每个节点包含（startofrange，endofrange，location） . 我将按节目顺序保留节点 . 我还没有完成任何事情 . 主要问题是 - 当第二个改变位置的功能被称为9899123448位置到b时
range1节点应拆分为3个节点第1个节点 (9899123446,9899123447,a) 第2个节点 (9899123448,9899123448,b) 第3个节点 (9899123449,9912345678,a) .
请提出合适的方法，提前致谢
2 回答
通常，您可以使用专门的数据结构来存储范围并实现查询，例如Interval Tree .
但是，由于电话号码范围为 do not overlap ，您可以将范围存储在基于标准树的数据结构中（Binary Search Tree，AVL Tree，Red-Black Tree，B Tree，一切正常）排序 only by [begin] .
对于findLocation（数字），使用相应的树搜索算法查找[begin]值小于该数字的第一个元素，检查其[end]值并验证该数字是否在该范围内 . 如果找到匹配项，则返回该位置，否则该数字不在任何范围内 .
对于changeLocation（）操作：
查找包含该号码的旧节点
如果在步骤1中找到现有节点，则删除它并插入新节点
如果未找到现有节点，请插入新节点并尝试将其与相邻节点合并 .
我假设您使用相同的操作来简单地添加新节点 .
更实际的是，您可以将所有条目存储在数据库中，在[begin]上构建索引 .
首先
range= [begin;end;location]使用两种结构：
排序数组以存储
rangesbegins哈希表通过
begins访问end和location应用以下算法：
使用二进制搜索查找"nearest less" value ob
begin使用hash-table查找
end和locationforbegin