HashMap

HashMap是基于动态数组和单向链表实现的，具体是怎么实现的呢，我们来看源码

public HashMap() {
    table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
    threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}

首先，在构造方法中会创建一个默认大小为2存储对象为HashMapEntry的table数组

 private static final Entry[] EMPTY_TABLE
     = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

这个HashMapEntry又是什么呢，它保存有4个参数

HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
   this.key = key;
   this.value = value;
   this.hash = hash;
   this.next = next;
}

先了解到这，我们来看看put方法是怎么实现的

@Override 
public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
         if (e.hash == hash && key.equals(e.key)) {
             preModify(e);
             V oldValue = e.value;
             e.value = value;
             return oldValue;
        }
    }

    // No entry for (non-null) key is present; create one
    modCount++;
    if (size++ > threshold) {
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);
    return null;
}

首先，判断key值是否为空，如果为空，则用一个entryForNullKey对象来存储相应数据

private V putValueForNullKey(V value) {
     HashMapEntry<K, V> entry = entryForNullKey;
     if (entry == null) {
         addNewEntryForNullKey(value);
         size++;
         modCount++;
         return null;
     } else {
         preModify(entry);
         V oldValue = entry.value;
         entry.value = value;
         return oldValue;
    }
}

void addNewEntryForNullKey(V value) {
    entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}

else方法是对已有key为null的数据更新，preModify不用管，在HashMap中并无具体实现

继续往下看，我们先跳过for方法，回头再来看，doubleCapacity是对数组扩容的，也就不看了，直接来看addNewEntry方法

void addNewEntry(K key, V value, int hash, int index) {
    table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

这边就是往数组中插入，并将原先位置的数据作为新数据的next变量，举个例子：
put("1","1")，put("qa","2s")，put两个数据，假设这两次的index值获取到的都为0，会怎么处理呢？首先第一次put时，table[0]会直接存相应数据，当第二次put时，table[0]的值就更新为第二次的数据，原先的table[0]会作为现在table[0]的next参数，形成单向链表存储，以后若还有indexi为0的数据过来，则继续按照这种规则规则存储。

再来看看for方法，先判断这个index是否存在数据，不存在则addNewEntry，若存在，则找到这个数据，判断key值和hash值是否相等，若相等，说明是要更新数据，若不等，则需要找到链表的下一个值，再次判断，周而复始。若最终链表循环结束，还是未找到，则走addNewEntry方法，这样就又跟举的例子一样的处理步骤了。

至于HashMap是无序的，那又是为什么呢？

一次主要因为这个index值，put的数据可能会存在table的任何位置上，而读取时是按照从小到大依次读取的，我们来看看读取的源码

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

         HashMapEntry<K, V> entryToReturn = nextEntry;
         HashMapEntry<K, V>[] tab = table;
         HashMapEntry<K, V> next = entryToReturn.next;
         while (next == null && nextIndex < tab.length) {
             next = tab[nextIndex++];
        }
        nextEntry = next;
        return lastEntryReturned = entryToReturn;
}

看while方法，只有当next的值为空，即链表索引都结束了，tab的nextIndex才会加1，再继续找当前链表中的值，所以导致打印出来的所有key的顺序并不跟插入的一致