JDK7中，HashMap使用数组+链表的结构，JDK8中，HashMap使用数组+链表+红黑树的结构。
HashMap添加数据的过程梳理，从JDK7为例梳理过程，并分析JDK8与JDK7之间的区别:
JDK7为例，HashMap首先初始化，HashMap map = new HashMap();创建了一个长度为16的一维数组Entry[] table，之后使用map.put(key, value)不断向其添加数据
以某次执行map.put(key1, value1)为例：
//计算key1的hash值，得到在数组的存放位置，若该位置为空，添加成功。
int hash = hash(key1);
若该位置上有值，以链表形式存在，将hash(key1)循环与该位置存在的hash比较，
//循环比较hash值，若有相同的，继续比较equals方法，若完全相同，则替换。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
若循环比较时，与该链表中存在的所有数据的hash值均不相同，或者hash值相同但equals()方法不同，添加成功
//添加成功
addEntry(hash, key, value, i);
扩容问题，当超出临界值(且要存放的位置非空)时，扩容为原来容量的2倍，并将原有的数据复制过来。
JDK8与JDK7区别：
HashMap map = new HashMap();底层创建的数组为Node[],而非Entry[]，默认为{}。在首次调用map.put(key1, value1)时，创建长度为16的数组。JDK7底层结构：数组+链表，JDK8中底层结构：数组+链表+红黑树。JDK8中的HashMap源码分析：//默认的装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//底层数组
transient Node<K,V>[] table;
//默认构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75f
}
//调用put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//传入key算出hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//JDK8底层的数组为：Node<K,V>[] tab, JDK7底层的数字为Entry[] table
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)
//使用putTreeVal()
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//循环遍历看是否相等 binCount 是链表中元素个数
for (int binCount = 0; ; ++binCount) {
//比较到最后发现没有相同的，直接在链表结尾添加进去元素
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//新插入节点后链表长度大于等于8，判断需要使用红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//数组长度<64时，直接扩容，>=64时,使用红黑树
treeifyBin(tab, hash);
break;
}
//如果存在相等的元素 跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果有对应key的元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//替换旧值为传入的新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//没有找到元素 修改次数+1
++modCount;
//元素数量加1，判断是否需要扩容
if (++size > threshold)
// 扩容
resize();
afterNodeInsertion(evict);
return null;
}
// HashMap的默认容量，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap的默认加载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//扩容的临界值，=容量*装载因子：16 * 0.75 => 12
int threshold;
//Bucket中链表长度大于等于该默认值，转化为红黑树:8
static final int TREEIFY_THRESHOLD = 8;
//桶中的Node被树化时最小的hash表容量:64
static final int MIN_TREEIFY_CAPACITY = 64;
LinkedHashMap比HashMap多一个双向链表，可保证元素按插入的顺序访问。简单理解为LinkedHashMap=LinkedList + HashMap 。//多了before, after用来记录顺序
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
JDK7中HashMap扩容时，多线程情况下复制数据时会出现环形链表的情况
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//循环数组的每一个索引的数据
for (Entry<K,V> e : table) {
//循环单个索引下的链表中的数据
while(null != e) {
//next是一个局部变量
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//头插法
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
两个重要的属性：
//底层是hashMap
private transient HashMap<E,Object> map;
//所有的key指向的value 放到map中
private static final Object PRESENT = new Object();
HashSet内部使用的是HashMap，存储的key无序不可重复。
public HashSet() {
map = new HashMap<>();
}
当向HashSet中添加数据时，调用的是map.put()方法，
//添加key调用的是map的put方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashSet的初始容量，初始化时指定容量是为了减少扩容的次数，提高效率。初始容量应设置为(int) (c.size()/.75f) + 1。
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
LinkedHashSet底层实现LinkedHashSet是HashSet的子类，底层使用的是LinkedHashMap，所以它可以按照插入的顺序进行排序。
//构造函数使用父类构造函数
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
ArrayList的构造方法，底层Object[] elementData初始化为{}。
//实例化后未添加元素时，空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//底层数组
transient Object[] elementData
//构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
使用add()方法添加数据，如果是空数组，初始化为10，每次扩容为原来的1.5倍，并复制元素到扩容后的数组上。
public boolean add(E e) {
//添加数据前检查是否需要扩容 空数组默认初始化为10
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加数据到最后
elementData[size++] = e;
return true;
}
定义双链表结构
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;
}
}
原创不易，欢迎转载，转载时请注明出处，谢谢！
作者：潇～萧下
原文链接：https://www.cnblogs.com/manongxiao/p/13697961.html
原文：https://www.cnblogs.com/manongxiao/p/13697961.html