黑马程序员技术交流社区

标题: 【成都校区】LinkedHashMap 小结 [打印本页]

作者: 生发危稽 时间: 2018-11-22 13:01
标题: 【成都校区】LinkedHashMap 小结
继承了HashMap，自己额外实现了环形双向链表，能保存元素添加的顺序

构造器都差不多，不过加了一个：
initialCapacity, loadFactor, accessOrder

accessOrder：决定了要不要把每次get的Entry排到环形双向链表的最后面

重写了init方法，在跑initialCapacity, loadFactor构造器时会调用，会初始化hearder，并且它的before
和after都引用了header，header的值都是无效值：hash为-1，其它都是null

重写了transfer方法，本来是表数据转义，把旧HashMap的数据转移到新的HashMap，重写后不再重旧表复制
到新表，而是直接从重双向链表中把数据挨个加入新表，新数据也是加入单链表表头

重写了containsValue方法，不再用数组+链表遍历的方式查找value，而是直接遍历双向链表

重写了get方法，在调用父类的get方法获得Entry后，如果Entry不为null，则用返回的Entry调用recordAccess

重写了clear，不但调用父类的clear清除了所有数组，而且自己清洁了双向链表，链表应该是环形的，因为
在init和clear时header都是用 header.before = header.after = header 来初始化的

重写了addEntry，调用父类的addEntry，如果removeEldestEntry返回true，就根据header的key在数组+链表
中删除对应的Entry，因为header的key是null，所以如果removeEldestEntry返回true就删除key为null的Entry

重写了createEntry，不但会把新的Entry插入对应index的链表头，并且把调用addBefore，把新的Entry插入
双向链表的header的before(上一个)

removeEldestEntry：直接返回false

自己写了Entry内部类，继承了HashMap的Entry

新增了而两个属性：before上一个
after后一个

Entry新增方法：

recordAccess：如果accessOrder为true的话，modCount++，并调用remove和addBefore，addBefore传入head

remove：在双向链表中删除当前的Entry

addBefore(Entry)：把this(当前的Entry)插入传进来的Entry的上一个，引用当然会解决了，因为只会影响到
传入的Entry和Entry.before，所以只用到了传入的Entry和Entry.before，在LinkedHashMap里，传入的Entry
为header

recordRemoval(HashMap)：这个直接调用remove，参数都不要了，应该是用来给覆盖的

Iterator：
跟HashMap的Iterator大同小异

lastReturned：最后一个返回的Entry
nextEntry：下一个返回的Entry

因为Iterator是直接迭代双向链表，而双向链表的新元素添加总是添加到上一个，而Iterator迭代是一
直往next走，因此LinkedHashMap的迭代器是有序的，并且是按照添加顺序排列的，不过因为每次调用get，
都会调用recordAccess，如果accessOrder为true的话，每次get的Entry都会排到双向链表的最后面

hashNext：不再是判断是否到了最后一个数组的链表尾，而是判断是否到了header，回到起点说明结束了

remove：

nextEntry：

难道是环形链表？为什么for的结束条件是e == header，这是说最后会回到header吗

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2