Shulou(Shulou.com)06/02 Report--

Editor to share with you the Java of HashSet principles and common methods of example analysis, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to understand it!

one。 Overview of HashSet

HashSet is an implementation class of Java collection Set, and Set is an interface. Its implementation class includes TreeSet in addition to HashSet, and inherits the Collection,HashSet collection, which is also a knowledge point that programmers are often asked about during interviews. Here is the structure diagram.

Public class HashSetextends AbstractSetimplements Set, Cloneable, java.io.Serializable {}

two。 HashSet construction

HashSet has several overloaded constructions. Let's take a look at it.

Private transient HashMapmap;// default constructor public HashSet () {map = new HashMap ();} / / add the incoming collection to HashSet's constructor public HashSet (Collection)

C) {map = new HashMap (Math.max ((int) (c.size () / .75f) + 1,16)); addAll (c);} / / the constructor public HashSet (int initialCapacity, float loadFactor) {map = new HashMap (initialCapacity, loadFactor) with explicit initial capacity and loading factor;} / / only the constructor with explicit initial capacity (loading factor default 0.75) public HashSet (int initialCapacity) {map = new HashMap (initialCapacity);}

Through the above source code, we found that HashSet is TM is a bag company, it is external to the work, received the work directly thrown to the HashMap processing. Because the underlying layer is implemented through HashMap, here is a brief mention:

HashMap data storage is achieved through the array + linked list / red-black tree, the storage process is probably through the hash function to calculate the location stored in the array, if the location already has a value, determine whether the key is the same, the same will be overwritten, different will be put into the linked list corresponding to the element, if the linked list length is greater than 8, it will be converted into a red-black tree, if the capacity is not enough, it will need to be expanded (note: this is just a rough process).

If you are not clear about the principle of HashMap, you can learn about it first.

HashMap principles (1) Concepts and underlying Architecture

HashMap principle (2) capacity expansion Mechanism and access principle

three。 Add method

HashSet's add method is implemented through HashMap's put method, but HashMap is a key-value key-value pair, and HashSet is a collection, so how is it stored? let's take a look at the source code.

Private static final Object PRESENT = new Object (); public boolean add (E e) {return map.put (e, PRESENT) = = null;}

Look at the source code, we know that the element added by HashSet is stored in the key location of HashMap, while value takes the default constant PRESENT, which is an empty object. As for the put method of map, you can see HashMap principle (II) capacity expansion mechanism and access principle.

four。 Remove method

The remove method of HashSet is realized by the remove method of HashMap.

