HashMap 最早出现在 JDK 1.2 中，底层基于散列算法实现。HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。
HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表。数据结构示意图如下：
对于拉链式的散列算法，其数据结构是由数组和链表（或树形结构）组成。在进行增删查等操作时，首先要定位到元素的所在桶的位置，之后再从链表中定位该元素。比如我们要查询上图结构中是否包含元素 35，步骤如下：
定位元素35所处桶的位置，index = 35 % 16 = 3
在3号桶所指向的链表中继续查找，发现35在链表中。
上面就是 HashMap 底层数据结构的原理，HashMap 基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于 JDK 1.8 中引入了红黑树，底层数据结构由数组+链表变为了数组+链表+红黑树，不过本质并未变。
JDK版本 实现方式 节点数>=8 节点数<=61.8以前 数组+单向链表 数组+单向链表 数组+单向链表
1.8以后 数组+单向链表+红黑树 数组+红黑树 数组+单向链表
源码分析
下面开始分析 HashMap 源码实现。
1. Node 节点对象在分析具体代码前，先看 Node 节点对象，这是 HashMap 里面的一个内部类，也是 HashMap 的数据存储对象。具体源码如下：
static class Node<K,V> implements Map.Entry<K,V> { // hash 值 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; } // 返回：key的hashCode值和value的hashCode值进行异或运算结果 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判断相等的依据是，要么是同一个 Node 对象，要么是Map.Entry的一个实例，并且键键、值值都相等就返回True 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; } }