ArrayList、HashMap、LinkedList、Has

ArrayList

ArrayList基础知识

了 ArrayList 用来组织一系列同类型的数据对象，支持对数据对象的顺序迭代与随机访问。我们还了解了 ArrayList 所支持的操作以及各项操作的时间复杂度。接下来我们来看看这个类实现了哪些接口。

public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable

我们可以看到，它实现了 4 个接口：List、RandomAccess、Cloneable、Serializable。
官方文档对 List 接口的说明如下：List 是一个有序的集合类型（也被称作序列）。使用 List 接口可以精确控制每个元素被插入的位置，并且可以通过元素在列表中的索引来访问它。列表允许重复的元素，并且在允许 null 元素的情况下也允许多个 null 元素。
List 接口定义了以下方法：

ListIterator<E> listIterator();
void add(int i, E element);
E remove(int i);
E get(int i);
E set(int i, E element);
int indexOf(Object element);

我们可以看到，add、get 等方法都是我们在使用 ArrayList 时经常用到的。在 ArrayList 的源码注释中提到了，ArrayList 使用 Object 数组来存储集合元素。我们来一起看下它的源码中定义的如下几个字段：

/** * 默认初始 capacity. */
private static final int DEFAULT_CAPACITY = 10;
/** * 供空的 ArrayList实例使用的空的数组实例 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 
* 供默认大小的空的 ArrayList 实例使用的空的数组实例。
 * 我们把它和 EMPTY_ELEMENTDATA 区分开来，
以便指导当第一个元素被添加时把内部数组尺寸设为多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放 ArrayList 中的元素的内部数组。
 * ArrayList 的 capacity 就是这个内部数组的大小。
 * 任何 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
的空ArrayList 在第一个元素被添加进来时，其 capacity 都会被扩大至 DEFAULT_CAPACITYhe
*/
transient Object[] elementData; // non-private to simplify nested class
access/** *ArrayList 所包含的元素数 */
private int size;

通过以上字段，我们验证了 ArrayList 内部确实使用一个 Object 数组来存储集合元素。
那么接下来我们看一下 ArrayList 都有哪些构造器，从而了解 ArrayList 的构造过程。

ArrayList 的构造器

首先我们来看一下我们平时经常使用的 ArrayList 的无参构造器的源码：

