javalinkedhashmap源码解析-java开发java经验技巧

《javalinkedhashmap源码解析-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JavaLinkcdHashMap源码解析-编程开发技术JavaLinkedHashMap源码解析原文出处：liujiacai(@jiacai2050)上周把HashMap.TreeMap这两个Meip体系中比较冇代表性的类介绍完了，大家应该也能体会到，如果该类所对应的数据结构与算法掌握好了，再看这些类的源码真是太简单不过了。其次，我希望大家能够触类旁通，比如我们已经掌握了HashMap的原理，我们可以推知HashSet的内部实现HashSet内部用一个HashMap对象存储数据，更具体些，只用到了key,value全部为一du

2、mmy对象。HashSet这个类太简单了，我不打算单独写文章介绍。今天介绍个比较实用的类LinkedHashMapo签名publicclassLinkcdIIashMapextendsHashMapimplementsMap可以看到，LinkedHashMap是HashMap的一子类，它根据自身的特性修改了HashMap的内部某些方法的实现，要想知道LinkedHashMap具体修改了哪些方法,就需要了解LinkedHashMap的设计原理了。设计原理双向链表LinkedllashMap是key键有

3、序的IlashMap的一种实现。它除了使用哈希表这个数据结构，使用双向链表来保证key的顺序双向链表双向链表算是个很常见的数据结构，上图中的头节点的prev＞尾节点的next指向null,双向链表述有一种变种，见下图preDataVNode1pnLrData®IeX1V11Node2n

4、DataXNodenLinksHead环型双向链表可以看到，这种链表把首尾节点相连，形成一个环。LinkedHashMap中采用的这种环型双向链表，环型双向链表的用途比较多，感兴趣可以看这里：•http://stackoverflow.com/q

5、uestions/3589772/why-exactly-do-we-need-a-circular-linked-list-singly-or-doubly-data-structur双向链表这种数据结构，最关键的是保证在增加节点、删除节点时不要断链，后面在分析LinkedHashMap具体代码时会具体介绍，这里就不赘述了。LinkedHashMap特点一般來说，如果需要使用的Map中的key无序,选择IlashMap；如果要求key有序，则选择TreeMapo但是选择TreeMap就会冇性能问题，因为TreeMap的get操

6、作的时间复杂度是O(log(n))的，相比于HashMap的0(1)还是差不少的，LinkedHashMap的出现就是为了平衡这些因素，使得能够以0(1)时间复杂度増加查找元素，又能够保证key的有序性此外，LinkedHashMap提供了两种key的顺序：•访问顺序(accessorder)。非常实用，口J以使用这种顺序实现LRU(LeastRecentlyUsed)缓存•插入顺序(insertionorde)o同一key的多次插入，并不会影响其顺序源码分析首先打开Eclipse的outline面版看看LinkedHashMa

7、p里面有那些成员OutlineS3CUnkedHashMap»serialVersionUID:longo丫header:Entry□accessOrder:boolean•cLinkedHashMap(inttfloat)•cUnkedHashMapGnt)•cUnkedHashMapO•cLinkedHashMap(Map)•LinkedHashMap(inttfloat,boolean)▲▲initf):voidA^transfer(Entry[),boolea

8、n):void•containsValue(Object):boolean•▲get(Object):V•▲clear。:void►QsEntry►LinkedHashIterator►®Keyiterator►@Valueiterator►®EntryiteratorAnewKeylteratorO:lterator▲▲newValueIterator。：lteratorAnewEntrylteratorO:lterator

9、dA▲createEntry(int,K.V.int):voidQremoveEldestEntry(Entry):booleanLinkedHashMap结构可以看到，由于LinkedHashMap继承自HashMap,所以人部分的方法都是根据key