记一次hashmap乱序的问题

你的名字 2022-07-16 17:30 258阅读 0赞

首先交代一下背景，一个用户权限菜单按照数据库字段sort倒序排列,首先sql按照order by sort desc倒序传到前台中的数据没问题，但是将数据转为树节点（此代码是我维护），

简单看了下，他是采用Hashmap.而 Hashmap是无序，所以在网上查了下有序的map，，看到一个说Treemap是有序的，于是改用TreeMap,最后发现还是无序的，key是采用的String.

于是查看源码

![Center][]

从源码中可以看到，是通过key的compareto方法进行比较的，于是查看String实现Comparable的接口compareTo的源码![Center 1][]

从源码中可以看到，String首先将较小长度的字符串与较长字符串比较（如  "abc"和"abcd"），若较小字符串与较长字符串的前几位都想等则较长字符串大，否则就是通过asc码来比较大小。所以TreeMap是不能记录元素的放入顺序的。

结果采用LinkedHashMap解决问题。LinkedHashMap是采用双向链表的方式记录插入的顺序

--------------------

2019-4-9  补充

HashMap 无序的原因就是 它在放入元素的时候，是通过key值产生一个哈希值，然后构造一个node节点放入数组中，每个key产生的哈希值是无法确定的，它在数组中的位置是无法确定的，所以 HashMap中的放入元素是无序的。

LinkedHashMap 是有序的，jdk是1.8 , 我们看下它的放入元素代码：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
            LinkedHashMap.Entry<K,V> p =
                new LinkedHashMap.Entry<K,V>(hash, key, value, e);
            linkNodeLast(p);
            return p;
        }
    
     private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
            LinkedHashMap.Entry<K,V> last = tail;
            tail = p;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
        }
    
    
    static class Entry<K,V> extends HashMap.Node<K,V> {
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
                super(hash, key, value, next);
            }
        }

LinkedHashMap  的 put 方法和 putVal 方法都是共用的 HashMap 里面的。但是它重写了 newNode 方法 ，我们知道 newNode 是 HashMap  在大多数情况下插入数据的方法。

代码中可以看到 LinkedHashMap 底层维护了一个自己的 Entry 实现类 ，这个类 继承了 HashMap.Node ，里面的属性  before 和 after 分别指向前一个元素和后一个元素，你可能已经想到了一种数据结构，没错，它是一个双向链表。并且在 linkNodeLast 中，每个新插入的元素会被放入双向链表的尾部，所以 LinkedHashMap 就是通过自己实现的 Entry 双向链表来保证插入元素的顺序。

[Center]: /images/20220709/e672791990de474f94c5a4bb34abcdb5.png
[Center 1]: /images/20220709/5a027f37dbd04e168224dfd21f2edc65.png