/** * Constructs an empty list with an initial capacity of ten. */
public  ArrayList() {
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

我们可以看到，无参构造器仅仅是把 ArrayList 实例的 elementData 字段赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
接下来，我们再来看一下 ArrayList 的其他构造器

/** * Constructs an empty list with the specified initial capacity.
 * * @param initialCapacity the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial
capacity
 * is negative
*/
public ArrayList(int initialCapacity) {
 if (initialCapacity > 0) {
 this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) {
 this.elementData = EMPTY_ELEMENTDATA;
 } else {
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 }}
/** * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's *
iterator.
 * * @param c the collection whose elements are to be placed into this
list
 * @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
 elementData = c.toArray();
 if ((size = elementData.length) != 0) {
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, Object[].class);
 } else { 
// replace with empty array.
 this.elementData = EMPTY_ELEMENTDATA;
 }}

通过源码我们可以看到，第一个构造器指定了 ArrayList 的初始 capacity，然后根据这个初始 capacity 创建一个相应大小的 Object 数组。若 initialCapacity 为 0，则将 elementData 赋值为 EMPTY_ELEMENTDATA；若 initialCapacity 为负数，则抛出一个 IllegalArgumentException 异常。
第二个构造器则指定一个 Collection 对象作为参数，从而构造一个含有指定集合对象元素的 ArrayList 对象。这个构造器首先把 elementData 实例域赋值为集合对象转为的数组，而后再判断传入的集合对象是否不含有任何元素，若是的话，则将 elementData 赋值为EMPTY_ELEMENTDATA；若传入的集合对象至少包含一个
元素，则进一步判断 c.toArray 方法是否正确返回了 Object 数组，若不是的话，则需要用 Arrays.copyOf 方法把 elementData 的元素类型改变为 Object。
现在，我们又了解了 ArrayList 实例的构建过程，那么接下来我们来通过 ArrayList的 get、set 等方法的源码来进一步了解它的实现原理。

add 方法源码分析

/** * Appends the specified element to the end of this list.
 * * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
*/public boolean add(E e) {
 ensureCapacityInternal(size + 1); // Increments modCount!!
 elementData[size++] = e;
 return true;
}

我们可以看到，在 add 方法内部，首先调用了 ensureCapacityInternal(size+1)，这
句的作用有两个：
• 保证当前 ArrayList 实例的 capacity 足够大；
• 增加 modCount，modCount 的作用是判断在迭代时是否对 ArrayList 进行了结构性修改。
然后通过将内部数组下一个索引处的元素设置为给定参数来完成了向 ArrayList中添加元素，返回 true 表示添加成功。

get 方法源码分析

/** * Returns the element at the specified position in this list.
 * * @param index index of the element to return 
* @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
*/public E get(int index) {
 rangeCheck(index);
 return elementData(index);}

首先调用了 rangeCheck 方法来检查我们传入的 index 是否在合法范围内，然后调用了 elementData 方法，这个方法的源码如下：

E elementData(int index) {
 return (E) elementData[index];}

set 方法源码分析

/** * Replaces the element at the specified position in this list with
 * the specified element.
 * * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
 rangeCheck(index);
 E oldValue = elementData(index);
 elementData[index] = element;
 return oldValue;}

我们可以看到，set 方法的实现也很简单，首先检查给定的索引是否在合法范围内，若在，则先把该索引处原来的元素存储在 oldValue 中，然后把新元素放到该索引处并返回 oldValue 即可。

LinkedList

LinkedList基础知识

LinkedList 类源码中的注释如下：

/** * 实现了 List 接口的双向链表。实现了所有可选列表操作，
并且可以存储所有类型的元素，包括 null。
 * 对 LinkedList 指定索引处的访问需要顺序遍历整个链表，直到到达指定元素。
 * 注意 LinkedList 是非同步的。若多线程并发访问 LinkedList 对象，
 * 并且至少一个线程对其做结构性修改，
 * 则必须在外部对它进行同步。这通常通过在一些自然封装了
LinkedList 的对象上同步来实现。
 * 若不存在这样的对象，这个 list 应使用Collections.synchronizedList 来包装。
 * 这最好在创建时完成，以避免意外的非同步访问。
 * LinkedList 类的 iterator()方法以及 listIterator()方法返回的迭代器是
fail-fast 的：
 * 在 iterator 被创建后的任何时候，若对 list 进行了结构性修改
 *（以任何除了通过迭代器自己的remove 方法或 add 方法的方式），
 *迭代器会抛出一个ConcurrentModificationException 异常。
 * 因此，在遇到并发修改时，迭代器马上抛出异常，
 *而不是冒着以后可能在不确定的时间发生不确定行为的风险继续。
 *需要注意的是，迭代器的 fail-fast 行为是不能得到保证的，
 *因为通常来说在未同步并发修改面前无法做任何保证。
 *fail-fast 迭代器会尽力抛出ConcurrentModificationException 异常。
 * 因此编写正确性依赖于这个异常的程序是不对的：fail-fast 行为应该仅仅在检测 bugs 时被使用。
 * LinkedList 类是 Java 集合框架中的一员。
*/

当我们需要一种支持高效删除/添加元素的数据结构时，可以考虑使用链表。总的来说，链表具有以下两个优点：
• 插入及删除操作的时间复杂度为 O(1)
• 可以动态改变大小
链表主要的缺点是：由于其链式存储的特性，链表不具备良好的空间局部性，也就是说，链表是一种缓存不友好的数据结构。

Node 类

在 LinkedList 类中我们能看到以下几个字段：

transient int size = 0;
/** * 指向头结点 */
transient Node<E> first;
/*** 指向尾结点 */
transient Node<E> last;

我们看到，LinkedList 只保存了头尾节点的引用作为其实例域，接下来我们看一下 LinkedList 的内部类 Node 的源码如下：

private static class Node<E> {
 E item;
 Node<E> next;
 Node<E> prev;
 Node(Node<E> prev, E element, Node<E> next) {
 this.item = element;
 this.next = next;
 this.prev = prev;
 }}

每个 Node 对象的 next 域指向它的下一个结点，prev 域指向它的上一个结点，item为本结点所存储的数据对象。

HashMap

HashMap基础知识

HashMap 是基于 Map 接口实现的一种键-值对<key,value>的存储结构，允许 null 值，同时非有序，非同步(即线程不安全)。HashMap 的底层实现是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）。它存储和查找数据时，是根据键 key 的 hashCode的值计算出具体的存储位置。HashMap 最多只允许一条记录的键 key 为 null，HashMap 增删改查等常规操作都有不错的执行效率，是 ArrayList 和 LinkedList
等数据结构的一种折中实现。
如果没有指定初始大小，默认底层 hash 表数组的大小为 16

HashMap 的底层实现是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分），核心
组成元素有：
int size;用于记录 HashMap 实际存储元素的个数；
float loadFactor;负载因子（默认是 0.75，此属性后面详细解释）。
int threshold;下一次扩容时的阈值，达到阈值便会触发扩容机制 resize
（阈值 threshold = 容器容量 capacity * 负载因子 load factor）。也就是
说，在容器定义好容量之后，负载因子越大，所能容纳的键值对元素个数
就越多。
Node<K,V>[] table; 底层数组，充当哈希表的作用，用于存储对应 hash
位置的元素 Node<K,V>，此数组长度总是 2 的 N 次幂。（具体原因后面详细解释）

public class HashMap<K,V> extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable {
·····
 /* ---------------- Fields -------------- */
 /**
 * 哈希表，在第一次使用到时进行初始化，重置大小是必要的操作，
 * 当分配容量时，长度总是 2 的 N 次幂。
 */
 transient Node<K,V>[] table;
 /**
 * 实际存储的 key - value 键值对 个数
 */
 transient int size;
 /**
 * 下一次扩容时的阈值
 * (阈值 threshold = 容器容量 capacity * 负载因子 load factor).
 * @serial
 */
 int threshold;
 /**
 * 哈希表的负载因子
 *
 * @serial
 */
 final float loadFactor;
·····}

• 其中 Node<K,V>[] table;哈希表存储的核心元素是Node<K,V>,
Node<K,V>包含：
1、final int hash;元素的哈希值，决定元素存储在 Node<K,V>[] table;哈希表中的位置。由 final 修饰可知，当 hash 的值确定后，就不能再修改。
2、final K key; 键，由 final 修饰可知，当 key 的值确定后，就不能再修
改。
3、V value; 值
4、Node<K,V> next; 记录下一个元素结点(单链表结构，用于解决 hash 冲突)

/**
 * 定义 HashMap 存储元素结点的底层实现
 */
 static class Node<K,V> implements Map.Entry<K,V> {
 final int hash;//元素的哈希值 由 final 修饰可知，当 hash 的值确定
后，就不能再修改
 final K key;// 键，由 final 修饰可知，当 key 的值确定后，就不能再
修改
 V value; // 值
 Node<K,V> next; // 记录下一个元素结点(单链表结构，用于解决 hash
冲突)

 /**
 * Node 结点构造方法
 */
 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; }
 /**
 * 为 Node 重写 hashCode 方法，值为：key 的 hashCode 异或 value
的 hashCode
 * 运算作用就是将 2 个 hashCode 的二进制中，同一位置相同的值为 0，
不同的为 1。
 */
 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 重写 equals 方法
 */
 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;
 }
 }

