Java链表数组

Question

我正在尝试编写一个自定义哈希表，允许存储多个值。

我们是按照以下方式实现的：

1. 创建一个大小为 Integer_MAX（自定义链接列表）的链接列表数组。
2. 将值（int）插入到编号为键号的链接列表中。

这意味着结构如下：

value1 -> value6
NULL
Null
value3 -> value7
Null
...
...(until Int-Max)

现在，由于我们将存储近5亿个键值对，至少会浪费1.6亿个链接列表。

现在，根据我的工作场所的建议，我正在尝试构建具有以下结构的哈希表：

1 -> value1 -> value6
0
0
1 -> value3 -> value7  // here 0/1 bit defines linked lists exits or not
0
...
...(until Int-Max)

有人能帮我看看是否可能构建这样的结构吗？

编辑：

1. 我们为什么要这样做可以在这里找到。
2. Louis Wasserman编写的当前代码可以在这里找到。

- Arpssss

Answer 1

你不能创建泛型类型的数组，因为数组是具体化的类型。泛型是通过类型擦除实现的。

- gkuzmin

---

尝试使用ArrayList。它应该具有接近数组的性能。 - gkuzmin

但是如果我定义一个ArrayList(Int-Max)，它会像数组一样产生影响。抱歉，甚至更像对象。 - Arpssss

我不太清楚你具体想做什么。你是想在当前实现中减少“null”链接的数量吗？还是只想根据某些条件存储链接？ - gkuzmin

请保持Int-Max的大小不变（即O（1）复杂度），但不要因为https://dev59.com/1GbWa4cB1Zd3GeqPacy_而减少大小。 - Arpssss

我可以建议使用抽象节点类CustomHashMap.AbstractNode，其中包括两个子类 - CustomHashMap.EmptyNode和CustomHashMap.NotEmptyNode。 CustomHashMap.EmptyNode应该是一个没有数据的单例。这样，您将有额外的实例检查，但可以减少内存使用量。如果我理解错误或者再次没有理解您的问题，请纠正我。 - gkuzmin

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/14801/discussion-between-gkuzmin-and-arpssss - gkuzmin