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

This article mainly introduces what are the differences between HashMap and Hashtable, the article is very detailed, has a certain reference value, interested friends must read it!

The detailed difference between HashMap and Hashtable 1. Brief introduction: 1. Security.

Hashtable is thread-safe, HashMap is not thread-safe. The performance of HashMap is higher than that of Hashtable. It is recommended to use HashMap if there is no special need when using HashMap. In a multithreaded environment, you need to use the Collections.synchronizedMap () method to obtain a thread-safe collection (Collections.synchronizedMap ()). The principle is that Collections defines an inner class of SynchronizedMap, which implements the Map interface and uses synchronized to ensure thread synchronization when calling the method.

two。 Whether null can be used as key

HashMap can use null as a key, but it is recommended to avoid it as much as possible. When HashMap uses null as its key, it is always stored on the first node of the table array. Hashtable does not allow null to be a key.

3. What has been inherited and what has been achieved?

HashMap inherits AbstractMap,HashTable inherits the Dictionary abstract class, and both implement the Map interface

4. Default capacity and how to expand it

The initial capacity of HashMap is 16 and the initial capacity of Hashtable is 11, and the fill factor of both is 0.75 by default. When HashMap is expanded, the current capacity is doubled, that is, when capacity * 2 is expanded, the capacity is doubled by + 1, that is, capacity * (2x1).

6. Underlying implementation

The underlying implementation of HashMap and Hashtable is array + linked list structure.

7. The method of calculating hash is different

The calculation of hash by Hashtable directly uses the hashcode of key to directly model the length of the table array.

HashMap calculates hash to hash the hashcode of key twice to get a better hash value, and then modulates the length of the table array

2. To elaborate on:

Reference article: www.cnblogs.com/xinzhao/p/5644175.html

What's the difference between HashMap and HashTable? During the interview and being interviewed, I have asked and been asked this question, and I have seen a lot of answers. Today, I decided to write about my ideal answer.

Code version

Every version of JDK is improving. The HashMap and HashTable discussed in this article are based on JDK 1.7.0v67. The source code can be found here

1. time

HashTable is produced in JDK 1.1, while HashMap is produced in JDK 1.2. From the perspective of time, HashMap appears later than HashTable.

two。 Author

Here are the authors of HashTable:

The following code and comments are from java.util.HashTable* @ author Arthur van Hoff* @ author Josh Bloch* @ author Neal Gafter

Here are the authors of HashMap:

The following code and comments are from java.util.HashMap * @ author Doug Lea * @ author Josh Bloch * @ author Arthur van Hoff * @ author Neal Gafter

You can see that the author of HashMap has more than the great god Doug Lea. If you don't know anything about Doug Lea, you can read here.

3. External interface (API)

Both HashMap and HashTable are utility classes that implement key-value mapping based on hash tables. To discuss their differences, let's first take a look at the differences in their exposed API.

3.1 Public Method

In the following two diagrams, I draw the class inheritance system for HashMap and HashTable, and list the externally callable public methods of these two classes.

As can be seen from the figure, the inheritance systems of the two classes are somewhat different. Although the three interfaces of Map, Cloneable and Serializable are implemented. But HashMap inherits from the abstract class AbstractMap, and HashTable inherits from the abstract class Dictionary. The Dictionary class is an obsolete class, as we can see from the comments in its code:

The following code and comments are from java.util.Dictionary * NOTE: This class is obsolete. New implementations should * implement the Map interface, rather than extending this class.

At the same time, we see that HashTable has two more public methods than HashMap. One is elements, which comes from the abstract class Dictionary, which is useless because it is obsolete. Another extra method is contains, which is useless because it has the same function as the containsValue method. The code is the proof:

The following code and comments are from java.util.HashTable public synchronized boolean contains (Object value) {if (value = = null) {throw new NullPointerException ();} Entry tab [] = table; for (int I = tab.length; Imura-> 0;) {for (Entry e = tab [I]; e! = null) E = e.next) {if (e.value.equals (value)) {return true;} return false;} public boolean containsValue (Object value) {return contains (value);}

So in terms of exposed methods, these two classes provide the same functionality. All provide key-value mapping services, you can add, delete, check, change key-value pairs, and provide traversal views for building, value, and key-value pairs. Support for shallow copy and serialization.

3.2 Null Key & Null Value

HashMap supports null keys and null values, and HashTable throws a NullPointerException exception when it encounters a null. This is not because HashTable has any special implementation-level reason that null keys and null values cannot be supported, but only because HashMap does special treatment to null during implementation, setting the hashCode value of null to 0, thus storing it in the 0th bucket of the hash table. Let's take a look at the details of the code with the put method as an example:

The following code and comments come from java.util.HashTablepublic synchronized V put (K key, V value) {/ / if value is null, throw NullPointerException if (value = = null) {throw new NullPointerException () } / / if key is null, throw NullPointerException / /.} the following code and comments from java.util.HasMappublic V put (K key, V value) {if (table = = EMPTY_TABLE) {inflateTable (threshold); / / when key is null, call putForNullKey special handling if (key = = null) return putForNullKey (value) / /...} private V putForNullKey (V value) {/ / key is null, put for (Entry e = table [0]; e! = null; e = e.next) {if (e.key = = null) {V oldValue = e.value; e.value = value; e.recordAccess (this); return oldValue }} modCount++; addEntry (0, null, value, 0); return null;} 4. Realization principle

This section discusses the differences between HashMap and HashTable in terms of data structures and algorithms.

4.1 data structure

Both HashMap and HashTable use hash tables to store key-value pairs. The data structure is basically the same, creating a private inner class Entry inherited from Map.Entry, and each Entry object represents a key-value pair stored in the hash table.

The Entry object uniquely represents a key-value pair and has four properties:

-K key key object

-V value value object

-Hash value of the int hash key object

-Entry entry points to the next Entry object in the linked list, which can be null, indicating that the current Entry object is at the end of the linked list.

It can be said that there are as many Entry objects as there are key-value pairs, so how do you store these Entry objects in HashMap and HashTable so that we can find and modify them quickly? Please look at the picture below.

The figure above shows the memory layout of a HashMap/HashTable with 8 buckets and 5 key-value pairs. You can see that inside HashMap/HashTable there is a reference array of type Entry, which is used to represent the hash table, the length of the array, that is, the number of hash buckets. Each element of the array is an Entry reference. From the properties of the Entry object, we can see that it is a node of the linked list, and each Entry object contains a reference to another Entry object.

It can be concluded that HashMap/HashTable internally implements a hash table using the Entry array, while key-value pairs mapped to the same hash bucket (the same location in the array) are stored using the Entry linked list (resolving hash conflicts).

The following code and comments are from java.util.HashTable/** * The hash table data. * / private transient Entry [] table; the following code and comments are from java.util.HashMap/** * The table, resized as necessary. Length MUST Always be a power of two. * / transient Entry [] table = (Entry []) EMPTY_TABLE

As you can see from the code, the implementation of the two classes is consistent for the internal representation of the hash bucket.

4.2 algorithm

The internal data structure used to represent the hash table has been mentioned in the previous section. HashMap/HashTable also needs an algorithm to map a given key key to a determined hash bucket (array position). It is necessary to have an algorithm to expand the size of the hash table (the size of the array) when there are many key-value pairs in the hash bucket. This section compares the algorithmic differences between the two classes.

The difference between the initial capacity and the capacity of each expansion. Look at the code first:

The following code and comments from the java.util.HashTable// hash table default initial size of 11public Hashtable () {this (11,0.75f);} protected void rehash () {int oldCapacity = table.length; Entry [] oldMap = table; / / each expansion to the original 2n+1 int newCapacity = (oldCapacity > > 20) ^ (h > 12); return h ^ (h > 7) ^ (h > 4) } / / Division static int indexFor (int h, int length) {/ / assert Integer.bitCount (length) = = 1: "length must be a non-zero power of 2"; return h & (length-1);}

As we said, because HashMap uses the power of 2, it does not need to do division in the modular operation, just the sum operation of bits. However, due to the aggravation of the hash conflict, HashMap does some bit operations to break up the data after calling the hashCode method of the object. This article will no longer expand on the question of why these bit calculations can break up the data. If you are interested, you can look here.

If you read the code carefully, you can also find that both HashMap and HashTable use a variable called hashSeed when calculating hash. This is because the Entry objects mapped to the same hash bucket exist in the form of linked lists, and the query efficiency of linked lists is relatively low, so the efficiency of HashMap/HashTable is very sensitive to hash conflicts, so you can open an additional hash (hashSeed) to reduce hash conflicts. Because this is the same point between the two classes, this article is no longer expanded, you are interested to see here. In fact, this optimization has been removed in JDK 1.8, because Entry objects mapped to the same hash bucket (array location) in JDK 1.8 are stored using a red-black tree, which greatly speeds up its lookup efficiency.

5. Thread safety

We say that HashTable is synchronous, but HashMap is not, which means that HashTable does not need to do additional synchronization in the case of multithreading, while HashMap is not. So how does HashTable do it?

The following code and comments come from java.util.HashTablepublic synchronized V get (Object key) {Entry tab [] = table; int hash = hash (key); int index = (hash & 0x7FFFFFFF)% tab.length; for (Entry e = tab [index]; e! = null; e = e.next) {if ((e.hash = = hash) & & e.key.equals (key)) {return e.value }} return null;} public Set keySet () {if (keySet = = null) keySet = Collections.synchronizedSet (new KeySet (), this); return keySet;}

As you can see, and quite simply, public methods such as get use synchronized descriptors. Traversal views such as keySet are wrapped synchronously using Collections.synchronizedXXX.

6. Code style

From my taste, HashMap's code is much cleaner than HashTable. The following HashTable code, I feel a little confused, can not accept this way of code reuse.

The following code and comments are from java.util.HashTable/** * A hashtable enumerator class. This class implements both the * Enumeration and Iterator interfaces, but individual instances * can be created with the Iterator methods disabled. This is necessary * to avoid unintentionally increasing the capabilities granted a user * by passing an Enumeration. * / private class Enumerator implements Enumeration, Iterator {Entry [] table = Hashtable.this.table; int index = table.length; Entry entry = null; Entry lastReturned = null; int type; / * Indicates whether this Enumerator is serving as an Iterator * or an Enumeration. (true-> Iterator) * / boolean iterator; / * * The modCount value that the iterator believes that the backing * Hashtable should have. If this expectation is violated, the iterator * has detected concurrent modification. * / protected int expectedModCount = modCount; Enumerator (int type, boolean iterator) {this.type = type; this.iterator = iterator;} / /...} 7. HashTable has been eliminated, so don't use it in your code.

The following description comes from HashTable's class comments:

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

To put it simply, if you don't need thread safety, use HashMap, and if you need thread safety, use ConcurrentHashMap. HashTable is obsolete, so don't use it in new code.

8. Continuous optimization

Although the public interfaces of HashMap and HashTable should not change, or not frequently. However, each version of JDK optimizes the internal implementation of HashMap and HashTable, such as the red-black tree optimization of JDK 1.8 mentioned above. So try to use the new version of JDK as much as possible. In addition to those cool new features, ordinary API will also have a performance improvement.

Why should HashTable be optimized when it has been eliminated? Because some old code is still using it, after optimizing it, the old code can also get a performance improvement.

These are all the contents of this article entitled "what are the differences between HashMap and Hashtable". Thank you for reading! Hope to share the content to help you, more related 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.