java - 表内链接的哈希表

Question

我有这个任务要完成。（我是java新手）。我开始考虑并制定计划。我不是在寻找答案，只是对我的方法的反馈。我应该使用哈希表中的链接方案（不同于常规链接方案）将整数输入到哈希表中。我的想法是使用一个数组列表，这样我就可以在哈希表的每个槽中存储数据+指针。当发生冲突时，找到一个空槽，插入新的整数并将指针从原始散列槽设置到数组列表中的这个新位置。这样我就在数组中构建了一种链表。那有意义吗？有一个关于使用堆栈跟踪可用空间的提示......在这里我不得不说我不确定如何在那个实例中使用堆栈

标签： javahashhashtable

Answer 1

因此，在 java8 hashmap 内部将使用类似于您的方法的链接列表解决冲突之前，如果发生冲突，它将性能从 O(1) 提高到 O(n)，因为 java8 它是通过平衡树处理的，这进一步提高了复杂性O(log n) 在发生碰撞的情况下。您使用列表的方法是正确的，但它涉及到您如何实现它。