转载请注明来源-作者@loongshawn：http://blog.csdn.net/loongshawn/article/details/77759475，建议读者阅读原文，确保获得完整的信息

基础概念

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap是对数据结构中哈希表(Hash Table)的实现，Hash表又叫散列表。Hash表是根据关键码Key来访问其对应的值Value的数据结构，它通过一个映射函数把关键码映射到表中一个位置来访问该位置的值，从而加快查找的速度。这个映射函数叫做Hash函数，存放记录的数组叫做Hash表。

源码释义

HashMap中有三个核心数据结构：table[]、单向链表、TreeNode(红黑树)；其中数组为Node[]，其元素是一个Node节点实现：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

既然是一个数组，就有下标，HashMap的数组下标是如何实现的呢，源码是这么写的：

// hash码函数 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // table下标计算 n = tab.length; Node<K,V> p = tab[i = (n - 1) & hash];

即数组的下标index是(length-1)与key的hash值的&(与)运算。在获取到这个index后，会有以下几种情况：

对应节点为null，则插入一个新的Node；对应节点key与put的key相同，则更新value对象。非红黑树节点时，给单链表添加或更新元素。单链表长度大于8时，触发红黑树转换，将该链表结构转为红黑树。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);

既然用到了单链表，那新增元素的位置是如何编排的呢，链表头或链表尾？需要看看put的源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 红黑树分支转换添加 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 单链表添加，通过循环判断，链表大小不超过8，将新元素添加到链表头部；链表大小大于8，则将链表转换为红黑树存储。 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; } } 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(); afterNodeInsertion(evict); return null; }

java8对HashMap进行了优化，当节点个数多了之后使用红黑树存储。这样做的好处是，最坏的情况下即所有的key都Hash冲突，采用链表的话查找时间为O(n)，而采用红黑树为O(logn)，这也是Java8中HashMap性能提升的奥秘。

当然，HashMap内容远不止上面这点，网络上有很多写得很好的文章能够帮助理解其原理。但是有一点一定注意，看源码，因为jdk升级后，其实现改变了，所以不能太依赖网络文章理解，还得辅助看看源码。

参考文章

http://blog.csdn.net/ghsau/article/details/16890151

http://zhangshixi.iteye.com/blog/672697

https://segmentfault.com/a/1190000003016453

http://blog.csdn.net/chenssy/article/details/18323767