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