Table of Contents
Overall introduction
remove()
LinkedHashSet
Home Java javaTutorial Detailed explanation of Java collection framework LinkedHashSet and LinkedHashMap source code analysis (picture)

Detailed explanation of Java collection framework LinkedHashSet and LinkedHashMap source code analysis (picture)

Mar 28, 2017 am 10:57 AM

Overall introduction

If you have read the previous information about HashSet and HashMap, as well as TreeSet and TreeMap For the explanation, you must be able to think that LinkedHashSet and LinkedHashMap that will be explained in this article are actually the same thing. LinkedHashSet and LinkedHashMap also have the same implementation in Java. The former just wraps the latter, that is to say, inside LinkedHashSet There is a LinkedHashMap (Adapter Pattern). Therefore, this article will focus on analyzing LinkedHashMap.

LinkedHashMap implements the Map interface, which allows elements with key to be null and also allows insertion of value is an element of null. It can be seen from the name that the container is a mixture of linked list and HashMap, which means that it satisfies both HashMap and # Some features of ##linked list. Think of LinkedHashMap as HashMap enhanced with linked list.

Detailed explanation of Java collection framework LinkedHashSet and LinkedHashMap source code analysis (picture)

In fact

LinkedHashMap is a direct subclass of HashMap, The only difference between the two isLinkedHashMap Based on HashMap, all entry are connected in the form of a doubly-linked list. This is to ensure that the iteration sequence of the elements follows The insertion order is the same . The above figure shows the structure diagram of LinkedHashMap. The main part is exactly the same as HashMap, with the addition of header pointing to the head of the doubly linked list (which is a dummy element) , The iteration order of the doubly linked list is the insertion order of entry.

In addition to preserving the order of iteration, this structure also has another advantage:

When iterating LinkedHashMap, there is no need to traverse the entire table like HashMap , and you only need to directly traverse the doubly linked list pointed to by header, that is to say, the iteration time of LinkedHashMap is only the same as that of entry It is related to the number and has nothing to do with the size of table.

There are two parameters that can affect the performance of

LinkedHashMap: initial capacity (initial capacity) and load factor (load factor). The initial capacity specifies the size of the initial table, and the load factor is used to specify the critical value for automatic expansion. When the number of entry exceeds capacity*load_factor, the container will automatically expand and rehash. For scenarios where a large number of elements are inserted, setting a larger initial capacity can reduce the number of rehashes.

When putting the

object into LinkedHashMap or LinkedHashSet, there are two methods that require special attention: hashCode() and equals(). hashCode()The method determines which bucket the object will be placed in. When the hash values ​​of multiple objects conflict, equals() Method determines whether these objects are "the same object". Therefore, if you want to put a custom object into LinkedHashMap or LinkedHashSet, you need *@Override*hashCode() and equals() method.

You can get a

LinkedHashMap that is the same as the source Mapiteration order in the following way:

void foo(Map m) {
    Map copy = new LinkedHashMap(m);

}
Copy after login

For performance reasons ,

LinkedHashMap is asynchronous (not synchronized). If it needs to be used in a multi-threaded environment, programmer needs to be synchronized manually; or LinkedHashMap is packaged in the following way. (wrapped) Synchronized:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

Method analysis

get( )

get(Object<a href="http://www.php.cn/wiki/60.html" target="_blank"> key)</a> method returns the corresponding value based on the specified key value. The process of this method is almost exactly the same as the HashMap.get() method. Readers can refer to the previous article and will not go into details here.

put()

put(K key, V value)The method is to add the specified key, value pair to the map inside. This method will first search map to see if it contains the tuple. If it is included, it will return directly. The search process is similar to the get() method; if it is not found, then A new entry will be inserted through the addEntry(int hash, K key, V value, int bucketIndex) method.

Note that the

insertion here has two meanings:

  1. From the perspective of

    table, new The entry needs to be inserted into the corresponding bucket. When there is a hash conflict, the head insertion method is used to insert the new entry into the head of the conflict linked list. .

  2. header的角度看,新的entry需要插入到双向链表的尾部。

Detailed explanation of Java collection framework LinkedHashSet and LinkedHashMap source code analysis (picture)

addEntry()代码如下:

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容,并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}
Copy after login

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面,这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:

// LinkedHashMap.Entry.addBefor(),将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}
Copy after login

上述代码只是简单修改相关entry的引用而已。

remove()

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。

注意,这里的删除也有两重含义

  1. table的角度看,需要将该entry从对应的bucket里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。

  2. header的角度来看,需要将该entry从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。

