Java容器

Java容器

Java集合主要由两大接口派生而来：一是collection，用于存放单一元素；二是map，用于存放键值对。

List ArrayList

基于动态数组实现，支持随机访问。

扩容机制

// minCapacity为最小需要容量
private void grow(int minCapacity) {
	// oldCapacity为当前容量，初始默认容量为10
	int oldCapacity = elementData.length;
	// 新容量更新为旧容量的1.5倍，
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	// 检查新容量是否满足需要，若不满足则直接把最小需要容量当作数组的新容量
	if (newCapacity - minCapacity < 0)
	    newCapacity = minCapacity;
	// 再检查新容量是否超出了ArrayList所定义的最大容量，若超出则新容量则为Interger.MAX_VALUE
	if (newCapacity - MAX_ARRAY_SIZE > 0)
	    newCapacity = Interger.MAX_VALUE;

	// 复制元素至新数组
	...
}

Vector

基于动态数组实现，支持构造时配置扩容倍数（默认是2）。
通过对方法加synchronized来保证线程安全，性能较差。

linkedList

基于双向链表实现，只能顺序访问。

Set 特点

• 无序性
  存储的数据在底层数组中不是按照数组索引顺序添加的，而是根据数据的hash值。
• 不可重复性
  判断元素是否重复会根据equals()和hashCode()方法，故两者都需要重写。

实现类

• HashSet、linkedHashSet 和 TreeSet 都是Set接口的实现类，都不保证线程安全
• HashSet基于哈希表（HashMap）；linkedHashSet基于链表和哈希表，元素进出满足FIFO规则；TreeSet基于红黑树，元素有序存储。

Queue

根据对 因容量问题而导致的 *** 作失败 的处理方式，分为两组方法：

抛出异常返回特殊值插入队尾add(E e)offer(E e)移除队首remove()poll()插入队尾element()peek() Deque

扩展为两端队列，在队列的两端均可以插入或删除元素。
ArrayDeque 和 linkedList 都实现了 Deque 接口，前者不能存 null。

PriorityQueue

优先级高的先出队。
基于二叉堆实现，底层用动态数组存储数据。
通过堆元素的上浮和下沉，插入和删除的时间复杂度为O(logn)
不保证线程安全，不支持存储 null 和 non-comparable 对象。

Map HashMap 数据结构

基于数组+链表+红黑树(JDK1.8)实现

通过Entry数组存储键值对，Entry同时也是单向链表的节点。
链表在数组中的位置，是对key的hashCode进行高低十六位异或，再对数组长度取模而得。

扩容机制

初始容量capacity(默认值16)，扩容阈值为 capacity * loadFactor(默认0.75)，每次扩容翻倍。
若创建时指定了容量，则初始容量为大于等于指定值的最小2的幂次方。

static final int tableSizeFor(int cap) {
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Q：为什么HashMap容量必须是2的幂次方？
A：因为HashMap确认元素在数组中的位置时，涉及到取模运算。而注意到 x % 2n = x & (2n-1) ，因此将capacity设计为 2n，从而把取模计算转换为与计算，提高效率。

插入流程

遍历方式

使用迭代器，既高效又安全。

并发问题

HashMap不保证线程安全，并发下存在数据覆盖、丢失以及扩容引起的死循环问题（元素间形成一个循环链表，JDK1.8通过将头插法改为尾插法解决）。

ConcurrentHashMap

JDK1.7采用分段锁Segment，每个Segment维护着几个桶HashEntry，多个线程可以同时访问不同分段锁上的桶。
JDK1.8放弃了分段锁，使用CAS *** 作来支持更高的并发度，在 CAS *** 作失败时使用内置锁 synchronized（只锁当前链表或红黑树的首节点，只有hash冲突时才产生并发，效率大大提高）。

Collections

Collections 工具类常用方法:①排序 ②查找&替换

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素