Java Hashset Linkedhashset

LinkedHashSet || HashSet

Compare LinkedHashSet and HashSet

Posted by freeCookie🍪 on December 18, 2016

HashSet 和 LinkedHashSet

第一次接触到LinkedHashSet, LC381.Insert Delete GetRandom O(1) - Duplicates allowed 如果用LinkedHashSet 150ms， 用HashSet就要 200ms…

参考

HashSet, TreeSet 和 LinkedHashSet区别

HashSet VS TreeSet VS LinkedHashSet

java 集合

Difference between HashSet, TreeSet and LinkedHashSet

总体看来LinkedHashSet 和 HashSet的区别在于加入时前者是按照链表的顺序排列的， 而hashset则不一定按照加入顺序排列。另外对于iterator().next()，LinkedHashSet更快一些。

According to Javadoc Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the “capacity” of the backing HashMap instance (the number of buckets).The idea is that, when iterator() is called, HashSet needs to link the its elements while LinkedHashSet has the linkage ready. Therefore, HashSet’s iterator() might cost O(n) .

CATALOG
    FEATURED TAGS
    Java Hashset Linkedhashset BFS Array DFS Hashmap Design ICC DP Stack Python Database BinarySearch ArrayList SegmentTree BIT TopologicalSort Bit BST TreeSet TreeMap Trie String LinkedList KMP D&C Greedy Math Backtracking Tree UnionFind TwoPointers C/C++ GC Web Sort Graph DS DL PP ML Sampling Minimax Heap