Java 数据结构之-LinkedHashMap

继承关系和基本概念

   LinkedHashMap是HashMap的子类，它继承了HashMap的基本功能。它在HashMap的基础上，通过维护一个双向链表来记录元素的插入顺序或者访问顺序（可以通过构造函数指定），从而在遍历元素时能够按照特定的顺序返回元素。

        这种有序性使得LinkedHashMap在一些需要按照特定顺序处理元素的场景中非常有用，例如缓存系统，按照访问顺序来淘汰最近最少访问的元素（LRU 缓存策略）。

底层数据结构组合

   LinkedHashMap底层主要由哈希表（和HashMap类似的数组 + 链表 / 红黑树结构）和一个双向链表组成。

哈希表部分

        哈希表用于快速定位元素。和HashMap一样，它通过对键（key）进行哈希运算，将元素存储在对应的桶（bucket）中。如果多个元素的哈希值对应的桶相同，则在桶内以链表（当链表长度较短时）或者红黑树（当链表长度达到一定阈值时）的形式存储。

        例如，假设有一个简单的哈希函数h(key)，对于键k1、k2和k3，如果h(k1)和h(k2)的值相同，那么k1和k2会被存储在同一个桶中。如果桶中的元素较多，会根据情况将链表转换为红黑树以提高查找效率。

双向链表部分

        双向链表用于维护元素的顺序。当有新元素插入时，会将元素添加到链表的末尾（如果是按照插入顺序）或者将元素移动到链表的末尾（如果是按照访问顺序）。

        假设已经插入了元素e1、e2和e3，它们在双向链表中的顺序为

e1->e2->e3。

        如果按照插入顺序，当插入新元素e4时，它会被添加到链表的末尾，顺序变为

e1->e2->e3->e4。

        如果按照访问顺序，当访问e2时，e2会被移动到链表的末尾，顺序变为

e1->e3->e2。

关键操作的实现细节

插入操作（put）

        首先，LinkedHashMap会调用父类HashMap的put方法来完成元素在哈希表中的插入操作。这个过程包括计算键的哈希值，找到对应的桶，然后将元素插入桶中（可能是链表或者红黑树）。

        在完成哈希表中的插入后，如果是按照插入顺序维护链表，会将新插入的元素添加到双向链表的末尾。如果是按照访问顺序维护链表，此时新插入的元素就已经在链表的末尾了。

访问操作（get）

        当通过get方法获取元素时，LinkedHashMap同样会先在哈希表中查找元素。找到元素后，如果是按照访问顺序维护链表，会将被访问的元素移动到双向链表的末尾。

        例如，有一个LinkedHashMap对象lhmap，执行Object value = lhmap.get(key)操作时，先在哈希表部分找到对应的元素，然后如果是访问顺序模式，会把这个元素在双向链表中的节点移动到末尾，这样就保证了最近访问的元素总是在链表的末尾，方便实现 LRU 等策略。

遍历操作（entrySet、keySet、values）

在遍历LinkedHashMap时，无论是通过entrySet遍历键值对、keySet遍历键或者values遍历值，都是按照双向链表中元素的顺序进行的。

因为双向链表维护了元素的顺序，所以在遍历过程中能够按照插入顺序或者访问顺序返回元素。例如，通过for (Map.Entry<K, V> entry : lhmap.entrySet())遍历LinkedHashMap，会按照链表中的顺序依次返回键值对。