1.png

问题

1、能说说 HashMap 常用操作的底层实现原理吗？如存储 put(K key, V value)，查找get(Object key)，删除 remove(Object key)，修改 replace(K key, V value)等操作。

答：调用 put(K key, V value)操作添加 key-value 键值对时，进行了如下操作：
判断哈希表 Node<K,V>[] table 是否为空或者 null，是则执行 resize()
方法进行扩容。根据插入的键值 key 的 hash 值，通过(n - 1) & hash 当前元素的 hash值 & hash 表长度 - 1（实际就是 hash 值 % hash 表长度） 计算出存储位置 table[i]。
如果存储位置没有元素存放，则将新增结点存储在此位置table[i]。
如果存储位置已经有键值对元素存在，则判断该位置元素的 hash 值和 key值是否和当前操作元素一致，一致则证明是修改 value 操作，覆盖 value即可。
当前存储位置即有元素，又不和当前操作元素一致，则证明此位置
table[i]已经发生了 hash 冲突，则通过判断头结点是否是 treeNode，如
果是 treeNode 则证明此位置的结构是红黑树，已红黑树的方式新增结点。
如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，
随后判断当前链表长度是否 大于等于 8，是则将当前存储位置的链表转
化为红黑树。遍历过程中如果发现 key 已经存在，则直接覆盖 value。
插入成功后，判断当前存储键值对的数量 大于 阈值 threshold 是则扩
容。

