HashSet HashTable 与 TreeSet

HashSetClass

HashSetclass is mainly designed to perform high-performance set operations, such as intersection, union, difference, etc. of two sets. A set contains a set of elements that do not occur repeatedly and have no order of attributes. Some features of

HashSet are as follows:

1. The values ​​in HashSet cannot be repeated and there is no order.

2. The capacity of HashSet will be automatically added as needed.

Constructor:

HashSet() The default equality comparator creates an empty new instance.

HashSet(IEnumerable collection) Copies the data in the collection in the specified collection to the collection

HashSet(IEqualityComparer comparer) Creates an empty new instance using the specified equality comparator

HashSet(IEnumerable collection,IEqualityComparer comparer) Instantiates data using the specified comparator and copies the elements in the specified collection to the collection.

Because HashSet is specially designed to do set operations, so many of the methods it provides are related to set operations.

The following is an introduction to some of its common methods

Member type description

Add　　　 Method adds the specified element to the set

Clear　　　 Method clears all elements in the set

Contains　　　 Method determines whether an element is in the HashSet

Exists　　　 Method determines whether the HashSet contains elements matching the specified condition

ExceptWith　　 Method removes all elements in the specified collection from the current HashSet

IntersectWith　　 Method modifies the current HashSet object to only contain this object and the specified Elements present in the set

IsProperSubsetOf Method determines whether the HashSet object is a true subset of the specified set

IsProperSupersetOf Method determines whether the HashSet object is a true superset of the specified set

IsSunsetOf Method determines whether the HashSet object is a child of the specified set Set

IsSupersetOf　 Method determines whether the HashSet object is a superset of the specified set

Remove　　 Method removes the specified element from the HashSet object

RemoveWhere　 Method removes the specified element from the HashSet collection that matches the conditions defined by the specified predicate All elements of

SetEquals　　 Method determines whether the HashSet object contains the same elements as the specified collection

SynmmetricExceptWith　 Method modifies the current HashSet object to only contain elements that exist in this object or the specified set

TrimExcess　　 Method will HashSet The object's capacity is set to the actual number of elements it contains, rounded up to the nearest characteristic and implementation value.

UnionWith Method TreeSet is an ordered set. The elements in the TreeSet will be arranged in ascending order. The default is to arrange in natural ordering, which means that the elements in the TreeSet must implement the Comparable interface. Or have a custom comparator.

We can pass the comparator object that implements the Comparator interface when constructing the TreeSet object.

The difference between TreeSet and HashSet

1. HashSet is implemented through HashMap, and TreeSet is implemented through TreeMap, but Set only uses the key of Map

2. The key of Map and Set have one thing in common The characteristic is the uniqueness of the set. TreeMap has an additional sorting function.

3. hashCode and equal() are used by HashMap. Since there is no need for sorting, you only need to focus on positioning and uniqueness.

a. hashCode It is used to calculate the hash value, and the hash value is used to determine the hash table index.

b. An index in the hash table stores a linked list, so it is necessary to loop through the equal method to compare each item on the chain. Only then can the object truly locate the Entry corresponding to the key value.

c. When putting, if it is not located in the hash table, add an Entry in front of the linked list. If it is located, replace the value in the Entry and return the old value.

4. Since TreeMap needs to be sorted, a Comparator is needed to compare the key values. Of course, it is also positioned using Comparator.

a. Comparator can be specified when creating TreeMap

b. If it is not determined when creating, then The key.compareTo() method will be used, which requires that the key must implement the Comparable interface.

c. TreeMap is implemented using the Tree data structure, so positioning can be completed using the compare interface.

HashTable

Hashtables (hash tables) are not a new concept in the computer field. They were designed to speed up computer processing, which is very slow by today's standards, and they allow you to quickly find a particular entry when querying many data entries. Although modern machines are thousands of times faster, hashtables are still a useful tool to get the best performance from your applications.

Hashtable and HashMap objects allow you to combine a key and a value and input the key/value pair into the table using the put() method. You can then get the value by calling the get() method, passing the key as a parameter. Key and value can be any objects as long as they meet two basic requirements. Note that because keys and values ​​must be objects, primitive types must be converted to objects using methods such as Integer(int).

In order to use an object of a specific class as a key, this class must provide two methods, equals() and hashCode(). These two methods are in java.lang.Object, so all classes can inherit these two methods; however, the implementation of these two methods in the Object class is generally useless, so you usually need to overload these two methods yourself. method.

Equals () method compares its object with another object and returns true if the two objects represent the same information. This method also looks to make sure that both objects belong to the same class. Object.equals() returns true if the two reference objects are identical objects, which explains why this method is generally not a good fit. In most cases, you need a way to compare field by field, so we consider different objects representing the same data to be equal.

The HashCode() method generates an int value by performing a hash function using the contents of the object. Hashtable and HashMap use this value to figure out which bucket (or list) a key/value pair is in. Hashtable performance
The main factor affecting the efficiency of hashtable is the average length of the list in the table, because the average search time is directly related to this average length. Obviously, to reduce the average length, you must increase the number of lists in the hashtable; you will get the best search efficiency if the number of lists is so large that most or all lists contain only one record. However, this may be going too far. If your hashtable has far more lists than data entries, then there is no need for you to make such a memory cost, and in some cases, it is impossible for people to accept this approach.

ashtable and HashMap
The Hashtable and HashMap classes have three important differences. The first difference is mainly for historical reasons. Hashtable is based on the old Dictionary class, and HashMap is an implementation of the Map interface introduced in Java 1.2.

Perhaps the most important difference is that Hashtable's methods are synchronous, while HashMap's methods are not. This means that, although you can use a Hashtable in a multi-threaded application without taking any special action, you must also provide external synchronization for a HashMap. A convenient method is to use the static synchronizedMap() method of the Collections class, which creates a thread-safe Map object and returns it as an encapsulated object. This object's methods allow you to access the underlying HashMap synchronously. The result of this is that you can't cut off synchronization in the Hashtable when you don't need it (such as in a single-threaded application), and synchronization adds a lot of processing overhead.

The third difference is that only HashMap allows you to use null values ​​as the key or value of a table entry. Only one record in a HashMap can be an empty key, but any number of entries can be an empty value. This means that if the search key is not found in the table, or if the search key is found but it is a null value, then get() will return null. If necessary, use the containKey() method to distinguish between these two situations.