LinkedHashMap源码分析

约定不等于承诺〃 2024-04-18 09:16 133阅读 0赞

1、特点

LinkedHashMap有序的,内部维护了一个双向链表

2、LinkedHashMap是如何保证顺序的

2.1 核心属性

  1. //是否根据操作顺序排序
  2. final boolean accessOrder;
  3. //链表头节点
  4. transient LinkedHashMap.Entry<K,V> head;
  5. //链表尾节点
  6. transient LinkedHashMap.Entry<K,V> tail;

#

  1. //当accessOrder=true是,LinkedHashMap链表顺序不是根据插入的顺序排序,而是根据操作的顺序显示
  2. @Test
  3. public void test4(){
  4. LinkedHashMap<String,String> map = new LinkedHashMap(16,0.75f,true);
  5. map.put("1","1");
  6. map.put("2","2");
  7. map.put("3","3");
  8. map.get("1");
  9. map.put("4","4");
  10. map.put("3","33");
  11. for(String key : map.keySet()){
  12. System.out.println(key);
  13. }
  14. }
  15. 显示结果为:2 1 4 3

2.2、put()方法

  1. /**
  2. * 1、LinkedHashMap继承了HashMap
  3. * 2、put()方法走HashMap的put方法
  4. *
  5. * 改变:
  6. * 在putVal()方法中,linkedHashMap重写了newNode()方法
  7. */
  8. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  9. //创建一个新节点
  10. LinkedHashMap.Entry<K,V> p =
  11. new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  12. linkNodeLast(p);
  13. return p;
  14. }
  15. private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  16. LinkedHashMap.Entry<K,V> last = tail;
  17. tail = p;
  18. //如果尾节点为空
  19. if (last == null)
  20. //则p为头节点
  21. head = p;
  22. else {
  23. //如果尾结点不为空,p的头结点为原始的尾结点,原始的尾结点的下一节点为p
  24. //这样就形成了链表结构,就有了顺序
  25. p.before = last;
  26. last.after = p;
  27. }
  28. }

3、LinkedHashMap独特的功能

  1. linkedHashMap可以根据操作顺序排序
  2. void afterNodeAccess(Node<K,V> e) {
  3. LinkedHashMap.Entry<K,V> last;
  4. //如果accessOrder=true,且当前节点不是尾结点
  5. if (accessOrder && (last = tail) != e) {
  6. LinkedHashMap.Entry<K,V> p =
  7. (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  8. p.after = null;
  9. //如果当前节点的头结点为空,说明当前节点为头结点,将头结点更新为当前节点的尾结点
  10. if (b == null)
  11. head = a;
  12. else
  13. //如果当前节点不是头结点,则将当前节点头结点的尾结点更新为当前节点的尾结点
  14. b.after = a;
  15. //如果当前节点的尾结点不为空,则说明当前节点再中间不是尾结点,将尾结点的头结点更新为当前节点的头结点
  16. if (a != null)
  17. a.before = b;
  18. else
  19. //如果当前节点是尾结点,则更新last为b节点
  20. last = b;
  21. //如果last(可以理解为倒数第二个节点)节点为空,说明链表中只有一个元素,设置头结点为p
  22. if (last == null)
  23. head = p;
  24. else {
  25. //更新当前节点的前节点为last,last的尾结点为p
  26. p.before = last;
  27. last.after = p;
  28. }
  29. //设置尾结点为p
  30. tail = p;
  31. //更新操作次数
  32. ++modCount;
  33. }
  34. }

发表评论

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

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

相关阅读