2.png

问 1：您上面说，存放一个元素时，先计算它的 hash 值确定它的存储位置，然后再把这个元素放到对应的位置上，那万一这个位置上面已经有元素存在呢，新增的这个元素怎么办？

问 2：hash 冲突（或者叫 hash 碰撞）是什么？为什么会出现这种现象，如何解决 hash 冲突？

答：hash 冲突： 当我们调用 put(K key, V value)操作添加 key-value 键值对，这个 key-value 键值对存放在的位置是通过扰动函数(key == null) ? 0: (h =key.hashCode()) ^ (h >>> 16)计算键 key 的 hash 值。随后将 这个 hash 值 % 模上 哈希表 Node<K,V>[] table 的长度 得到具体的存放位置。所以 put(K key, Vvalue)多个元素，是有可能计算出相同的存放位置。此现象就是 hash 冲突或者叫 hash 碰撞。

例子如下：
元素 A 的 hash 值 为 9，元素 B 的 hash 值 为 17。哈希表 Node<K,V>[]
table 的长度为 8。则元素 A 的存放位置为 9 % 8 = 1，元素 B 的存放
位置为 17 % 8 = 1。两个元素的存放位置均为 table[1]，发生了 hash 冲
突。

hash 冲突的避免：既然会发生 hash 冲突，我们就应该想办法避免此现象
的发生，解决这个问题最关键就是如果生成元素的hash值。Java是使用“扰
动函数”生成元素的 hash 值。
示例代码：

/**
 * JDK 7 的 hash 方法
 */
 final int hash(int h) {
 h ^= k.hashCode();
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }
 /**
 * JDK 8 的 hash 方法
 */
 static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

hash 冲突解决：解决 hash 冲突的方法有很多，常见的有：开发定址法，
再散列法，链地址法，公共溢出区法。HashMap 是使用链地址法解决 hash 冲突的，当有冲突元素放进来时，会将此元素插入至此位置链表的最后一位，形成单链表。但是由于是单链表的缘故，每当通过 hash % length 找到该位置的元素时，均需要从头遍历链表，通过逐一比较 hash 值，找到对应元素。如果此位置元素过多，造成链表过长，遍历时间会大大增加，最坏情况下的时间复杂度为 O(N)，造成查找效率过低。所以当存在位置的链表长度 大于等于 8 时，HashMap 会将链表 转变为 红黑树，红黑树最坏情况下的时间复杂度为 O(logn)。以此提高查找效率。

问：HashMap 的容量为什么一定要是 2 的 n 次方？

答：因为调用 put(K key, V value)操作添加 key-value 键值对时，具体确定此元素的位置是通过 hash 值 % 模上 哈希表 Node<K,V>[] table 的长度hash %length 计算的。但是"模"运算的消耗相对较大，通过位运算 h & (length-1)也可以得到取模后的存放位置，而位运算的运行效率高，但只有 length 的长度是2 的 n 次方时，h & (length-1) 才等价于 h % length。而且当数组长度为 2 的 n 次幂的时候，不同的 key 算出的 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

（5.）问：HashMap 的负载因子是什么，有什么作用？

负载因子表示哈希表空间的使用程度（或者说是哈希表空间的利用率）。
例子如下：
底层哈希表 Node<K,V>[] table 的容量大小 capacity 为 16，负载因子
load factor 为 0.75，则当存储的元素个数 size = capacity 16 * load
factor 0.75 等于 12 时，则会触发 HashMap 的扩容机制，调用 resize()
方法进行扩容。
当负载因子越大，则 HashMap 的装载程度就越高。也就是能容纳更多的元素，元素多了，发生 hash 碰撞的几率就会加大，从而链表就会拉长，此时的查询效率就会降低。当负载因子越小，则链表中的数据量就越稀疏，此时会对空间造成浪费，但是此时查询效率高。
我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；
如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；
如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。
通常情况下，默认负载因子 (0.75) 在时间和空间成本上寻求一种折衷，
程序员无需改变负载因子的值。
因此，如果我们在初始化 HashMap 时，就预估知道需要装载 key-value 键
值对的容量 size，我们可以通过 size / load factor 计算出我们需要初
始化的容量大小 initialCapacity，这样就可以避免 HashMap 因为存放的
元素达到阈值 threshold 而频繁调用 resize()方法进行扩容。从而保证
了较好的性能。

