简介
1、集合类存放于java.util包中。
2、集合类型主要有3种：set(集）、list(列表）和map(映射)。
3、集合存放的都是对象的引用，而非对象本身。所以我们称集合中的对象就是集合中对象的引用。
简单来讲：集合就是一个放数据的容器，准确的说是放数据对象引用的容器。
一、集合框架图
集合与数组的区别
| 区别 | 集合 | 数组 |
|---|---|---|
| 长度区别: | 集合是可以动态扩展容量，可以根据需要动态改变大小 | 数组是静态的，数组实例具有固定的大小，一旦创建就无法改变容量 |
| 存储数据类型 | 可以不是一种(不加泛型时添加的类型是Object) | 只能是同一种（基本类型/引用类型） |
| 声明数据类型 | 引用类型 | 基本类型/引用类型 |
常用的集合
Collection
├——-List ：有序集合，元素按进入先后有序保存，可重复
│—————-├ LinkedList 基于链表， 遍历效率低，插入删除效率高， 非同步， 线程不安全
│—————-├ ArrayList ， 基于数组， 实现了动态大小的数组，遍历效率高， 非同步， 线程不安全
│—————-└ Vector ： 基于数组， 同步， 线程安全，效率低
│ ———————-└ Stack 是Vector类的实现类
└——-Set 接口： 无序集合，不允许相同元素，最多有一个null元素
├—————-└HashSet 使用hash表（数组）存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树，元素排好序
Map 接口 键值对的集合 （双列集合）
├———Hashtable 接口实现类， 同步， 线程安全
├———HashMap 接口实现类 ，没有同步， 线程不安全-
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└———IdentifyHashMap
三、List集合
List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。List允许有相同的元素。
3.1、ArrayList
3.1.1、ArrayList扩容机制：
1、我们对ArrayList的源码进行解读，发现如下几个重要属性：
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 默认共享的空对象数组：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList 实际数据存储的一个数组：
transient Object[] elementData; // non-private to simplify nested class access
// elementData 的大小：
private int size;
2、新增数据的add 方法
/**
* 将指定元素追加到列表的末尾。
*/
public boolean add(E e) {
// 确保容量够用
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果新增数据已没有位置存放，则进行扩容。
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
2、具体扩容方法：
private void grow(int minCapacity) {
// 原来的容量
int oldCapacity = elementData.length;
// 新的容量是原来的1.5倍，准确的说是新容量=原容量+原容量右移1位
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 最终利用Arrays.coppy 进行扩容，生成一个1.5倍元素的数组。
elementData = Arrays.copyOf(elementData, newCapacity);
}
总结：ArrayList 的内部实现，其实是用一个对象数组进行存放具体的值，然后用一种扩容的机制，进行数组的动态增长。
其扩容机制可以理解为，当元素的个数大于其容量时，则把其容量扩展为原来容量的1.5倍，准确的说是【新容量=原容量+原容量右移1位】。
3.1.2、remove方法源码解读：
public E remove(int index) {
// 检查索引是否在范围内
rangeCheck(index);
modCount++;
// 返回删除元素
E oldValue = elementData(index);
// 需要移动的数组长度
int numMoved = size - index - 1;
if (numMoved > 0)
/**
*Object src : 原数组
*int srcPos : 从元数据的起始位置开始
* Object dest : 目标数组
* int destPos : 目标数组的开始起始位置
* int length : 要copy的数组的长度
**/
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 设置最后一位为null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
3.2、LinkedList
1、LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当做堆栈、队列或双端队列进行使用。
2、LinkedList实现List接口，能让它进行队列操作。
3、LinkedList实现Deque接口，即能将LinkedList当做双端队列使用。
4、LinkedList实现Cloneable，即覆盖了函数clone()，能被克隆。
5、LinkedList实现了java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
6、LinkedList中的操作不是线程安全的。
源码解读：
3.2.1、几个重要属性
//链表节点的个数
transient int size = 0;
//链表首节点
transient Node<E> first;
//链表尾节点
transient Node<E> last;
3.2.2、Node结构
数据存储与Node中，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;
}
}
3.2.3、添加元素
public boolean add(E e) {
// 在链表尾部添加元素
linkLast(e);
// 因为是无界的，所以添加元素总是会成功
return true;
}
// 在链表尾部添加元素
void linkLast(E e) {
//将内部保存的尾节点赋值给l
final Node<E> l = last;
//创建新节点，新节点的prev节点是当前的尾节点
final Node<E> newNode = new Node<>(l, e, null);
//把新节点作为新的尾节点
last = newNode;
//判断是否是第一个添加的元素
if (l == null)
//如果是将新节点赋值给first
first = newNode;
else
//如果不是把原首节点的next设置为新节点
l.next = newNode;
//更新链表节点个数
size++;
//将集合修改次数加1
modCount++;
}
/**
* 在链表首部添加元素原理相同，不做解读
*/
3.2.4、获取元素
使用二分法查找元素，提供搜索效率。
Node<E> node(int index) {
//如果index小于size的一半，就从首节点开始遍历，一直获取x的下一个节点
//如果index大于或等于size的一半，就从尾节点开始遍历，一直获取x的上一个节点
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
3.2.5、删除元素
public boolean remove(Object o) {
//因为LinkedList允许存在null，所以需要进行null判断
if (o == null) {
//从首节点开始遍历
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//调用unlink方法删除指定节点，指定节点是null
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
//调用unlink方法删除指定节点，指定节点不是null
unlink(x);
return true;
}
}
}
return false;
}
//删除指定节点
E unlink(Node<E> x) {
//获取x节点的元素，以及它上一个节点，和下一个节点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果x的上一个节点为null，说明是首节点，将x的下一个节点设置为新的首节点
//否则将x的上一节点设置为next，将x的上一节点设为null
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//如果x的下一节点为null，说明是尾节点，将x的上一节点设置新的尾节点
//否则将x的上一节点设置x的上一节点，将x的下一节点设为null
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//将x节点的元素值设为null，等待垃圾收集器收集
x.item = null;
//链表节点个数减1
size--;
//将集合修改次数加1
modCount++;
//返回删除节点的元素值
return element;
}
3.3、Vector
3.3.1 Vector的优缺点
优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高其时间复杂度O(1)。
缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O（n），另外当空间不足时还需要进行扩容。
3.3.2 Vector与ArrayList的区别
阅读Vector源码分容易发现，Vector的方法都是同步的，这是Vector与ArrayList最大的不同。ArrayList是线程非安全的，在并发下一定会出现线程安全问题。另一个方法就是Vector，它是ArrayList的线程安全版本，其实现90%和ArrayList都完全一样，区别在于：
1、Vector是线程安全的，ArrayList是线程非安全的
2、在默认情况下，当用来存放元素的数组超过了内部分配的长度的时候。ArrayList会按照原长度的50%来续加长度。
Vector会按照原长度的一倍来增加长度。（Vector也可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小*2。）
3.4、Stack
栈是Vector的一个子类，它实现了一个标准的后进先出的栈。
堆栈只定义了默认构造函数，用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。
4、Set集合
Set是一种无序的并且不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
4.1、HashSet
HashSet是基于HashMap实现的，底层采用HashMap来保存元素，在准确的说使用HashMap的key来保存元素，value中统一存放private static final Object PRESENT = new Object();
HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能。
HashSet 的方法都是非同步的，不是线程非安全的。
源码解读
// 底层是由HashMap实现的
private transient HashMap<E,Object> map;
// value中统一存放PRESENT
private static final Object PRESENT = new Object();
/**
* 默认初始容量（16）和负载系数（0.75）
*/
public HashSet() {
// 底层是由HashMap实现的
map = new HashMap<>();
}
4.2、LinkedHashSet
LinkedHashSet继承自HashSet，但是LinkedHashSet内部使用的是LinkHashMap来存储数据。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。
// 继承HashSet
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2851667679971038690L;
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
// 调用HashSet中的方法创建对象
public LinkedHashSet() {
super(16, .75f, true);
}
// HashSet类
// 底层由LinkedHashMap存储
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
总结：
LinkedHashSet 是 Set 的一个具体实现，其维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。
如果需要迭代的顺序为插入顺序或者访问顺序，那么 LinkedHashSet 是需要你首先考虑的。
4.3、TreeSet
TreeSet是一个有序的集合，它的作用是提供有序的Set集合。TreeSet是基于TreeMap实现的，TreeSet的元素支持2种排序方式：自然排序或者根据提供的Comparator进行排序。
总结：
1、不能有重复的元素；
2、具有排序功能；
3、TreeSet中的元素必须实现Comparable接口并重写compareTo()方法，TreeSet判断元素是否重复 、以及确定元素的顺序 靠的都是这个方法；
①对于Java类库中定义的类，TreeSet可以直接对其进行存储，如String，Integer等,因为这些类已经实现了Comparable接口);
②对于自定义类，如果不做适当的处理，TreeSet中只能存储一个该类型的对象实例，否则无法判断是否重复。
4、依赖TreeMap。
5、相对HashSet,TreeSet的优势是有序，劣势是相对读取慢。根据不同的场景选择不同的集合。
5、Map集合
Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。
5.1、HashMap
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
HashMap存储结构图
源码解读-属性
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 填充因子，默认值是0.75f
final float loadFactor;
put新增数据
//根据key值计算出hashcode，
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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数组未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// hash值不相等，即key不相等；为红黑树结点
else if (p instanceof TreeNode)
// 放入树中
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;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示找到key值、hash值与插入元素相等的结点
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
加入过程用脑图进行表示：
小疑问：为什么使用 (n - 1) & hash 确定元素存放在哪个桶中?
其中就利用了按位与操作的一个特点,必须两个位都为1,才是1,那么也就是说,如果数组最大下标为15,那么不管Hash(key)是多少都不会大于15，也就不会数组越界的问题。
resize扩容
什么时候扩容：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈---即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。
扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
/**
* 初始化或者翻倍表大小。
* 如果表为null，则根据存放在threshold变量中的初始化capacity的值来分配table内存
* （这个注释说的很清楚，在实例化HashMap时，capacity其实是存放在了成员变量threshold中，
* 注意，HashMap中没有capacity这个成员变量）
* 。如果表不为null，由于我们使用2的幂来扩容(指长度扩为原来2倍)，所以，经过rehash之后
* 则每个bin元素要么还是在原来的bucket(桶)中，，要么是在原位置再移动2次幂的位置
* 此方法功能：初始化或扩容
*/
final HashMap.Node<K,V>[] resize() {
// 把扩容前的table数组 赋值给 oldTab
HashMap.Node<K,V>[] oldTab = table;
// oldCap： 原容量值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr：原扩容阀界值
int oldThr = threshold;
//新的容量值，新的扩容阀界值
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值设置为整数的最大值 Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return oldTab;
}
// newCap： 新长度设置为原长度的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果能进来证明此map是扩容而不是初始化
//操作：将原扩容阀界值<<1(相当于*2)赋值给 newThr
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
/**
* 进入此if证明创建map时用的带参构造：public HashMap(int initialCapacity)
* 或 public HashMap(int initialCapacity, float loadFactor)
* 注：带参的构造中initialCapacity（初始容量值）不管是输入几都会通过
* “this.threshold = tableSizeFor(initialCapacity);”来作为初始化容量（初始化容量==oldThr）
* tableSizeFor方法:返回一个比给定值大的最小的2的次幂（大于initialCapacity参数的最小的2^n的数值）
* tableSizeFor(initialCapacity)方法说明：例如输入100会返回128
*/
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//进入此if证明创建map时用的无参构造：
// 新长度设置为默认容量：16
newCap = DEFAULT_INITIAL_CAPACITY;
// 新阈值设置为 默认加载因子（0.75f）*16 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//进入此if有两种可能
// 第一种：进入此“if (oldCap > 0)”中且不满足该if中的两个if
// 第二种：进入这个“else if (oldThr > 0)”
//分析：进入此if证明该map在创建时用的带参构造，如果是第一种情况就说明是进行扩容且oldCap（旧容量）小于16，
// 如果是第二种说明是第一次put
float ft = (float)newCap * loadFactor;
//计算扩容阀界值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
//如果“oldTab != null”说明是扩容，否则直接返回newTab
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.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 HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//此对象接收会放在原来位置
HashMap.Node<K,V> loHead = null, loTail = null;
//此对象接收会放在“j + oldCap”（当前位置索引+原容量的值）
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
do {
next = e.next;
// e.hash & oldCap判断是否需要移位
if ((e.hash & oldCap) == 0) {
// 不需要移位
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 需要移位
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;
// 移动到当前hash槽位 + oldCap的位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
1、 如果table == null, 则为HashMap的初始化, 生成空table返回即可;
2、 如果table不为空, 需要重新计算table的长度, newLength = oldLength << 1(注, 如果原oldLength已经到了上限, 则newLength = oldLength);
3、 遍历oldTable:
4、 首节点为空, 本次循环结束;
5、 无后续节点, 重新计算hash位, 本次循环结束;
6、 当前是红黑树, 走红黑树的重定位;
7、 当前是链表, JAVA7时还需要重新计算hash位, 但是JAVA8做了优化, 通过(e.hash & oldCap) == 0来判断是否需要移位; 如果为真则在原位不动, 否则则需要移动到当前hash槽位 + oldCap的位置;
HashMap::resize的核心就是上图, 链表与红黑树的resize过程大同小异: 红黑树是把构建新链表的过程变为构建两颗新的红黑树, 定位table中的index都是用的 e.hash & oldCap == 0 来判断;
再来看下 e.hash & oldCap == 0为什么可以判断当前节点是否需要移位, 而不是再次计算hash;
只需要看看原来的hash值新增的那个bit是1还是0就好了（红线标注），是0的话索引没变，是1的话索引变成“原索引+oldCap”。
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
5.2、HashTable
Hashtable与HashMap的区别
1、HashMap是非同步的，没有对读写等操作进行锁保护，所以是线程不安全的，在多线程场景下会出现数据不一致的问题。而HashTable是同步的，所有的读写等操作都进行了锁（synchronized）保护，在多线程环境下没有安全问题。但是锁保护也是有代价的，会对读写的效率产生较大影响。
2、HashMap结构中，是允许保存null的，Entry.key和Entry.value均可以为null。但是HashTable中是不允许保存null的。
3、两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
4、哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。代码是这样的：
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新计算hash值，而且用与代替求模：
int hash = hash(k);
int i = indexFor(hash, table.length);
5、Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
5.3、TreeMap
TreeMap使用的存储结构是平衡二叉树，也称为红黑树。它首先是一棵二叉树，具有二叉树所有的特性，即树中的任何节点的值大于它的左子节点，且小于它的右子节点，如果是一棵左右完全均衡的二叉树，元素的查找效率将获得极大提高。最坏的情况就是一边倒，只有左子树或只有右子树，这样势必会导致二叉树的检索效率大大降低。为了维持二叉树的平衡，程序员们提出了各种实现的算法，其中平衡二叉树就是其中的一种算法。平衡二叉树的数据结构如下图所示：
TreeMap存储结构
5.4、LinkHashMap
LinkHashMap存储结构
应用场景
HashMap是无序的，当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了。
Map<String, String> hashMap = new HashMap<String, String>();
hashMap.put("name1", "josan1");
hashMap.put("name2", "josan2");
hashMap.put("name3", "josan3");
Set<Entry<String, String>> set = hashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
image
我们是按照xxx1、xxx2、xxx3的顺序插入的，但是输出结果并不是按照顺序的。
同样的数据，我们再试试LinkedHashMap
Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("name1", "josan1");
linkedHashMap.put("name2", "josan2");
linkedHashMap.put("name3", "josan3");
Set<Entry<String, String>> set = linkedHashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
image
结果可知，LinkedHashMap是有序的，且默认为插入顺序
网友评论