Hash Map采用的是散列表来记录数据，可以把散列表想象成table[]数组，每个下标下标保存一个链表的head，用链表解决hash值冲突的问题，每次添加调用put(key , value),先得到key的hash值然后用hash & (table的长度）来得到这个Node<key,value>应该存放的位置index，为什么不同hash % (table的长度），这里就不详细说明了，得到index后就会查看这个table[index]存不存在数据，如果不存在直接把table[index]指向Node<key,value>,如果存在就会有哈希冲突，就会遍历这个table[index]指向的链表，如果已经存在这个key值就会更新该Node<key, value>中的value值，如果不存在就添加到table[index]指向链表的尾节点。源代码如下：
put(K key, V value)源代码：
public V put(K key, V value) { //hash(key)返回的是key的hash值 return putVal(hash(key), key, value, false, true); }直接调用putVal，putVal的源代码
putVal(int hash, K key, V value, boolean onlyIfAbsent，boolean evict）源代码 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果table为null，返回新的table，相当于初始化table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash算出该node节点插入的位置，如果该链表为空，直接指向该node if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果如果该链表不为空 Node<K,V> e; K k; //如果链表的第一个节点的key值与要插入的node的key值相等，直接替换掉就行 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //如果链表已经变成树，jdk1.8后，链表超过8会转变成红黑树，红黑树大小小于6会转回链表 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //如果是链表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果已经存在key值，替换掉原来的value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //把该新插入的节点移到最后 afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) //扩容就在这个resize()里面，size大于threshold就要扩容 resize(); afterNodeInsertion(evict); return null; }resize()的源代码
>final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //更新新table的容器大小， if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //原来的table指向新的table table = newTab; if (oldTab != null) { //把oldtab的节点移到newtab上 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) //只有一个节点，不用遍历 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //如果是红黑树结构，转向split ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //如果是链表 Node<K,V> loHead = null, loTail = null;//记录在newtab下位置也是j的节点 Node<K,V> hiHead = null, hiTail = null;///记录在newtab下位置是j + oldtab的节点 Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { //如果该节点的(e.hash & oldCap) == 0，说明(e.hash & newCap - 1) == j if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //否则就是(e.hash & newCap - 1) =j + oldtab if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }jdk1.8版本一千发生死循环主要是在把oldtab的节点放到newtable时，多线程发生指向错误的问题，jdk1.8后对此进行了改进。具体细节如下： 1，假如oldtab的大小为2，里面有7，3两个节点，因为2 > 2 * 0.75,现在要扩容到大小为4的newtable，然后把节点从oldtable移到newtable，假设这里有两个线程，每个线程里面都有e，next分别记录当前节点和下一个节点，现在两个线程一起扩容会发生一下情况 首先， 线程（thread1)第一次进入循环，把e1，nex1t分别指向7，3 而此时线程2得到cpu，从的并把扩容的步骤全部做好了，因为jdk1.8后是直接把节点放到newtable[j]尾节点，而jdk1.8前是直接放到头节点，避免了死循环 jdk1.8后升级的 jdk1.8前的 jdk1.8以前发生死循环是这样的，因为thread1的e1节点指向了3节点，next1节点指向7节点。而此时3和7节点在thread2的扩容情况下已经改变了节点的顺序。如果thread1继续扩容就会发生这样的情况： 1，newtable[3]=e1，然后发现next1不为空（此时e1=7，next1=3，newt able[3]=7，3指向7，7指向null） 2，e1=next1（节点3），next1=next1.next(节点7) （e1=3，next1=7，newt able[3]=7，3指向7，7指向null） 3，然后e1.next=newtable[3] ,newtable[3]=e1（e1=3，next1=7，newt able[3]=3，3指向7，7指向null） 4, e1=next1（节点7），next1 = e1.next （e1=7，next1=null，newt able[3]=3，3指向7，7指向null） 5，e1.next = newtable[3] , newtable = e1, e1 = next1 （e1=null，next1=null，newt able[3]=7，3指向7，7指向3） 就会照成死循环。 jdk1.8之前和之后不同之处就是jdk1.8后是直接把节点放到newtable[j]尾节点，而jdk1.8前是直接放到头节点。虽然解决了死循环，但hashMap在多线程使用下还是会有很多问题，在多线程下最好还是使用ConcurrentHashMap比较好。 （以上纯属个人见解，有错误的欢迎提出）