（6.）问：您能说说 HashMap 和 HashTable 的区别吗？

答：HashMap 和 HashTable 有如下区别：
1）容器整体结构：
HashMap的key和value都允许为null，HashMap遇到key为null的时候，
调用 putForNullKey 方法进行处理，而对 value 没有处理。
Hashtable 的 key 和 value 都不允许为 null。Hashtable 遇到 null，直接
返回 NullPointerException。
2） 容量设定与扩容机制：
HashMap 默认初始化容量为 16，并且容器容量一定是 2 的 n 次方，扩容
时，是以原容量 2 倍 的方式 进行扩容。
Hashtable 默认初始化容量为 11，扩容时，是以原容量 2 倍 再加 1 的
方式进行扩容。即 int newCapacity = (oldCapacity << 1) + 1;。
3） 散列分布方式（计算存储位置）：
HashMap 是先将 key 键的 hashCode 经过扰动函数扰动后得到 hash 值，然后再利用 hash & (length - 1)的方式代替取模，得到元素的存储位置。
Hashtable 则是除留余数法进行计算存储位置的（因为其默认容量也不是
2 的 n 次方。所以也无法用位运算替代模运算），int index = (hash &
0x7FFFFFFF) % tab.length;。
由于 HashMap 的容器容量一定是 2 的 n 次方，所以能使用 hash & (length- 1)的方式代替取模的方式计算元素的位置提高运算效率，但 Hashtable的容器容量不一定是 2 的 n 次方，所以不能使用此运算方式代替。
4）线程安全（最重要）：
HashMap 不是线程安全，如果想线程安全，可以通过调用
synchronizedMap(Map<K,V> m)使其线程安全。但是使用时的运行效率会下降，所以建议使用 ConcurrentHashMap 容器以此达到线程安全。
Hashtable 则是线程安全的，每个操作方法前都有 synchronized 修饰使
其同步，但运行效率也不高，所以还是建议使用 ConcurrentHashMap 容器以此达到线程安全。
因此，Hashtable 是一个遗留容器，如果我们不需要线程同步，则建议使用HashMap，如果需要线程同步，则建议使用 ConcurrentHashMap。
此处不再对 Hashtable 的源码进行逐一分析了，如果想深入了解的同学，可以参考此文章
Hashtable 源码剖析https://blog.csdn.net/chdjj/article/details/38581035

（7.）问：您说 HashMap 不是线程安全的，那如果多线程下，它是如何处理的？并且什么情况下会发生线程不安全的情况？

答：HashMap 不是线程安全的，如果多个线程同时对同一个 HashMap 更改数据的话，会导致数据不一致或者数据污染。如果出现线程不安全的操作时，HashMap会尽可能的抛出 ConcurrentModificationException 防止数据异常，当我们在对一个 HashMap 进行遍历时，在遍历期间，我们是不能对 HashMap 进行添加，删除等更改数据的操作的，否则也会抛出 ConcurrentModificationException 异常，此为 fail-fast（快速失败）机制。从源码上分析，我们在 put,remove 等更改 HashMap数据时，都会导致 modCount 的改变，当 expectedModCount != modCount 时，则抛出 ConcurrentModificationException。如果想要线程安全，可以考虑使用
ConcurrentHashMap。（而且，在多线程下操作 HashMap，由于存在扩容机制，当 HashMap 调用resize()进行自动扩容时，可能会导致死循环的发生。）

（8.）问：我们在使用 HashMap 时，选取什么对象作为 key 键比较好，为什么？

答：不可变对象。
可变对象：指创建后自身状态能改变的对象。换句话说，可变对象是该对象在创建后它的哈希值可能被改变。
我们在使用 HashMap 时，最好选择不可变对象作为 key。例如 String，
Integer 等不可变类型作为 key 是非常明智的。
如果 key 对象是可变的，那么 key 的哈希值就可能改变。在 HashMap 中可变对象作为 Key 会造成数据丢失。因为我们再进行 hash & (length - 1)
取模运算计算位置查找对应元素时，位置可能已经发生改变，导致数据丢
失。

