HashMap的实现原理
1、HashMap的数据结构
HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());
在JDK1.7中，HashMap的底层是基于数组和链表来实现的，在JDK1.8中，HashMap的底层是基于数组、链表和红黑树来实现的。数组中存储的元素是链表或红黑树的头结点(一个Entry对象)，链表或红黑树中存储的元素是Entry<K,V>（Entry是HashMap类中的内部类，存储的是键值对，在JDK1.8中使用Node代替Entry），如下图所示。
HashMap中桶的个数就是图中0-n的数组的长度，存储第一个entry的位置叫‘桶（bucket）’，而桶中只能存一个值，也就是链表的头节点，链表的每个节点就是添加的一个entry值，也可以理解成一个存储entry 类型链表的数组，数组的索引位置就是一个个桶的索引地址。
先来看一下Entry的源码：
/** Entry是单向链表，是 “HashMap链式存储法”对应的链表。它实现了Map.Entry接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数**/ （在java 8即JDK1.8中，使用Node代替Entry）
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; // 指向下一个节点 Entry<K,V> next; final int hash; //构造函数。输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判断两个Entry是否相等 // 若两个Entry的“key”和“value”都相等，则返回true。否则，返回false public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } // 实现hashCode() public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } //当向HashMap中添加元素时，会调用recordAccess()。这里不做任何处理 void recordAccess(HashMap<K,V> m) { } //当从HashMap中删除元素时，会调用recordRemoval()。这里不做任何处理 void recordRemoval(HashMap<K,V> m) { }
}
HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。
在java 8即JDK1.8中，使用Node代替Entry。
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;}
}
java.util.Objects.equals方法的源码如下所示：
public static boolean equals(Object a, Object b) {return (a == b) || (a != null && a.equals(b));
}
2、HashMap存储数据的过程
再来看一下HashMap类的部分源码：
下面这几个是HashMap类中的一些关键属性：
transient Entry[] table;//存储元素的实体数组，初始容量默认是16
transient int size;//存放元素的个数
int threshold; //临界值，当实际大小超过临界值时，会进行扩容threshold=加载因子*容量
final float loadFactor; //加载因子，默认值是0.75
transient int modCount;//被修改的次数
public V put(K key, V value) {// 若key为null，则将该键值对添加到table[0]中if (key == null) return putForNullKey(value);//若key不为null，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中int hash = hash(key.hashCode());//搜索指定hash值在对应table中的索引int i = indexFor(hash, table.length);//循环遍历Entry链表，若该key对应的键值对已经存在，则用新value取代旧valuefor (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k;//如果key相同则覆盖并返回旧值//如果两个key的哈希值相同，且key的值也相同，说明这两个key相同if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//修改次数+1modCount++;//将key-value添加到table[i]处，作为链表新的头结点(头插法)，放到桶中//JDK1.7使用头插法，JDK1.8使用尾插法addEntry(hash, key, value, i);return null; //若该key在HashMap中不存在，则存到HashMap中后返回null
}private V putForNullKey(V value) {for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null) { //如果有key为null的对象存在，则覆盖掉V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(0, null, value, 0); //如果键为null的话，则hash值为0return null;
}//计算hash值的方法 通过键的hashCode来计算
static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}//得到hash值之后就会通过hash值计算出应该存储在数组中的索引
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值return h & (length-1); //key的哈希值与桶数取余(取模)，桶数是2的n次幂
}void addEntry(int hash, K key, V value, int bucketIndex) {
//将新Entry作为头结点放到桶中，原来的头结点作为新Entry的下一个节点Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e);if (size++ >= threshold) //如果大于临界值就扩容，以2的倍数扩容resize(2 * table.length);
}void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}Entry[] newTable = new Entry[newCapacity];transfer(newTable); //用来将原先table的元素全部移到newTable里面table = newTable; //再将newTable赋值给tablethreshold = (int)(newCapacity * loadFactor); //重新计算临界值
}
根据以上源码分析可知，当将某个新的键值对Entry<K,V>存储到HashMap中时，大致需要经过下面几个步骤：
1、首先根据hash(key.hashCode())方法计算出新Entry的key的哈希值，接着通过indexFor(hash, table.length)方法计算出key的哈希值在数组table(存储的是Entry)中对应的索引。
2、然后根据索引从数组table中取出该索引位置上的Entry对象。
3、若该Entry对象为空，说明该索引位置上还未存储任何Entry对象，可以直接将这个新的键值对Entry存储到该索引位置对应的桶中(跳过for循环)。
4、若该Entry对象不为空，说明该索引位置上已经存储了Entry对象(有可能是Entry链表)。进入for循环，判断新Entry的key的哈希值与旧Entry的key的哈希值是否相等，若哈希值相等，再通过equals方法，判断新key与旧key的值是否相等。
5、如果新key与旧key的哈希值和值都相等，则用新Entry对象的value覆盖旧Entry对象的value，并返回旧Entry对象的value(返回旧的value值)。
6、如果不相等，进行下一轮for循环，依次判断其他旧Entry对象的key与新Entry对象的key是否相等，如果有相等的key，则用新的value值覆盖原来的value值。如果不存在相等的key，则调用addEntry方法将新Entry对象保存到该索引对应的桶中，即成为链表的新表头，原来的表头Entry设置为新表头的next结点。
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null;
}
从HashMap中get元素时，首先计算key的hash，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
重点看一下indexFor方法，一般对哈希表的散列很自然地会想到用hash值对length取模（即hash%length，除法散列法），Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。
接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的二进制位的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即h&(length-1)的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
如果多个key的哈希值相同的话，根据hash%length(或hash&(length-1))可知，这些Entry必定存储在同一个桶中(数组索引相同)。如多个key的哈希值不同的话，这些Entry也有可能存储在同一个桶中。假设两个key1和key2的哈希值分别是3和7，桶的数量是4(即数组长度为4)，根据hash%length可知，结果都是3，所以存储在同一个桶中。
HashMap小结：
1、HashMap其实就是一个Entry数组，Entry对象中包含了键和值以及指向下一个Entry的next节点，其中next也是一个Entry对象，它就是用来处理hash冲突的。如果两个key的hashCode方法得到的值相同，而key的equals方法得到的值为false，就会形成一个链表。
2、影响HashMap查询速度的因素有容量和负载因子，若容量大负载因子小，则查询速度快，但浪费空间，反之则相反；
3、数组的index值是由hash&(length-1)的值来确定的（key是Entry<K,V>对象的键，hash为key的哈希值，length数组的大小，即桶的数量），如果容量大负载因子小，则index相同（index相同也就是指向了同一个桶）的概率小，链表长度就小，则查询速度快，反之，index相同的概率大，链表比较长，查询速度慢。
4、对于HashMap以及其子类来说，他们是采用hash算法来决定集合中元素的存储位置，当初始化HashMap的时候系统会创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置称为桶（bucket）,每一个桶都有其指定索引，系统可以根据索引快速访问该桶中存储的元素。
5、无论何时HashMap 中的每个桶都只存储一个元素（Entry 对象）。由于Entry对象可以包含一个引用变量用于指向下一个Entry，因此可能出现HashMap 的桶（bucket）中只有一个Entry，但这个Entry指向另一个Entry，这样就形成了一个Entry 链。链表用于解决hash冲突。
3、为什么说HashMap是线程不安全的？
在向HashMap中存储数据时(put方法)，如果HashMap容量不足，需要通过resize方法进行扩容，在resize方法中调用了transfer方法，接下来看一下transfer方法。
正常的ReHash的过程：(此时只有一个线程)
假设原来HashMap的容量为2，存储三个Entry，三个Entry的key的hash值分别是3,7,5，那么这三个Entry都存储在索引为1的桶中，如下图所示。现在对原HashMap进行扩容，假设容量扩大到4，那么，rehash之后的新HashMap如第三步所示。
并发下的rehash：(假设此时有两个线程)
假设线程1刚刚执行到上面的第2行代码就被挂起了，线程1只是把HashMap容量扩大到了4，e指向了key:3，next指向了key:7，而线程2 rehash完成，如下图所示。由于线程1的e指向了key:3，next指向了key:7，在线程2 rehash完成后，线程1的e依然指向key:3，next依然指向key:7，只是此时e和next指向了线程2重组后的链表节点。
接着，线程1继续向下执行。执行第3行代码，求得i=3。执行第4行代码：e.next = newTable[i];(线程1获取到的newTable[i]是key:7，即线程2在索引3上的头节点，因为线程1和2操作的是同一个HashMap，此时key:3的next变成了key:7。由于key:7的next是key:3，即key:3与key:7形成了循环链表。接着线程1执行第5行代码：newTable[i] = e;线程1将数组newTable的索引3的头节点变成了key:3。此时循环链表已形成。) 在上图的线程2中，e指向key:3，e.next为null，next指向key:7，第4行代码执行完之后，e.next依然为null。执行第5行代码：newTable[i] = e; 则线程1的索引为3的桶指向key:3。执行第6行代码：e = next; 由于next原来指向key:7，所以第6行代码执行完之后，e和next都指向了key:7。
当下一次循环开始时，执行第2行代码：Entry<K,V> next = e.next; 此时next指向了key:3，如上图所示。执行第3行代码，求得i=3。执行第4行代码：e.next = newTable[i]; 由上面分析可知，线程1的索引为3的桶指向key:3，即newTable[3]的值是key:3，所以e.next指向key:3(此时e指向key:7，即key:7的下一个节点是key:3)。执行第5行代码：newTable[i] = e; 则线程1的索引为3的桶指向key:7(因为在上面分析中，e指向key:7)。执行第6行代码：e = next; 由于next指向了key:3，所以第6行代码执行完之后，e和next都指向了key:3。
再次执行循环，执行第2行代码：Entry<K,V> next = e.next; 此时next指向了null，如上图所示。执行第3行代码，求得i=3。执行第4行代码：e.next = newTable[i]; 由上面分析可知，线程1的索引为3的桶指向key:7，即newTable[3]的值是key:7，所以e.next指向key:7(此时e指向key:3，即key:3的下一个节点是key:7。由上面的分析可知，key:7的下一个节点是key:3，所以就形成了环形链表)。执行第5行代码：newTable[i] = e; 则线程1的索引为3的桶指向key:3(因为在上面分析中，e指向key:3)。执行第6行代码：e = next; 由于next指向了null，所以第6行代码执行完之后，e和next都指向了null，循环结束。最终结果如下图所示。
由以上分析可知，HashMap线程不安全发生在扩容时。
关于 HashMap 线程不安全这一点，《Java并发编程的艺术》一书中是这样说的：
HashMap在并发执行put操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致HashMap的Node链表形成环形数据结构，一旦形成环形数据结构，Node的next节点永远不为空，就会在获取 Node 时产生死循环。
在jdk1.7及以前，由于HashMap在扩容时使用头插法，会形成循环链表导致死循环。在jdk1.8使用尾插法对HashMap进行扩容，虽然解决了循环链表导致的死循环问题，但是多线程环境下扩容会导致数据被覆盖的问题。
假如线程1向HashMap中put数据，根据数据key的哈希值计算出索引位置，该位置暂无数据，或者已有数据的key与待保存数据的key不同，准备保存数据时，CPU时间片到期，线程1被挂起。此时线程2向HashMap中put数据，根据数据key的哈希值计算出索引位置，恰巧也是在同一个位置，该位置暂无数据，或者已有数据的key与待保存数据的key不同，而且线程1与线程2要保存的数据key也不一样，只是两个key根据哈希值计算出的索引位置相同而已。线程2保存成功之后，线程1获取到CPU执行权，线程1接着保存数据，线程1保存数据成功，此时线程2的数据就会被覆盖掉。因为线程1与线程2保存的数据占据同一个位置，或者是链表中的同一个节点位置。
4、在jdk1.7和1.8中HashMap有什么区别
1、底层数据结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构（当链表长度大于8，转为红黑树）。
2、JDK1.8中resize()方法在表为空时，创建表；在表不为空时，扩容；而JDK1.7中resize()方法负责扩容，inflateTable()负责创建表。
3、1.8中没有区分键为null的情况，而1.7版本中对于键为null的情况调用putForNullKey()方法。但是两个版本中如果键为null，那么调用hash()方法得到的都将是0，所以键为null的元素都始终位于哈希表table【0】中。
4、1.7中新增节点采用头插法，1.8中新增节点采用尾插法。这也是为什么1.8不容易出现环型链表的原因。
5、1.7中扩容时是通过元素的hash值与新数组的长度进行求余计算元素的新位置，1.8中扩容时元素的新位置=元素的旧位置或者旧位置+原数组的长度。
6、在扩容的时候：1.7在插入数据之前扩容，而1.8插入数据成功之后扩容。
5、HashSet的实现原理
HashSet是基于HashMap来实现的，底层采用HashMap来保存元素。
向HashSet中添加元素时，HashSet会先调用元素的hashCode方法得到元素的哈希值，通过元素的哈希值可以算出该元素在哈希表中的存储位置。
情况1：如果存储位置上目前没有存储任何元素，那么该元素可以直接存储到该位置上。
情况2：如果存储位置上已经存在其他元素了，那么会调用该元素的equals方法与该位置的元素进行比较，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素添加成功。
HashSet的部分源码如下所示：
package java.util;
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {static final long serialVersionUID = -5024744406713321676L;// 底层使用HashMap来保存HashSet中所有元素。 private transient HashMap<E,Object> map;// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。 private static final Object PRESENT = new Object();/** * 默认的无参构造器，构造一个空的HashSet。实际底层会初始化一个空的HashMap，* 并使用默认初始容量为16和加载因子0.75。*/ public HashSet() {map = new HashMap<E,Object>();}/** * 构造一个包含指定collection中的元素的新set。实际底层使用默认的加载因子0.75和足* 以包含指定collection中所有元素的初始容量来创建一个HashMap。* @param c 其中的元素将存放在此set中的collection。*/ public HashSet(Collection< extends E> c) {map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));addAll(c);}/** * 以指定的initialCapacity和loadFactor构造一个空的HashSet。* 实际底层以相应的参数构造一个空的HashMap。* @param initialCapacity 初始容量。 * @param loadFactor 加载因子。*/ public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<E,Object>(initialCapacity, loadFactor);}/** * 以指定的initialCapacity构造一个空的HashSet。实际底层以相应的参数及加载因子* loadFactor为0.75构造一个空的HashMap。* @param initialCapacity 初始容量。 */ public HashSet(int initialCapacity) {map = new HashMap<E,Object>(initialCapacity);}/** * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 * @param initialCapacity 初始容量。 * @param loadFactor 加载因子。 * @param dummy 标记。 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);}/** * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 * 底层实际调用底层HashMap的keySet来返回所有的key。可见HashSet中的元素，* 只是存放在了底层HashMap的key上，value使用一个static final的Object对象标识。* @return 对此set中元素进行迭代的Iterator。 */ @Overridepublic Iterator<E> iterator() {return map.keySet().iterator();}/** * 返回此set中的元素的数量（set的容量）。 * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 * @return 此set中的元素的数量（set的容量）。 */ @Overridepublic int size() {return map.size();}/** * 如果此set不包含任何元素，则返回true。 * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 * @return 如果此set不包含任何元素，则返回true。 */ @Overridepublic boolean isEmpty() {return map.isEmpty();}/*** 如果此set包含指定元素，则返回true。 * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))的e元素时，返* 回true。底层实际调用HashMap的containsKey判断是否包含指定key。* @param o 在此set中的存在已得到测试的元素。 * @return 如果此set包含指定元素，则返回true。 */ @Overridepublic boolean contains(Object o) {return map.containsKey(o);}/** * 如果此set中尚未包含指定元素，则添加指定元素。 * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))的元素e2，* 则向此 set 添加指定的元素e。如果此set已包含该元素，则该调用不更改set并返回false。* 底层实际将该元素作为key放入HashMap。由于HashMap的put()方法添加key-value对时，* 当新放入HashMap的Entry中key与集合中原有Entry的key相同（hashCode()返回值相等，* 通过equals比较也返回true），新添加的Entry的value会将覆盖原来Entry的value，但* key不会有任何改变，因此如果向HashSet中添加一个已经存在的元素时，新添加的集合* 元素将不会被放入HashMap中，原来的元素也不会有任何改变，这也就满足了Set中元* 素不重复的特性。* @param e 将添加到此set中的元素。 * @return 如果此set尚未包含指定元素，则返回true。 */ @Overridepublic boolean add(E e) {return map.put(e, PRESENT)==null;}/** * 如果指定元素存在于此set中，则将其移除。 * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，则将其移* 除。若此set已包含该元素，则返回true(或者：如果此set因调用而发生更改，则返回true)。* 一旦调用返回，则此set不再包含该元素。底层实际调用HashMap的remove方法删除指* 定Entry。* @param o 如果存在于此set中则需要将其移除的对象。 * @return 如果set包含指定元素，则返回true。 */ @Overridepublic boolean remove(Object o) {return map.remove(o)==PRESENT;}/** * 从此set中移除所有元素。此调用返回后，该set将为空。 * 底层实际调用HashMap的clear方法清空Entry中所有元素。 */ @Overridepublic void clear() {map.clear();}
}