HashMap无序与LinkedHashMap有序

HashMap为什么是无序？

 

HashMap的数据结构是table[entry],entry是一个链表结构，数据的每个元素是一个链表。不同key，但是具有相同hashcode会落在table[hashcode]的链表上

当使用iterator遍历时，使用如下code：

 

final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {//如果链表中的最后一个元素则取table中的下一个element中的链表
                Entry[] t = table; //HashMap中的table[entry]
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }

 

 

 

如上代码，顺序每次都是固定的，并且按照table+entry链表的顺序，而不是插入顺序。

LinkedHashMap用额外的链表保证插入顺序

 

  void createEntry(int hash, K key, V value, int bucketIndex) {

        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);//插到链表中
        size++;
    }

 

 

 Entry<K,V> nextEntry() {//遍历链表
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }