Java集合框架数据结构 Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，”x” 代表 key，”y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
Collection 接口的集合：List Arraylist： Object[] 数组，非线程安全，查找/修改快，添加/删除慢。增/删指定位置时要移动其它元素System.arraycopy() 初始大小10。** int newCapacity = oldCapacity + (oldCapacity >> 1);
Vector：Object[] 数组，线程安全。
LinkedList：双向链表(next、prev)，非线程安全，添加/删除快，查找/修改慢。
ArrayList扩容机制：
以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
添加元素前会判断是否需要扩容，ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，奇数丢掉小数是 1.5 倍左右）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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++; // 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 + (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: elementData = Arrays.copyOf(elementData, newCapacity); }
最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数
Set HashSet(无序，唯一): 基于 HashMap 实现的，底层数据结构是哈希表，采用 HashMap 来保存元素。
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的，是链表和哈希表，元素的插入和取出顺序满足 FIFO。
TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)，底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
三者都能保证元素唯一，但都是非线程安全的。
Queue PriorityQueue: Object[] 数组来实现二叉堆
ArrayQueue: Object[] 数组 + 双指针
Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。操作失败后处理方式的不同 分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Queue 接口抛出异常
返回特殊值
插入队尾
add(E e)
offer(E e)
删除队首
remove()
poll()
查询队首元素
element()
peek()
Deque 是双端队列，在队列的两端均可以插入或删除元素。扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法。Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。
Deque 接口抛出异常
返回特殊值
插入队首
addFirst(E e)
offerFirst(E e)
插入队尾
addLast(E e)
offerLast(E e)
删除队首
removeFirst()
pollFirst()
删除队尾
removeLast()
pollLast()
查询队首元素
getFirst()
peekFirst()
查询队尾元素
getLast()
peekLast()
ArrayDeque 与 LinkedList 的区别 ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？
ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。
PriorityQueue PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
这里列举其相关的一些要点：
PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第K大的数、带权图的遍历等，所以需要会熟练使用才行。
Map 接口的集合：HashMap 1.7之前：数组 + 单链表，头插法 链表散列
1.8之后：数组 + 单链表 + 红黑树 尾插法
1 2 3 4 5 6 7 8 9 10 11 12 //默认初始容量 - 必须是2的幂。 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //阈值，要调整大小时的阈值(capacity * load factor) int threshold;//如果尚未分配表数组，则此字段保存初始数组容量，或零表示DEFAULT_INITIAL_CAPACITY。 //链表转树的阈值 static final int TREEIFY_THRESHOLD = 8; //当链表长度大于阈值(默认为8)，将链表转换成红黑树前会判断，但如果当前数组的长度小于 64， 那么会选择先进行数组扩容，而不是转换为红黑树，数组大小>=64且链表长度>=8时将链表转化为红黑树，以减少搜索时间 static final int MIN_TREEIFY_CAPACITY = 64;//可以将 bin 树化的最小表容量。
容量大小为二次幂：在进行计算元素在数组中的位置，取模的位运算(n - 1) & hash的值避免相同，降低冲突概率。
1.8后使用红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。
HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
构造方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 //在指定initialCapacity时，计算threshold值，在初始化时threshold大小为初始数组的容量大小 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); } //返回给定目标容量的二次幂。 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; }
put()方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 //1.8 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); } //第一次put的时候才初始化HashMap final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //判断tab是否为空，为空则进行初始化resize() if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; 先判断hash值对应位置tab[(n - 1) & hash]位置是否存在元素 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //判断p的hash、key和要添加的hash、Key是否相同 e = p; else if (p instanceof TreeNode) //判断p是否是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)))) break; p = e; } } //如果存在key对应的元素，修改其value为新值 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); }
resize()：初始化或加倍表大小。如果为空，则根据字段阈值中持有的初始容量目标进行分配。否则，因为我们使用的是二次幂扩展，所以每个 bin 中的元素必须保持相同的索引，或者在新表中以二次幂的偏移量移动。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 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; } //扩容为原来的2倍 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 newCap = oldThr; //初始容量被置于阈值,在指定initialCapacity时 else { // zero initial threshold signifies using defaults //零初始阈值表示使用默认值，在未指定initialCapacity时 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //指定initialCapacity时，计算threshold值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; 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) 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; }
常见Map比较： HaspMap：内存浪费：存在25%，尤其扩容时2倍.。线程不安全。无序，可以存储 null 的 key 和 value，null 作为键只能有一个，null 作为值可以有多个。
Hashtable： 数组+链表 的形式，没有红黑树机制。线程安全，put/get方法是同步方法，对整个方法加锁，使用同一把锁 ，效率低。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态。无序，不允许有 null 键和 null 值。初始大小为 11，之后每次扩充，容量变为原来的 2n+1。
ConcurrentHashMap：1.7是数组 + 链表，1.8是数组 + 链表/红黑二叉树。线程安全，效率高，无序。
在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。 synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。
TreeMap：红黑树，不安全，有序。默认是按 key 的升序排序，可自定以排序的比较器。对元素有搜索的能力。
LinkedHashMap：不安全，有序。维护了一个双向链表，默认按插入顺序维护链表，
accessOrder传ture时为按访问顺序维护链表，可实现LRU。重写removeEldestEntry()自定义删除条件，返回true删除最近最少访问节点，false不会删除最近最少访问节点。accessOrder为true时访问节点后会调用afterNodeAccess()移到节点最后。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 // Callbacks to allow LinkedHashMap post-actions //访问完节点，accessOrder为true时将节点移到最后 void afterNodeAccess(Node<K,V> p) { LinkedHashMapEntry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } } //插入完节点是否删除最年长的(即最前面的head) void afterNodeInsertion(boolean evict) { LinkedHashMapEntry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } //removeNode()移除节点后调用，取消链接 void afterNodeRemoval(Node<K,V> p) { LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }
SparseArray int[] + Object[]
key为int类型，使用二分查找元素，按key大小存放
1 2 3 4 5 private int[] mKeys;//存放key @UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, E) private Object[] mValues;//存放value @UnsupportedAppUsage(maxTargetSdk = 28) // Use size() private int mSize;
构造
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public SparseArray() { this(10); } public SparseArray(int initialCapacity) { if (initialCapacity == 0) { mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length]; } mSize = 0; }
put()：二分查找key所在位置，key存在就替换value值，不存在就插入。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; } else { i = ~i; if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { gc(); // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } }
remove()：标记为DELETED，假删。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public void remove(int key) { delete(key); } public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } }
ArrayMap/SimpleArrayMap key为任何类型，key的hash值作为映射
value为Object[] mArray
其实是HashMap + SparseArray特点结合体
1 2 int[] mHashes; Object[] mArray;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public V put(K key, V value) { final int osize = mSize; final int hash; int index; if (key == null) { hash = 0; index = indexOfNull(); } else { hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode(); index = indexOf(key, hash); } if (index >= 0) { index = (index<<1) + 1; final V old = (V)mArray[index]; mArray[index] = value; return old; } ... } //把Object类型key转成Int int indexOf(Object key, int hash) { }
红黑树(Red-Black Tree，简称R-B Tree)，它一种平衡二叉查找树。
(1) 每个节点或者是黑色，或者是红色。
左旋：对x进行左旋，意味着”将x变成一个左节点”。
右旋：对y进行右旋，意味着”将y变成一个右节点”。
二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。
平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。红黑树应用广泛，如Java的TreeMap和TreeSet。