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的顺序并不跟插入的一致
