我想得到一个 list
来自 list
的独特元素元素重复,元素在列表中出现的顺序应保持不变。
为了实现这一点,我可以编写如下算法:
private ArrayList<T> getUnique(ArrayList<T> list)
{
// maintain a hashmap of numbers and a uniqueList to be returned(ArrayList<T>)
// Add element in result list and the hashmap if the element isn't already present in the hashmap, else just add in the hashmap
HashMap<T, Boolean> map = new HashMap<>();
ArrayList<T> uniqueList = new ArrayList<>();
for (T t: list)
{
if (map.get(t) == null)
{
// t wasn't present so, adding them in map as well as in the list
map.put(t, true);
uniqueList.add(t);
}
}
return uniqueList;
}
这个算法需要 O(n)
时间 O(n)
额外空间(用于 HashMap)。
或者简单地说,我可以使用以下语法:
Set<T> set = new LinkedHashSet<>(list);
Java 中的上述语法用于获取 set
来自 list
的独特元素元素出现顺序与list
相同.
然后将此集合转换为列表。 ( ArrayList<T> uniqueList = new ArrayList<>(set);
)
我假设这里的时间复杂度也是 O(n)
.我想知道 Java 使用什么算法。
我看到类名为 LinkedHashSet,所以我认为他们可能使用了一些 LinkedList
实现这一点的概念,所以我查看了源代码,发现了这些东西:
- 在
LinkedHashSet.java
,构造函数看起来像:
143: public LinkedHashSet(Collection<? extends T> c)
144: {
145: super(c);
146: }
here是来源。
- 所以,我查看了父类构造函数,即
HashSet
,我发现:
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
- 接下来,我搜索了
addAll
方法,我在AbstractCollection
找到了类(HashSet
类的祖 parent ),函数定义为:
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
这正在调用 add
这就像:
public boolean add(E e) {
throw new UnsupportedOperationException();
}
here .
我无法理解这一点。他们使用什么算法来完成这项任务?
最佳答案
对于寻找整个故事的人
基于LinkedHashSet的源代码, HashSet , LinkedHashMap .
当构造一个 LinkedHashSet
扩展 HashSet
与其他集合(LinkedHashSet.java line 143)时,
public LinkedHashSet(Collection<? extends T> c)
{
super(c);
}
它将调用(HashSet.java 第 136 行):
public HashSet(Collection<? extends T> c)
{
this(Math.max(2 * c.size(), HashMap.DEFAULT_CAPACITY));
addAll(c);
}
然后调用(HashSet.java 第 122 行):
public HashSet(int initialCapacity, float loadFactor)
{
map = init(initialCapacity, loadFactor);
}
由于 init
方法在 LinkedHashSet
中被重写了
HashMap<T, String> init(int capacity, float load)
{
return new LinkedHashMap<T, String>(capacity, load);
}
支持 map
是一个 LinkedHashMap
。
根据 LinkedHashMap 的 java 文档
This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.
而HashSet
的add
方法是
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
因此,构建的平均时间复杂度为 O(n)。 算法方面,我想你可以去看看LinkedHashMap的代码了解一下。 进一步阅读 How is the internal implementation of LinkedHashMap different from HashMap implementation? , HashSet vs LinkedHashSet
关于java - 在 JRE 中使用什么算法将 ArrayList<T> 转换为 LinkedHashSet<T>,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52457353/