Detailed explanation of Java collection framework LinkedHashSet and LinkedHashMap source code analysis (picture)

removeEntryForKey()对应的代码如下:

// LinkedHashMap.removeEntryForKey(),删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {

    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}
Copy after login

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装,对LinkedHashSet函数调用都会转换成合适的LinkedHashMap方法,因此LinkedHashSet的实现非常简单,这里不再赘述。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }

}
Copy after login

The above is the detailed content of Detailed explanation of Java collection framework LinkedHashSet and LinkedHashMap source code analysis (picture). For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Roblox: Bubble Gum Simulator Infinity - How To Get And Use Royal Keys
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Fusion System, Explained
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers Of The Witch Tree - How To Unlock The Grappling Hook
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial
1677
14
PHP Tutorial
1279
29
C# Tutorial
1257
24
Composer: Aiding PHP Development Through AI Composer: Aiding PHP Development Through AI Apr 29, 2025 am 12:27 AM

AI can help optimize the use of Composer. Specific methods include: 1. Dependency management optimization: AI analyzes dependencies, recommends the best version combination, and reduces conflicts. 2. Automated code generation: AI generates composer.json files that conform to best practices. 3. Improve code quality: AI detects potential problems, provides optimization suggestions, and improves code quality. These methods are implemented through machine learning and natural language processing technologies to help developers improve efficiency and code quality.

What does 'platform independence' mean in the context of Java? What does 'platform independence' mean in the context of Java? Apr 23, 2025 am 12:05 AM

Java's platform independence means that the code written can run on any platform with JVM installed without modification. 1) Java source code is compiled into bytecode, 2) Bytecode is interpreted and executed by the JVM, 3) The JVM provides memory management and garbage collection functions to ensure that the program runs on different operating systems.

H5: Key Improvements in HTML5 H5: Key Improvements in HTML5 Apr 28, 2025 am 12:26 AM

HTML5 brings five key improvements: 1. Semantic tags improve code clarity and SEO effects; 2. Multimedia support simplifies video and audio embedding; 3. Form enhancement simplifies verification; 4. Offline and local storage improves user experience; 5. Canvas and graphics functions enhance the visualization of web pages.

How to use MySQL functions for data processing and calculation How to use MySQL functions for data processing and calculation Apr 29, 2025 pm 04:21 PM

MySQL functions can be used for data processing and calculation. 1. Basic usage includes string processing, date calculation and mathematical operations. 2. Advanced usage involves combining multiple functions to implement complex operations. 3. Performance optimization requires avoiding the use of functions in the WHERE clause and using GROUPBY and temporary tables.

Discuss situations where writing platform-specific code in Java might be necessary. Discuss situations where writing platform-specific code in Java might be necessary. Apr 25, 2025 am 12:22 AM

Reasons for writing platform-specific code in Java include access to specific operating system features, interacting with specific hardware, and optimizing performance. 1) Use JNA or JNI to access the Windows registry; 2) Interact with Linux-specific hardware drivers through JNI; 3) Use Metal to optimize gaming performance on macOS through JNI. Nevertheless, writing platform-specific code can affect the portability of the code, increase complexity, and potentially pose performance overhead and security risks.

How to use type traits in C? How to use type traits in C? Apr 28, 2025 pm 08:18 PM

typetraits are used in C for compile-time type checking and operation, improving code flexibility and type safety. 1) Type judgment is performed through std::is_integral and std::is_floating_point to achieve efficient type checking and output. 2) Use std::is_trivially_copyable to optimize vector copy and select different copy strategies according to the type. 3) Pay attention to compile-time decision-making, type safety, performance optimization and code complexity. Reasonable use of typetraits can greatly improve code quality.

How to configure the character set and collation rules of MySQL How to configure the character set and collation rules of MySQL Apr 29, 2025 pm 04:06 PM

Methods for configuring character sets and collations in MySQL include: 1. Setting the character sets and collations at the server level: SETNAMES'utf8'; SETCHARACTERSETutf8; SETCOLLATION_CONNECTION='utf8_general_ci'; 2. Create a database that uses specific character sets and collations: CREATEDATABASEexample_dbCHARACTERSETutf8COLLATEutf8_general_ci; 3. Specify character sets and collations when creating a table: CREATETABLEexample_table(idINT

How to rename a database in MySQL How to rename a database in MySQL Apr 29, 2025 pm 04:00 PM

Renaming a database in MySQL requires indirect methods. The steps are as follows: 1. Create a new database; 2. Use mysqldump to export the old database; 3. Import the data into the new database; 4. Delete the old database.

See all articles