Content deleted Content added
Make Stack a subheading of Vector |
→Set interfaces: Add subsections |
||
Line 148:
==Set interfaces==
Java's '''{{Javadoc|module=java.base|package=java.util|class=Set|monotype=y}}'''interface defines the <code>Set</code>. A <code>Set</code> can't have any duplicate elements in it. Additionally, the <code>Set</code> has no set order. As such, elements can't be found by index. <code>Set</code> is implemented by '''{{Javadoc|module=java.base|package=java.util|class=HashSet|monotype=y}}''', '''{{Javadoc|module=java.base|package=java.util|class=LinkedHashSet|monotype=y}}''', and '''{{Javadoc|module=java.base|package=java.util|class=TreeSet|monotype=y}}'''.
===HashSet class===
<code>HashSet</code> uses a hash table. More specifically, it uses a '''{{Javadoc|module=java.base|package=java.util|class=LinkedHashMap|monotype=y}}''' to store the hashes and elements and to prevent duplicates.
====
The <code>java.util.LinkedHashSet</code> class extends {{java|HashSet}} by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over the <code>Set</code> is predictable.
===SortedSet interface===
The <code>java.util.SortedSet</code> interface extends the <code>java.util.Set</code> interface. Unlike a regular <code>Set</code>, the elements in a <code>SortedSet</code> are sorted, either by the element's {{Javadoc:SE|module=java.base|name=compareTo(T o)|java/lang|Comparable|compareTo(T)}} method, or a method provided to the constructor of the <code>SortedSet</code>. The first and last elements of the <code>SortedSet</code> can be retrieved using the {{Javadoc:SE|module=java.base|name=first()|java/util|SortedSet|first()}} and {{Javadoc:SE|module=java.base|name=last()|java/util|SortedSet|last()}} methods respectively, and subsets can be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of the <code>SortedSet</code>. The <code>java.util.TreeSet</code> class implements the <code>SortedSet</code> interface.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html |title=SortedSet (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>
The '''{{Javadoc|module=java.base|package=java.util|class=NavigableSet|monotype=y}}''' interface extends the <code>java.util.SortedSet</code> interface and has a few additional methods. The {{Javadoc:SE|module=java.base|name=floor(E e)|java/util|NavigableSet|floor(E)}}, {{Javadoc:SE|module=java.base|name=ceiling(E e)|java/util|NavigableSet|ceiling(E)}}, {{Javadoc:SE|module=java.base|name=lower(E e)|java/util|NavigableSet|lower(E)}}, and {{Javadoc:SE|module=java.base|name=higher(E e)|java/util|NavigableSet|higher(E)}} methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the <code>Set</code> is provided. As with <code>SortedSet</code>, <code>java.util.TreeSet</code> implements <code>NavigableSet</code>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/NavigableSet.html |title=NavigableSet (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06}}</ref>
=====TreeSet class=====
<code>java.util.TreeSet</code> uses a [[red–black tree]] implemented by a '''{{Javadoc|module=java.base|package=java.util|class=TreeMap|monotype=y}}'''. The red–black tree ensures that there are no duplicates. Additionally, it allows <code>TreeSet</code> to implement '''{{Javadoc|module=java.base|package=java.util|class=SortedSet|monotype=y}}'''.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Set.html |title=Set (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>
==Map interfaces==
| |||