/ / HashSet's remove method public boolean remove (Object o) {return map.remove (o) = = PRESENT;} / / map's remove method public V remove (Object key) {Nodee; / / find the position of the element in the array through hash (key), and then call the removeNode method to delete return (e = removeNode (hash (key), key, null, false, true)) = = null? Null: e.value;} / * / final NoderemoveNode (int hash, Object key, Object value, boolean matchValue, boolean movable) {Node [] tab; Nodep; int n, index; / / step 1. First, you need to find the exact location of the Node corresponding to key. First, use (n-1) & hash to find the first node if ((tab = table)! = null & & (n = tab.length) > 0 & & (p = tab [index = (n-1) & hash])! = null) {Nodenode = null, e; K k; V v / / 1.1 if the node happens to have the same key value, you are lucky to find if (p.hash = = hash & & (k = p.key) = = key | | (key! = null & & key.equals (k) node = p / * * 1.2Unluckily, the Node found in the array has the same hash, but the key value is different, which is obviously wrong. We need to traverse to continue * look down * / else if ((e = p.next)! = null) {/ / 1.2.1 if it is TreeNode, it means that HashMap is currently stored through an array + red-black tree. Traverse the red-black tree to find the corresponding node if (p instanceof TreeNode) node = ((TreeNode) p) .getTreeNode (hash, key) Else {/ / 1.2.2 if it is a linked list Traverse the linked list to find the corresponding node do {if (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) {node = e Break;} p = e;} while ((e = e.next)! = null) }} / / found the corresponding Node through the previous step 1, and now we need to delete it if (node! = null & &! matchValue | | (v = node.value) = = value | | (value! = null & & value.equals (v) {/ * if it is a TreeNode type The deletion method is implemented through the deletion of red-black tree nodes. For more information, please see [TreeMap principle implementation * and common methods] / if (node instanceof TreeNode) ((TreeNode) node) .removeTreeNode (this, tab, movable) / * in the case of a linked list, when the node found is the first element in the hash position of the array, after the element is deleted, the reference in the first position of the array * can be directed to the next in the linked list * / else if (node = = p) tab [index] = node.next / * if the node found is already a node on the linked list, it is also simple. Point the next of the last node of the node to be deleted to the * next of the node to be deleted, and isolate the node to be deleted * / else p.next = node.next; + + modCount;-- size / / the storage structure may be adjusted after deletion. For more information, please see remove method afterNodeRemoval (node) in [LinkedHashMap how to ensure sequency]; return node;}} return null;}

The concrete realization of removeTreeNode method can refer to the realization of TreeMap principle and common methods.

For the specific implementation of the afterNodeRemoval method, please refer to how to ensure the ordering of LinkedHashMap.

five。 Ergodic

HashSet as a collection, there are a variety of traversal methods, such as ordinary for loop, enhanced for loop, iterator, let's take a look at iterator traversal

Public static void main (String [] args) {HashSetsetString = new HashSet (); setString.add (Monday); setString.add (Tuesday); setString.add (Wednesday); setString.add (Thursday); setString.add (Friday); Iterator it = setString.iterator (); while (it.hasNext ()) {System.out.println (it.next ());}}

What is the result of the print?

Tuesday

Wednesday

It's Thursday

Friday

Monday

Unsurprisingly, HashSet is implemented through HashMap, and HashMap determines the location of storage through hash (key), which does not have storage order, so the elements traversed by HashSet are not in the order in which they are inserted.

six。 Total

According to my previous plan, each piece of main content should be written separately, such as the collection ArrayList,LinkedList,HashMap,TreeMap and so on. However, when I was writing this article about HashSet, I found that after the previous explanation of HashMap, it was really simple. HashSet is a leather company, adding a shell to HashMap, so does LinkedHashSet add a shell to LinkedHashMap, and does TreeSet add a shell to TreeMap? Let's verify it.

Take a look at LinkedHashSet first.

The initial structure diagram has already mentioned that LinkedHashSet is a subclass of HashSet. Let's look at the source code.

Public class LinkedHashSetextends HashSetimplements Set, Cloneable, java.io.Serializable {public LinkedHashSet (int initialCapacity, float loadFactor) {super (initialCapacity, loadFactor, true);} public LinkedHashSet (int initialCapacity) {super (initialCapacity, .75f, true);} public LinkedHashSet () {super (16, .75f, true);} public LinkedHashSet (Collection)

C) {super (Math.max (2*c.size (), 11), .75f, true); addAll (c);} public Spliteratorspliterator () {return Spliterators.spliterator (this, Spliterator.DISTINCT | Spliterator.ORDERED);}}

The above is all the code of LinkedHashSet. Does it feel that IQ has been denied? this is basically nothing. The constructor also calls the parent class. The following is the construction method of its parent class HashSet.

HashSet (int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap (initialCapacity, loadFactor);}

Everyone can see that, like our guess, there is no need to go any further. If you are interested, you can see how LinkedHashMap ensures orderliness.

Take a look at TreeSet again

Public class TreeSetextends AbstractSetimplements NavigableSet, Cloneable, java.io.Serializable {public TreeSet () {this (new TreeMap ());} public TreeSet (Comparator

Comparator) {this (new TreeMap (comparator));} public TreeSet (Collection

C) {this (); addAll (c);} public TreeSet (SortedSets) {this (s.comparator ()); addAll (s);}}

Indeed, as we guessed, TreeSet is also completely dependent on TreeMap for implementation.

The above is all the contents of this article entitled "sample Analysis of HashSet principles and commonly used methods in Java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.