use*_*717 2 hashtable data-structures
我知道散列表可能存在性能问题,但是100万项的散列表怎么能比100项的散列表快？
Bro*_*ass 11
这一切都取决于冲突的数量:如果哈希表中没有任何冲突,有100万个项目,它将比具有100个项目和100个冲突的冲突更快.
如果没有冲突,则查找将仅使用散列键和模数O(1)(参见完美散列).在碰撞的情况下(假设散列表为数组和链接在链表中的碰撞),你必须顺序遍历所有这些,直到你找到有问题的项目,这是100%碰撞率的最坏情况(想想恒定散列函数即)将是O(n).
这取决于所使用的散列算法的效率.
如果小地图中有许多碰撞,而较大的地图中没有碰撞,那么较大的碰撞会更快.
阅读HashMapjavadocs以了解初始容量和负载因子,并阅读有关哈希码(从头开始Object.hashCode()).(Hashtable是一个古老的遗物,不要使用它.)