Tag: 数据结构

Java Collections Framework中常见方法（大小）的意外复杂性？

最近，我对一些Java集合没有方法size（）的常量时间操作感到惊讶。 虽然我了解到集合的并发实现作为并发增益（在ConcurrentLinkedQueue，ConcurrentSkipListSet，LinkedTransferQueue等中的大小为O（n））的折衷作出了一些妥协，但好消息是这在API文档中有适当的记录。 关注我的是一些集合的方法返回的视图的方法大小的性能。 例如， TreeSet.tailSet返回其元素大于或等于fromElement的支持集部分的视图。 令我惊讶的是，返回的SortedSet上的调用大小在时间上是线性的，即O（n）。 至少这是我设法从OpenJDK的源代码中挖掘出来的：在TreeSet中实现为TreeMap的包装器，在TreeMap中，有一个EntrySetView类，其size方法如下： abstract class EntrySetView extends AbstractSet<Map.Entry> { private transient int size = -1, sizeModCount; public int size() { if (fromStart && toEnd) return m.size(); if (size == -1 || sizeModCount != m.modCount) { sizeModCount = m.modCount; size = 0; Iterator i = iterator(); while (i.hasNext()) { size++; i.next(); } […]

如何在java中实现循环链​​表？

我读了一本关于“数据结构和算法”的书，其中有一些任务要求我实现循环链​​表。 这是一个学习练习，我的代码可能没有很高的标准。 我实现循环链​​表的主要思想是有一个指向最后一个元素的指针，每次添加新项时，最后一个项的字段“next”将刷新为指向新添加的项目。 插入方法工作正常，我可以添加项目没有任何问题，但由于某种原因我无法从列表中删除项目。 以下是“链接”或“节点”的代码： public class Link { public long data; public Link next; public Link(long val) { data = val; next = null; } public void displayLink() { System.out.print(data + ” “); } } // end class 这是执行工作的类的代码，错误显然在这里： public class CircularList { Link first; Link last; public CircularList() { first = null; last […]

Java中可排序的类似HashMap的数据结构？

Java中是否存在某种类似于可以按键或值排序的HashMap的数据结构？ 在PHP中，您可以使用可排序的关联数组。 Java中有这样的东西吗？

结构数组或数组结构？

嗯。 我有一个表，这是一个我需要用Java存储的结构数组。 天真的不用担心内存的方法说这样做： public class Record { final private int field1; final private int field2; final private long field3; /* constructor & accessors here */ } List records = new ArrayList(); 如果我最终使用大量（> 10 6 ）记录，偶尔访问个别记录，一次一个，我怎么能弄清楚前面的方法（ArrayList）如何与优化的存储成本方法进行比较： public class OptimizedRecordStore { final private int[] field1; final private int[] field2; final private long[] field3; Record getRecord(int i) { […]

使用链接列表实现优先级队列

我已经使用链表实现了优先级队列。 在此优先级队列中，最小的int值具有最高值，因此通过调用remove方法将删除最小的方法。 节点类代码 public class Node { public int iData; public Node next; public Node(int x) { iData = x; } public void displayNode() { System.out.println(iData + ” “); } } 链接列表代码 public class LinkList { private Node first; public LinkList() { first = null; } public boolean isEmpty() { return first == null; } […]

分离模型，视图和控制器的最佳方法

我正在考虑将模型视图和Controller-for Java分离并使用Eclipse的最佳方法，如果它有任何区别的话。 我曾经把每个类型的MVC分别放在自己的包中，但我开始认为这不是最好的方法： com.company.client（controler） com.company.client.model com.company.client.view com.company.another（controler） com.company.another.model com.company.another.view com.company.yetAnother（controler） com.company.yetAnother.model com.company.yetAnother.view （假设有很多不同的包，每个包都有自己的视图和模型） 我考虑过使用： com.company.client com.company.another com.company.yetAnother com.company.model.client com.company.model.another com.company.model.yetAnother com.company.view.client com.company.view.another com.company.view.yetAnother 我甚至考虑过将控制器，模型和视图放在不同的项目中。 也许它会更加模块化，我会更确定视图不使用控制器，例如（因为控制器项目将包括视图，但不是相反）。 那么分离M，V和C的最佳方法是什么？ （考虑网络和桌面应用，而不仅仅是网络）

Java中是否存在使用generics（域模型，而不是持久层）的多对多集合？

我似乎在Google中使用了错误的搜索字词… 我为多对多关联编写了一个通用类，但我猜这已经完成了。 它很可能存在于比我自己更好的实现中。 这是我第一次尝试编写generics类。 为了更好地了解我正在寻找的东西，我收录了一些我自己的片段： 我用2个哈希映射支持它： private final Map<T, List> ssForTs = new HashMap<T, List>(); private final Map<S, List> tsForSs = new HashMap<S, List>(); 这是实例化： new ManyToManyAssociations(); 一些可用的方法： public void addAssociation（T t，S s） public void removeAssociation（T t，S s） public List getListOfTs（） public List getListOfSs（） 公共列表 getTsForSs（S s） 公共列表 getSsForTs（T t） 这些方法的名字很差……我道歉。 基本用法是：我可以很容易地找到所有S for T和反向。 您是否可以将链接发布到已包含此function的抛光库中？

从队列中获取O（1）时间的最小值/最大值？

如何在0（1）时间复杂度的任何时间从队列中检索max和min元素？ 之前我使用Collections.max和min来查找元素，但这将是0（n）。

TreeSet的优点和缺点是什么

只是想知道TreeSet的优点和缺点是什么，如果有人能告诉我的话吗？ 谢谢！

JVM的function/不可变数据结构？

有没有人知道Java / JVM数据结构库提供熟悉的Java数据结构的function（也就是function意义上的不可变或“持久”）等价物？ “function”是指对象本身是不可变的，而对这些对象的修改会返回与父对象在适当位置共享相同内部的新对象（为了提高时间和空间的效率;一个天真的实现可以复制整个事物每写一次）。 就像Java的并发库一样，这似乎不是我能够或应该自己实现的东西，所以拥有一个我可以在JVM中使用的function数据结构库会更好。