使用ArrayList或HashMap

Question

嗨,我有一个关于是否使用ArrayList或的问题HashMap.

我正在尝试构建一个Paint程序.将为每个绘制的对象分配一个唯一的对象ID.

如果我想在单击某个对象时获得快速的检索速度,我应该使用arraylist或hashmap吗？

通常,hashmap具有O(1),而arraylist具有O(n)检索速度.

但是,我认为对于我的情况,因为当我点击一个对象时,我将获得ID,因此数组的索引和我可以做类似ArraylistObject.get(ithElement); ,那么在这种情况下,这也将是一个O(1)检索过程？

任何输入？

谢谢!

Answer 1

如果对象具有可以1对1映射到数组的ID,那么也将是O(1)访问,并且实际上将比hashmap查找稍快(您不必计算哈希).

但是,问题将是删除对象时发生的问题.您将在列表中留下一个洞.在创建新对象时,您可以继续追加到列表中并让它慢慢变得更加分散,或者尝试找到一个备用插槽,在这种情况下,您将进行O(n)搜索备用空间.

简而言之 - 哈希映射可能更合适.

如果它是Java Collections中的ArrayList,那么即使在删除对象之后该数组也应该是连续的(忘记实现细节).但是,如果对象ID与数组索引相同,则行为将更加奇怪,因为删除某个对象后,ID可能会开始指向一个全新的对象,因为所有内容都会向上移动以填补空白.所以绝对是一个HashMap. (2认同)