LinkedHashMap源码分析。

﹏ヽ暗。殇╰゛Y 2024-02-19 16:30 109阅读 0赞
  1. /**
  2. * Map 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于,
  3. * 后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,
  4. * 该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。注意,如果在映射中重新插入 键,则插入顺序不受影响。
  5. * (如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true,
  6. * 则调用时会将键 k 重新插入到映射 m 中。)
  7. * 此实现可以让客户避免未指定的、由 HashMap(及 Hashtable)所提供的通常为杂乱无章的排序工作,
  8. * 同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本,而与原映射的实现无关:
  9. * void foo(Map m) {
  10. * Map copy = new LinkedHashMap(m);
  11. * ...
  12. * }
  13. * 如果模块通过输入得到一个映射,复制这个映射,然后返回由此副本确定其顺序的结果,这种情况下这项技术特别有用。
  14. * (客户通常期望返回的内容与其出现的顺序相同。)
  15. * 提供特殊的构造方法来创建链接哈希映射,该哈希映射的迭代顺序就是最后访问其条目的顺序,
  16. * 从近期访问最少到近期访问最多的顺序(访问顺序)。这种映射很适合构建 LRU 缓存。
  17. * 调用 put 或 get 方法将会访问相应的条目(假定调用完成后它还存在)。
  18. * putAll 方法以指定映射的条目集迭代器提供的键-值映射关系的顺序,为指定映射的每个映射关系生成一个条目访问。
  19. * 任何其他方法均不生成条目访问。特别是,collection 视图上的操作不 影响底层映射的迭代顺序。
  20. * 可以重写 removeEldestEntry(Map.Entry) 方法来实施策略,
  21. * 以便在将新映射关系添加到映射时自动移除旧的映射关系。
  22. * 此类提供所有可选的 Map 操作,并且允许 null 元素。
  23. * 与 HashMap 一样,它可以为基本操作(add、contains 和 remove)提供稳定的性能,
  24. * 假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支,其性能很可能比 HashMap 稍逊一筹,
  25. * 不过这一点例外:LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。
  26. * HashMap 迭代时间很可能开支较大,因为它所需要的时间与其容量 成比例。
  27. * 链接的哈希映射具有两个影响其性能的参数:初始容量和加载因子。它们的定义与 HashMap 极其相似。
  28. * 要注意,为初始容量选择非常高的值对此类的影响比对 HashMap 要小,因为此类的迭代时间不受容量的影响。
  29. * 注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,
  30. * 则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象,
  31. * 则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
  32. * 最好在创建时完成这一操作,以防止对映射的意外的非同步访问:
  33. * Map m = Collections.synchronizedMap(new LinkedHashMap(...));
  34. * 结构修改是指添加或删除一个或多个映射关系,或者在按访问顺序链接的哈希映射中影响迭代顺序的任何操作。
  35. * 在按插入顺序链接的哈希映射中,仅更改与映射中已包含键关联的值不是结构修改。
  36. * 在按访问顺序链接的哈希映射中,仅利用 get 查询映射不是结构修改。)
  37. * Collection(由此类的所有 collection 视图方法所返回)的 iterator 方法返回的迭代器
  38. * 都是快速失败 的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的 remove 方法,
  39. * 其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。
  40. * 因此,面对并发的修改,迭代器很快就会完全失败,而不冒将来不确定的时间任意发生不确定行为的风险。
  41. * 注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。
  42. * 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。
  43. * 因此,编写依赖于此异常的程序的方式是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
  44. * @param <K> 由此映射维护的键的类型
  45. * @param <V> 映射值的类型
  46. */
  47. public class LinkedHashMap<K,V>
  48. extends HashMap<K,V>
  49. implements Map<K,V>
  50. {
  51. private static final long serialVersionUID = 3801124242820219131L;
  52. // 双链表的头。
  53. private transient Entry<K,V> header;
  54. // 这个链接哈希映射的迭代排序方法:true for 访问顺序(access-ordered), false for 插入顺序(insertion-order)。
  55. private final boolean accessOrder;
  56. /**
  57. * 构造一个带指定初始容量和加载因子的空插入顺序 LinkedHashMap 实例。
  58. * @param initialCapacity 初始容量
  59. * @param loadFactor 加载因子
  60. */
  61. public LinkedHashMap(int initialCapacity, float loadFactor) {
  62. super(initialCapacity, loadFactor);
  63. accessOrder = false;
  64. }
  65. /**
  66. * 构造一个带指定初始容量和默认加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
  67. * @param initialCapacity 初始容量
  68. */
  69. public LinkedHashMap(int initialCapacity) {
  70. super(initialCapacity);
  71. accessOrder = false;
  72. }
  73. /**
  74. * 构造一个带默认初始容量 (16) 和加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
  75. */
  76. public LinkedHashMap() {
  77. super();
  78. accessOrder = false;
  79. }
  80. /**
  81. * 构造一个映射关系与指定映射相同的插入顺序 LinkedHashMap 实例。
  82. * 所创建的 LinkedHashMap 实例具有默认的加载因子 (0.75) 和足以容纳指定映射中映射关系的初始容量。
  83. * @param m 要将其映射关系存放在此映射中的映射
  84. */
  85. public LinkedHashMap(Map<? extends K, ? extends V> m) {
  86. super(m);
  87. accessOrder = false;
  88. }
  89. /**
  90. * 构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
  91. * @param initialCapacity 初始容量
  92. * @param loadFactor 加载因子
  93. * @param accessOrder 排序模式 - 对于访问顺序,为 true;对于插入顺序,则为 false
  94. */
  95. public LinkedHashMap(int initialCapacity,
  96. float loadFactor,
  97. boolean accessOrder) {
  98. super(initialCapacity, loadFactor);
  99. this.accessOrder = accessOrder;
  100. }
  101. /**
  102. * 由超类构造函数和伪构造函数(clone、readObject)在将任何条目(entry)插入映射之前调用。初始化链。
  103. */
  104. @Override
  105. void init() {
  106. header = new Entry<>(-1, null, null, null);
  107. header.before = header.after = header;
  108. }
  109. /**
  110. * 将所有项传输到新表数组。此方法由超类resize()方法调用。为了提高性能,它被重写,因为使用链表迭代更快。
  111. * @param newTable 与当前对象相关联的新table[]
  112. * @param rehash 是否计算条目(entry)的哈希值
  113. */
  114. @Override
  115. void transfer(HashMap.Entry[] newTable, boolean rehash) {
  116. int newCapacity = newTable.length;
  117. for (Entry<K,V> e = header.after; e != header; e = e.after) {// 遍历链表
  118. if (rehash)// 是否计算条目(entry)的哈希值
  119. e.hash = (e.key == null) ? 0 : hash(e.key);
  120. int index = indexFor(e.hash, newCapacity);// 返回哈希码e.hash在表中的索引。
  121. e.next = newTable[index];
  122. newTable[index] = e;
  123. }
  124. }
  125. /**
  126. * 如果此映射将一个或多个键映射到指定值,则返回 true。
  127. * 覆盖:类 HashMap<K,V> 中的 containsValue
  128. * @param value 其在此映射中的存在已经测试的值
  129. * @return 如果此映射将一个或多个键映射到指定值,则返回 true
  130. */
  131. public boolean containsValue(Object value) {
  132. // 重写以利用更快的迭代器
  133. if (value==null) {// 为空
  134. for (Entry e = header.after; e != header; e = e.after)// 遍历链表
  135. if (e.value==null)
  136. return true;
  137. } else {// 非空
  138. for (Entry e = header.after; e != header; e = e.after)// 遍历链表
  139. if (value.equals(e.value))
  140. return true;
  141. }
  142. return false;
  143. }
  144. /**
  145. * 返回此映射到指定键的值。如果此映射中没有该键的映射关系,则返回 null 。
  146. * 更确切地讲,如果此映射包含满足 (key==null ? k==null : key.equals(k))
  147. * 的从键 k 到值 v 的映射关系,则此方法返回 v;否则,返回 null。
  148. * (最多只能有一个这样的映射关系。)
  149. * 返回 null 值并不 一定 表明此映射不包含该键的映射关系;也可能此映射将该键显式地映射为 null。
  150. * 可使用 containsKey 操作来区分这两种情况。
  151. * 覆盖:类 HashMap<K,V> 中的 get
  152. * @param key 要返回其关联值的键
  153. * @return V 指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null
  154. */
  155. public V get(Object key) {
  156. Entry<K,V> e = (Entry<K,V>)getEntry(key);
  157. if (e == null)
  158. return null;
  159. e.recordAccess(this); // 记录存取
  160. return e.value;
  161. }
  162. /**
  163. * 从该映射中移除所有映射关系。此调用返回后映射将为空。
  164. * 覆盖:类 HashMap<K,V> 中的 clear
  165. */
  166. public void clear() {
  167. super.clear();// 调用HashMap.clear()方法
  168. header.before = header.after = header;
  169. }
  170. /**
  171. * LinkedHashMap entry.
  172. */
  173. private static class Entry<K,V> extends HashMap.Entry<K,V> {
  174. // 这些字段包含用于迭代的双链表。
  175. Entry<K,V> before, after;
  176. /**
  177. * 创建新条目
  178. * @param hash 哈希值
  179. * @param key 键
  180. * @param value 值
  181. * @param next 下一个条目
  182. */
  183. Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
  184. super(hash, key, value, next);
  185. }
  186. /**
  187. * 从链表中移除此条目(entry)。
  188. * 即:上一个条目的after指向当前条目的after,下一个条目的before指向当前条目的before。
  189. */
  190. private void remove() {
  191. before.after = after;
  192. after.before = before;
  193. }
  194. /**
  195. * 将此条目插入到列表中指定的现有条目之前。
  196. */
  197. private void addBefore(Entry<K,V> existingEntry) {
  198. after = existingEntry;
  199. before = existingEntry.before;
  200. before.after = this;
  201. after.before = this;
  202. }
  203. /**
  204. * 每当Map.get()读取已存在条目的值时,超类就会调用此方法。通过Map.set获取或修改。
  205. * 如果所包围的映射是访问顺序(access-ordered)的,则将该条目移动到列表的末尾;否则,它什么也做不了。
  206. */
  207. void recordAccess(HashMap<K,V> m) {
  208. LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  209. if (lm.accessOrder) {// 如果是访问顺序
  210. lm.modCount++;
  211. remove();// 从链表中移除此条目(entry)。
  212. addBefore(lm.header);// 将此条目插入到列表中指定的现有条目(lm.header)之前。
  213. }
  214. }
  215. /**
  216. * 从链表中移除此条目(entry)。
  217. * @param m
  218. */
  219. void recordRemoval(HashMap<K,V> m) {
  220. remove();
  221. }
  222. }
  223. private abstract class LinkedHashIterator<T> implements Iterator<T> {
  224. Entry<K,V> nextEntry = header.after;
  225. Entry<K,V> lastReturned = null;
  226. /**
  227. * 迭代器认为支持列表应该具有的modCount值。如果违反了此期望,迭代器将检测到并发修改。
  228. */
  229. int expectedModCount = modCount;
  230. /**
  231. * 如果仍有元素可以迭代,则返回 true。
  232. */
  233. public boolean hasNext() {
  234. return nextEntry != header;
  235. }
  236. /**
  237. * 从迭代器指向的 collection 中移除迭代器返回的最后一个元素(可选操作)。
  238. */
  239. public void remove() {
  240. if (lastReturned == null)
  241. throw new IllegalStateException();
  242. if (modCount != expectedModCount)
  243. throw new ConcurrentModificationException();
  244. // 调用HashMap.remove()方法,
  245. LinkedHashMap.this.remove(lastReturned.key);
  246. lastReturned = null;
  247. expectedModCount = modCount;
  248. }
  249. /**
  250. * 返回下一个条目
  251. * @return
  252. */
  253. Entry<K,V> nextEntry() {
  254. if (modCount != expectedModCount)
  255. throw new ConcurrentModificationException();
  256. if (nextEntry == header)
  257. throw new NoSuchElementException();
  258. Entry<K,V> e = lastReturned = nextEntry;
  259. nextEntry = e.after;
  260. return e;
  261. }
  262. }
  263. /**
  264. * key迭代器
  265. */
  266. private class KeyIterator extends LinkedHashIterator<K> {
  267. public K next() { return nextEntry().getKey(); }
  268. }
  269. /**
  270. * value迭代器
  271. */
  272. private class ValueIterator extends LinkedHashIterator<V> {
  273. public V next() { return nextEntry().value; }
  274. }
  275. /**
  276. * 条目迭代器
  277. */
  278. private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
  279. public Map.Entry<K,V> next() { return nextEntry(); }
  280. }
  281. // 这些重写改变了超类视图的iterator()方法的行为
  282. Iterator<K> newKeyIterator() { return new KeyIterator(); }
  283. Iterator<V> newValueIterator() { return new ValueIterator(); }
  284. Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
  285. /**
  286. * 此重写更改超类.put()方法的行为。它使新分配的项插入到链表的末尾,并在适当的情况下删除最年长的条目(the eldest entry)。
  287. * @param hash 根据键计算的哈希值
  288. * @param key 指定值将要关联的键
  289. * @param value 指定键将要关联的值
  290. * @param bucketIndex 在table[]数组上的索引
  291. */
  292. void addEntry(int hash, K key, V value, int bucketIndex) {
  293. super.addEntry(hash, key, value, bucketIndex);
  294. // 如果有指令,则删除最年长的(eldest )条目(entry)
  295. Entry<K,V> eldest = header.after;
  296. if (removeEldestEntry(eldest)) {// 如果此映射移除其最旧的条目(eldest),则返回 true。
  297. removeEntryForKey(eldest.key);// 调用HashMap.removeEntryForKey(),删除并返回与LinkedHashMap中指定键关联的条目。
  298. }
  299. }
  300. /**
  301. * 此重写与addEntry()的不同之处在于,它不会调整表的大小或删除最老的条目(the eldest entry)。
  302. * @param hash 根据键计算的哈希值
  303. * @param key 指定值将要关联的键
  304. * @param value 指定键将要关联的值
  305. * @param bucketIndex 在table[]数组上的索引
  306. */
  307. void createEntry(int hash, K key, V value, int bucketIndex) {
  308. HashMap.Entry<K,V> old = table[bucketIndex];
  309. Entry<K,V> e = new Entry<>(hash, key, value, old);
  310. table[bucketIndex] = e;
  311. e.addBefore(header);// 将此条目插入到列表中指定的现有条目(header)之前。
  312. size++;
  313. }
  314. /**
  315. * 如果此映射移除其最旧的条目,则返回 true。在将新条目插入到映射后,put 和 putAll 将调用此方法。
  316. * 此方法可以提供在每次添加新条目时移除最旧条目的实现程序。
  317. * 如果映射表示缓存,则此方法非常有用:它允许映射通过删除旧条目来减少内存损耗。
  318. * 示例用法:此重写允许映射增加到 100 个条目,然后每次添加新条目时删除最旧的条目,始终维持 100 个条目的稳定状态。
  319. * private static final int MAX_ENTRIES = 100;
  320. * protected boolean removeEldestEntry(Map.Entry eldest) {
  321. * return size() > MAX_ENTRIES;
  322. * }
  323. * 此方法通常不以任何方式修改映射,相反允许映射在其返回值的指引下进行自我修改。
  324. * 使用此方法直接修改映射是 允许的,但是如果它执行了此操作,则一定 返回 false(表示该映射不应进行任何进一步的修改)。
  325. * 在此方法中修改映射后是否返回 true 是不确定的。
  326. * 此实现仅返回 false(这样,此映射的行为将类似于正常映射,即永远不能移除最旧的元素)。
  327. * @param eldest 在映射中最早插入的条目;如果是访问顺序映射,则为最早访问的条目。
  328. * 如果此方法返回 true,则此为将移除的条目。如果导致此调用的 put 或 putAll 调用之前映射为空,
  329. * 则该条目就是刚刚插入的条目;换句话说,如果映射只包含单个条目,则最旧的条目也是最新的条目。
  330. * @return 如果应该从映射移除最旧的条目,则返回 true;如果应该保留,则返回 false。
  331. */
  332. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  333. return false;
  334. }
  335. }

参考:JDK 1.6 API

发表评论

表情:
评论列表 (有 0 条评论,109人围观)

还没有评论,来说两句吧...

相关阅读