用于检索特定元素的LinkedHashMap和LinkedHashSet &按插入顺序检索
我做的问题显然需要使用Set，但我需要按插入顺序从集合中检索元素+检索特定的元素。
但是找到特定的元素太慢了(我想是O(n)，因为我必须遍历整个集合才能找到并返回它)。
因此，我使用了一个LinkedHashMap<someClass,someClass>，其中键值映射包含相同的对象。
虽然这样做速度更快，但它消耗的内存是内存的两倍，特别是考虑到我的键/值(无论如何都相同)是否占用了大量空间。
我希望有人对我的问题或优化有更好的解决方案。
编辑:顺便说一下，这个SO answer的注释可能会有所帮助
编辑：
public Set<CompanyDummy> run(int numberOfCompanies)
{
Set<CompanyDummy> companies=new LinkedHashSet<>();
//Create companies
CompanyDummy company;
for(int idx=0;idx<=numberOfCompanies-1;idx++)
{
company=new CompanyDummy(idx);
companies.add(company);
}
//Some code here to fill up each CompanyDummy element with engineers
//At this point,there will be input
//specifying which companies to merge via their index(not reference)
//Problem guarantees those companies exist. Hence, my reason why
//I didn't do something like
//if (set.contains(value)) return value;
//Do note when we merge companies u & v, v is closed down
for(int idx=0;idx<=transactions-1;idx++)
{
companyID= scanner.nextInt();
anotherCompanyID= scanner.nextInt();
//This part is where I search through companies to find if one exists
//which is O(n)
//Replacing sets with maps somehow makes the program faster
//despite LinkedHashSet being backed by LinkedHashMap
company=findCompany(companies, companyID);
anotherCompany=findCompany(companies, anotherCompanyID);
if(company!=null && anotherCompany!=null)
{
company.union(anotherCompany);
companies.remove(anotherCompany);
}
}
}
private CompanyDummy findCompany(Set<CompanyDummy> companies,int id)
{
for(CompanyDummy company : companies)
{
if(company.getIndex()==id)
{
return company;
}
}
return null;
}}
class CompanyDummy
{
private int index;
private Set<Integer> engineers;//The Integer here just denotes the engineer
public CompanyDummy(int index)
{
this.index=index;
}
public int getindex()
{
return index;
}
public void union(CompanyDummy someCompany)
{
this.engineers.addAll(someCompany.engineers);
}}
回答 2
Stack Overflow用户
发布于 2021-01-13 13:34:12
虽然速度更快，但它消耗的内存是内存的两倍，尤其是如果我的键/值(不管怎样都是相同的)占用了大量空间的话。
我不认为LinkedHashMap会更快。考虑到LinkedHashSet是使用后台LinkedHashMap实例实现的，所以与直接使用LinkedHashMap相比，它的开销可能更快一些。
至于内存，无论键/值实例的大小如何，两者都将占用完全相同的内存。您可以看到，当您向LinkedHashSet添加元素X时，它实际上将条目<X,PRESENT>放置到底层LinkedHashMap ( PRESENT是对某个虚拟Object的引用)。使用<X,X>而不是<X,PRESENT>没有什么区别，因为LinkedHashMap只包含对键和值的引用，而不包含键/值实例的副本。
，但是找到特定的元素太慢了(我猜O(n)，因为我必须遍历整个集合才能找到它)
HashSet/LinkedHashSet使用O(1)来确定特定元素是否已经在Set中。您不必对整个Set进行迭代。如果Set包含该元素，则已经有了对它的引用。您不必查找Set元素，它与您正在搜索的元素相等。
Stack Overflow用户
发布于 2021-01-13 13:37:50
在java中，HashSet是使用HashMap实现的。
HashSet确实不是用于特定元素检索的。映射中的键应该标识映射到它的值对象。另外，将复杂的对象作为映射键通常是个坏主意，除非您有一个非常好的HashCode()实现。
map也不会保持插入顺序(LinkedHashMap可能会保留它，因为它是由LinkedList支持的)。可以将键设置为表示插入顺序的整数序列。例如：
Map<Integer, SomeClass> map = new HashMap<>();
map.put(0, object1);
map.put(1, object2);诸若此类。这将比LinkedList更好，因为获取时间是O(1)。稍后，您可以在一个具有正在运行的索引的for循环中获取它们，以便按照插入它们的顺序得到它们。
如果需要防止集合中重复的HashSet属性，则需要保留每个对象的一组唯一标识符。例如，一个人的ID#。在插入到地图上的每个对象之前，您还要检查“唯一键”是否不在集合中，如果是，请将“唯一键”插入到集和映射中。这一切都取决于你的对象的性质。
如果你还需要什么，请在评论中告诉我。祝好运!
https://stackoverflow.com/questions/65702840
复制相似问题
腾讯云开发者