总结

HashMap 是基于 Map 接口实现的一种键-值对<key,value>的存储结构，允许 null 值，同时非有序，非同步(即线程不安全)。HashMap 的底层实现是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）。
HashMap 定位元素位置是通过键 key 经过扰动函数扰动后得到 hash 值，然后再通过 hash & (length - 1)代替取模的方式进行元素定位的。
HashMap 是使用链地址法解决 hash 冲突的，当有冲突元素放进来时，会
将此元素插入至此位置链表的最后一位，形成单链表。当存在位置的链表
长度 大于等于 8 时，HashMap 会将链表 转变为 红黑树，以此提高查找
效率。
HashMap 的容量是 2 的 n 次方，有利于提高计算元素存放位置时的效率，也降低了 hash 冲突的几率。因此，我们使用 HashMap 存储大量数据的时
候，最好先预先指定容器的大小为 2 的 n 次方，即使我们不指定为 2 的 n
次方，HashMap 也会把容器的大小设置成最接近设置数的 2 的 n 次方，如，设置 HashMap 的大小为 7 ，则 HashMap 会将容器大小设置成最接近 7 的一个 2 的 n 次方数，此值为 8 。
HashMap 的负载因子表示哈希表空间的使用程度（或者说是哈希表空间的利用率）。当负载因子越大，则 HashMap 的装载程度就越高。也就是能容纳更多的元素，元素多了，发生 hash 碰撞的几率就会加大，从而链表就会拉长，此时的查询效率就会降低。当负载因子越小，则链表中的数据量就越稀疏，此时会对空间造成浪费，但是此时查询效率高。
HashMap 不是线程安全的，Hashtable 则是线程安全的。但 Hashtable 是一个遗留容器，如果我们不需要线程同步，则建议使用 HashMap，如果需要线程同步，则建议使用 ConcurrentHashMap。
在多线程下操作 HashMap，由于存在扩容机制，当 HashMap 调用 resize()进行自动扩容时，可能会导致死循环的发生。
我们在使用 HashMap 时，最好选择不可变对象作为 key。例如 String，
Integer 等不可变类型作为 key 是非常明智的。

Hashset

HashSet 是 Set 的一种实现方式，底层主要使用 HashMap 来确保元素不重复。

Hashset 源码分析

属性

 // 内部使用 HashMap
 private transient HashMap<E,Object> map;
 // 虚拟对象，用来作为 value 放到 map 中
 private static final Object PRESENT = new Object();

构造方法（构造方法都是调用 HashMap 对应的构造方法。最后一个是给 LinkedHashSet 专属的方法）

public HashSet() {
 map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
 map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
 addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
 map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
 map = new HashMap<>(initialCapacity);
}
// 非 public，主要是给 LinkedHashSet 使用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
 map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

添加元素
直接调用 HashMap 的 put()方法，把元素本身作为 key，把 PRESENT 作为 value，也就是这个 map 中所有的 value 都是一样的。

public boolean add(E e) {
 return map.put(e, PRESENT)==null;
}

删除元素
直接调用 HashMap 的 remove()方法，注意 map 的 remove 返回是删除元素的value，而 Set 的 remov 返回的是 boolean 类型。
这里要检查一下，如果是 null 的话说明没有该元素，如果不是 null 肯定等于PRESENT。

public boolean remove(Object o) {
 return map.remove(o)==PRESENT;
}

查询元素
Set 没有 get()方法哦，因为 get 似乎没有意义，不像 List 那样可以按 index 获取元素。
这里只要一个检查元素是否存在的方法 contains()，直接调用 map 的 containsKey()方法。

public boolean contains(Object o) {
 return map.containsKey(o);
}

遍历元素

public Iterator<E> iterator() {
 return map.keySet().iterator();
}

总结

（1）HashSet 内部使用 HashMap 的 key 存储元素，以此来保证元素不重复；
（2）HashSet 是无序的，因为 HashMap 的 key 是无序的；
（3）HashSet 中允许有一个 null 元素，因为 HashMap 允许 key 为 null；
（4）HashSet 是非线程安全的；
（5）HashSet 是没有 get()方法的；

由上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

HashSet的绝大部分方法都是通过调用HashMap 的方法来实现的，因此HashSet 和HashMap 两个集合在实现本质上是相同的。