List
ArrayList
ArrayList 是 List 接口的典型实现类、主要实现类；本质上， ArrayList是对象引用的一个”变长”数组。它的底层就是维护了一个Object类型的数组elementData，当需要存储的数据量可能要大于数组的长度的时候，使用一定的策略创建容量更大的新的数组，再将旧的数组复制到新的数组中去，并替换原来容量小的数组。jdk1.7和jdk1.8中对ArrayList的实现方式不太一样。
JDK 1.7
创建
ArrayList list = new ArrayList();
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}
创建ArrayList
我们平时使用的默认构造方法，ArrayList的在初始化的时候创建了一个长度为10的Object类型数组elementData ，建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)
添加
// 添加元素
public boolean add(E e) {
// 先去确定下容器是否可存储下
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
// 容量Capacity确定方法
private void ensureCapacityInternal(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
// 如果容量不够，则需要扩容
grow(minCapacity);
}
// 容器扩容方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// oldCapacity >> 1 相当于 oldCapacity/2 扩容目标为原先的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
// 如果扩容1.5倍小于给定的容量，则直接扩容至给定的容量大小
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果扩容目标大于最大的数组大小，则将目标数组大小设置成最大
newCapacity = hugeCapacity(minCapacity);
// 将创建目标大小的新数组，并将旧数组复制到新数组中去，最后将 elementData 替换为新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 返回最大的容量大小
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
添加元素
扩容
查找
public int indexOf(Object o) {
if (o == null) {
// 查找元素为null的位置
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 底层调用的是所给对象的equals()方法进行比较的
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
删除
public boolean remove(Object o) {
// 使用元素的equals()方法查找元素所在容器中的索引，然后再进行删除。
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 删除的实际操作
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
// 如果不是最后一个元素，则把目标位置后面的元素 从目标位置开始复制(可理解往前移动一位)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 最后将数组最后置空
elementData[--size] = null; // Let gc do its work
}
JDK 1.8
创建
ArrayList list = new ArrayList();
// 默认的静态空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认无参的构造方法会容器是默认的静态空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 含参构造方法
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);
}
}
JDK 1.8 中ArrayList在初始化时如果不设置默认容量的话，不会创建默认长度的数组，只有一个静态的空数组。
添加
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
// 添加前先检查容量
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 计算目标容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 如果容器是空数组(或者说首次添加),在默认容量和给定大小中取最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 确保内部容量
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 确保许可容量
private void ensureExplicitCapacity(int minCapacity) {
// 记录数量
modCount++;
if (minCapacity - elementData.length > 0)
// 如果容量不够，则需要扩容
grow(minCapacity);
}
// 扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// oldCapacity >> 1 相当于 oldCapacity/2 扩容目标为原先的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
// 如果扩容1.5倍小于给定的容量，则直接扩容至给定的容量大小
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果扩容目标大于最大的数组大小，则将目标数组大小设置成最大
newCapacity = hugeCapacity(minCapacity);
// 将创建目标大小的新数组，并将旧数组复制到新数组中去，最后将 elementData 替换为新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 返回最大的容量大小
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
LinkedList
双向链表， 内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。 Node除了保存数据，还定义了两个变量：
prev变量记录前一个元素的位置next变量记录下一个元素的位置
LinkedList数据结构
Node
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;
}
}
创建
LinkedList linkedList = new LinkedList();
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
添加
public boolean add(E e) {
linkLast(e);
return true;
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
查找
// 获取给定元素的位置
public int indexOf(Object o) {
int index = 0;
if (o == null) {
// 从表头开始 顺序查找
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
// 从表头开始 顺序查找
for (Node<E> x = first; x != null; x = x.next) {
// 使用元素的equals()方法去对比
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
删除
// 移除某个元素并返回该元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 顺序查找 该元素
for (Node<E> x = first; x != null; x = x.next) {
// 使用equals()方法做判断
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
// 解除node的链接关系
E unlink(Node<E> x) {
// assert x != null;
// 先记录下给定元素 和它的前缀、后缀
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 判断是否是头结点
if (prev == null) {
// 如果前缀为空，即说明是头结点，则把要删除的元素后缀指定为头结点
first = next;
} else {
// 如果不是头结点，则让前缀的后缀指向要删元素的后缀，并让要删元素的前缀置空
prev.next = next;
x.prev = null;
}
// 判断是否是尾结点
if (next == null) {
// 如果是尾结点，就让尾指针指向元素的前缀
last = prev;
} else {
// 如果不是尾结点，就让后缀的前缀指向要删元素的前缀，并让要删元素的前缀置空
next.prev = prev;
x.next = null;
}
// 内容置空
x.item = null;
size--;
modCount++;
// 返回要删元素的副本
return element;
}
Vector
Vector是比较古老的一个类，它利用
synchronized关键字实现了线程安全，所以查看源码我们可以看到vector的一些方法都添加了synchronized关键字来修饰。
创建
jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍。
Vector vector = new Vector();
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
添加
// 添加元素
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
// 确定容量
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 如果需要的容量大于目前容器的容量，则需要扩容
grow(minCapacity);
}
// 扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 如果设定了扩容步长的话，就容器添加扩容步长的长度，如果没有的话，就扩大原容量的两倍。
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement:oldCapacity);
if (newCapacity - minCapacity < 0)
// 如果目标扩容的大小还不够，则将目标扩容的大小设置为需要的大小
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果目标扩容的大小已经超过最大的大小了，则直接将目标扩容大小设置成最大的大小
newCapacity = hugeCapacity(minCapacity);
// 将原有的数组拷贝到新数组并进行替换
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 获取最大的数组
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
问题
请问ArrayList/LinkedList/Vector的异同？ 谈谈你的理解？ ArrayList底层是什么？扩容机制？ Vector和ArrayList的最大区别?
- ArrayList和LinkedList的异同
二者都线程不安全，相对线程安全的Vector，执行效率高。
此外， ArrayList是实现了基于动态数组的数据结构， LinkedList基于链表的数据结构。对于
随机访问get和set， ArrayList觉得优于LinkedList，因为LinkedList要移动指针。对于新增
和删除操作add(特指插入)和remove， LinkedList比较占优势，因为ArrayList要移动数据。
- ArrayList和Vector的区别
Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于
强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用
ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。 Vector每次扩容请求其大
小的2倍空间，而ArrayList是1.5倍。 Vector还有一个子类Stack。
Map
Map双列数据，存储key-value对的数据,其中，Map的数据结构有如下特点：
- Map中的key:无序的、不可重复的，使用Set存储所有的key;
- Map中的value:无序的、可重复的，使用Collection存储所有的value；
- 一个键值对：key-value构成了一个Entry对象；
- Map中的entry:无序的、不可重复的，使用Set存储所有的entry。
Map 双列数据结构
HashMap
HashMap作为Map的主要实现类,它是线程不安全的，但是他的效率高，可以存储null的key和value。JDK 1.7 和 JDK 1.8中的实现方式有些不同，JDK 1.7 中底层使用的是
数组+链表的方式，而JDK 1.8中底层使用的是数组+链表+红黑树的方式。
JDK 1.7
HashMap 1.7的数据结构
Entry
// HashMap 中存储数据信息的类
static class Entry<K,V> implements Map.Entry<K,V> {
// finnal 修饰的key，不允许修改
final K key;
V value;
Entry<K,V> next;
int hash;
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;
}
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;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap<K,V> m) {
}
void recordRemoval(HashMap<K,V> m) {
}
}
创建
HashMap map = new HashMap();
// 默认的初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 实际存放的容器 Entry[]
transient Entry<K,V>[] table;
// 如果为true，则执行字符串键的替代哈希以减少由于弱哈希代码计算而导致的冲突发生率。
transient boolean useAltHashing;
// 默认无参构造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 含设置容量的构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 含容量以及加载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {
// 校验容量是否合法
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
// 如果超过最大容量了，就讲目标设定容量设置成最大容量。
initialCapacity = MAXIMUM_CAPACITY;
// 校验加载因子是否合法
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 较正容量为2的n次方的大小
int capacity = 1;
while (capacity < initialCapacity)
// capacity <<= 1 等同于 capacity = capacity * 2
capacity <<= 1;
this.loadFactor = loadFactor;
// 扩容的临界值
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 创建Entry[]数组
table = new Entry[capacity];
// 如果为true，则执行字符串键的替代哈希以减少由于弱哈希代码计算而导致的冲突发生率。
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// init()是个空方法
init();
}
添加
// 添加元素
public V put(K key, V value) {
if (key == null)
// 单独处理添加key为null的元素
return putForNullKey(value);
// 计算hash值
int hash = hash(key);
// 获取存储位置
int i = indexFor(hash, table.length);
// 在该位置查找是否也有数据
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))) {
// 如果hash系统 而且key相同，则替换value，并将旧值返回
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果没有hash冲突，直接插入，并返回null
modCount++;
addEntry(hash, key, value, i);
return null;
}
// 添加null值键值对
private V putForNullKey(V value) {
// 如果能找到就替换，不能找到就插入
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
// 根据hash值和容器大小计算位置
static int indexFor(int h, int length) {
// 使用 按位与 操作进行快速取模
return h & (length-1);
}
// 插入Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
// 如果容器大小大于等于临界值而且目标插入位置存在数据了，则扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 添加entry
createEntry(hash, key, value, bucketIndex);
}
// 扩容
void resize(int newCapacity) {
// 保存旧的容器
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
// 如果已经是最大的容量了,就不需要再扩了
threshold = Integer.MAX_VALUE;
return;
}
// 创建新的Entry[]
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// 判断是否需要重新hash key
boolean rehash = oldAltHashing ^ useAltHashing;
// 转移容器到新的容器中
transfer(newTable, rehash);
// 覆盖掉原来的table
table = newTable;
// 重新计算临界值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 转移数据 到新的容器中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
// 如果需要重新hash key
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新计算位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
// 添加新的entry
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
查找
// 根据key查询Entry
public V get(Object key) {
if (key == null)
// 查询key为null的Entry
return getForNullKey();
// 直接查询
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
// 查询key为null的Entry
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
// 查询
final Entry<K,V> getEntry(Object key) {
// 先计算key的hash
int hash = (key == null) ? 0 : hash(key);
// 查询这个位置的数据链是否有目标值
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 != null && key.equals(k))))
// 如果hash值相同 key相同，返回元素
return e;
}
return null;
}
// 根据key查找位置
static int indexFor(int h, int length) {
return h & (length-1);
}
JDK 1.8
HashMap JDK 1.8的数据结构
Node
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;
}
}
创建
// 默认加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 含 容量 的构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 含 容量 和 加载因子 的构造方法
public HashMap(int initialCapacity, float loadFactor) {
// 参数校验
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
// 如果容量大于最大值，则将容量设置成最大值
initialCapacity = MAXIMUM_CAPACITY;
// 加载因子校验
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
添加
// 添加元素
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;
if ((tab = table) == null || (n = tab.length) == 0)
// 如果容器是空的或者说是第一次添加，需要实例化数组
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果没有hash碰撞，即没有要插入的位置是空的，直接赋值即可。
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))))
// 已经存在key系统的对象，替换值
e = p;
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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 如果key相同，直接跳出循环
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 如果大于临界值就扩容
resize();
afterNodeInsertion(evict);
return null;
}
// 扩容
final Node<K,V>[] resize() {
// 记录旧的容器
Node<K,V>[] oldTab = table;
// 旧的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的边界值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果旧容量已经是最大值了，那就无需扩容，直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 容量扩大到原来的两倍，并且边界值也扩大到原来的两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果只提供了大于0的边界值，则新的容量大小设置为旧的边界值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 如果旧的容量为零，新的线程
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 定义新的临界值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//临界值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建Node[]
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 转移数据
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// e.hash & (newCap - 1) 是计算key的在table中的位置，然后赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果该节点是树，则需要插入树中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 如果只是链表节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
// 创建新Node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// 插入红黑树中
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
// 将所有链表节点装换成红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
什么时候扩容和树形化？
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的 默 认 值(DEFAULT_LOAD_FACTOR)为0.75， 这是一个折中的取值。 也就是说， 默认情况下， 数组大小(DEFAULT_INITIAL_CAPACITY)为16， 那么当HashMap中元素个数超过160.75=12（这个值就是代码中的threshold值， 也叫做临界值）的时候， 就把数组的大小扩展为 2*16=32， 即扩大一倍， 然后重新计算每个元素在数组中的位置， 而这是一个非常消耗性能的操作， 所以如果我们已经预知HashMap中元素的个数， 那么预设元素的个数能够有效的提高HashMap的性能。
当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。
JDK1.8中的变化
- HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组
- 当首次调用map.put()时，再创建长度为16的数组
- 数组为Node类型，在jdk7中称为Entry类型
- 形成链表结构时，新添加的key-value对在链表的尾部（七上八下）
- 当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置
上的所有key-value对使用红黑树进行存储。
LinkedHashMap
LinkedHashMap是HashMap的子类，它在HashMap的基础上，增加了首位指针，所以他是有序的。
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);
}
}
TreeMap
向TreeMap中添加key-value，要求key必须是由同一个类创建的对象,后面可以按照key进行排序：自然排序 、定制排序
Set
Set容器是存储无序的、不可重复的数据
HashSet
HashSet作为Set接口的主要实现类；它是线程不安全的，而且可以存储null值。 HashSet底层是数组+链表的结构，内部使用HashMap来充当容器，许多方法直接代理给了HashMap类的方法。
HashSet为例说明：
- 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
- 不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。
底层是数组， 初始容量为16， 当如果使用率超过0.75%（16*0.75=12）就会扩大容量为原来的2倍。（16扩容为32， 依次为64,128....等）
HashSet数据结构
创建
添加元素的过程：
我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，
此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断
数组此位置上是否已经有元素：
如果此位置上没有其他元素，则元素a添加成功。 --->情况1
如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值：
如果hash值不相同，则元素a添加成功。--->情况2
如果hash值相同，进而需要调用元素a所在类的equals()方法：
equals()返回true,元素a添加失败
equals()返回false,则元素a添加成功。--->情况2
对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。
jdk 7 :元素a放到数组中，指向原来的元素。
jdk 8 :原来的元素在数组中，指向元素a
总结：
七上八下
HashSet hashset = new HashSet();
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
jDK 1.7 插入方式
JDK 1.8 插入方式
LinkedHashSet
LinkedHashSet 作为HashSet的子类，他使用了头尾指针来实现了对顺序的记录，省得让Set有序。
LinkedHashSet数据结构
Entry
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);
}
}
TreeSet
TreeSet主要的特性是可以对元素进行自然排序（实现Comparable接口） 和 定制排序（Comparator）；向TreeSet中添加的数据，要求是相同类的对象。
- 自然排序中，比较两个对象是否相同的标准为：compareTo()返回0.不再是equals().
- 定制排序中，比较两个对象是否相同的标准为：compare()返回0.不再是equals().
网友评论