java - 困惑的Java数据结构

也许标题不合适，但此刻我想不出其他任何标题。我的问题是LinkedList和ArrayList或HashMap和THashMap有什么区别。

是否已经有Java(ex:AVL，红黑)或平衡或不平衡(链表)的树结构。如果这种问题不适合，请让我知道我将其删除。谢谢

最佳答案

ArrayList和LinkedList是List抽象的实现。第一个将列表中的元素保存在一个内部数组中，该数组将根据需要自动重新分配，以为新元素腾出空间。第二个构造一个双向链接的持有者单元列表，每个单元格都引用一个列表元素。尽管各个操作具有相同的语义，但是它们在性能特征上有很大不同。例如:

对get(int)的ArrayList操作需要固定的时间，但是所花费的时间与LinkedList的列表长度成比例。

通过Iterator.remove()删除元素需要花费恒定的时间来获取LinkedList，但它所花费的时间与ArrayList的列表长度成正比。

HashMap和THashMap都是使用哈希表的Map抽象的实现。区别在于每种情况下使用的哈希表数据结构形式。 HashMap类使用封闭式寻址，这意味着表中的每个存储桶都指向一个单独的元素链接列表。 THashMap类使用开放式寻址，这意味着哈希到同一存储桶的元素存储在表本身中。最终结果是THashMap使用更少的内存，并且在大多数操作中比HashMap更快，但是如果您需要映射的键/值对集合，它的速度将慢得多。

有关更多详细信息，请阅读有关数据结构的优秀教科书。如果失败，请查阅Wikipedia中的概念。最后，看一下各个类的源代码。