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 是无序的、可重复的，每个键最多映射到一个值。
ArrayList在之前已经讲过
vector
vectord底层也是对象数组 protected Object[] elementData;
vector是线程同步的 Vector 类的操作方法带有 synchronized
vector源码分析
创建vector对象 并循环添加
public class Vector_ {
public static void main(String[] args) {
// 无参构造 创建对象
Vector vector = new Vector();
for (int i = 0; i < 10; i++) {
vector.add(i);
}
}
}
首先执行无参构造器
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
所以new Vector（）会默认创建容量为10的对象数组
add方法添加时
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
首先执行ensureCapacityHelper() 方法判断是否要扩容
如果数组所需的最小容量大于当前数组容量，执行grow方法扩容
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow()方法源码：
默认扩容两倍大小
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);
}
也可指定扩容大小。在vector带参构造器中指定扩容大小
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
LinkedList
LinkedList底层是双向链表所以不需要扩容
LinkedList与ArrayList的区别
- 线程都是不安全的
- LinkedList的底层数据结构是双向链表，ArrayList底层数据结构是Object []数组
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
- LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），近似 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)） 时间复杂度近似为 O(n) ，因为需要先移动到指定位置再插入。
- LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
- ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）
Set
存放数据无序（但是取出的顺序是固定的），不许重复，所以null最多只有一个，
不能通过索引获取
HashSet
HashSet底层是HashMap
不能有重复的元素或对象的理解
package set;
import java.util.HashSet;
import java.util.Set;
public class SetTest {
public static void main(String[] args) {
Set set = new HashSet();
set.add("zf");
set.add("zf");//失败
set.add(new Dog("哈哈"));//成功
set.add(new Dog("哈哈"));//成功
System.out.println(set);
set.add(new String("test"));//成功
set.add(new String("test"));//失败
System.out.println(set);
}
}
class Dog{
public String name;
public Dog(String name) {
this.name = name;
}
@Override
public String toString() {
return "Dog{" +
"name='" + name + '\'' +
'}';
}
}
判断是否能够加入数据的依据是根据Hash()和equals进行比较的
HashMap扩容机制
先说结论
源码：
//对该代码进行分析
package set;
import java.util.HashSet;
public class HashSetSourceCode {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("c++");
hashSet.add("java");
System.out.println(hashSet);
}
}
首先第一步进入构造方法
public HashSet() {
map = new HashMap<>();
}
由此证明HashSet底层是HashMap了
添加第一个数据时
public boolean add(E e) { //e:"java"
return map.put(e, PRESENT)==null; PRESENT是一个final类型静态的一个Object对象
}
执行put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这时进入hash方法
//进入到hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//这里的hash方法计算出来的不是hashcode 而是计算出hashcode 与hashcode无符号右移16位 的值进行按位异或
}
真正的putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; //一些辅助变量
//这里的table就是HashMap中存储数据的Node数组
//if当前table为空 大小为0 第一次库容到16空间
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据key得到hash 去计算key应该存放到table表的哪个索引位置 并把这个位置对象赋给p
//如果p为空 还没放过数据 就创建一个node
if ((p = tab[i = (n - 1) & hash]) == null) //n=16 根据(n - 1) & hash确定要放数据的索引 如果当前这里没数据 就newNode（）将hash key value放进去
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)
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 判断现在数据数量是否大于12
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
如果tab和table值为空 进入到resize方法
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
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //赋容量为16
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<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;
}
第二次进入putVal
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)//不会进入这句 因为table中已经有数据
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)
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; //再次modCount++
if (++size > threshold) // 判断是否大于12
resize();
afterNodeInsertion(evict);
return null;
}
第三次put 放入跟第一次相同的数据 情况如何？
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)
tab[i] = newNode(hash, key, value, null);
else {
//进入这段代码
Node<K,V> e; K k;
//如果当前索引位置对应的链表第一个元素的hash值跟 要放入放入元素的hash值相同 并且 准备加入的key和p指向node节点的key是同一个对象 或者key不是空 且 要加入的key和指向p的key 满足equals 这里的equals方法是看程序员确定的 看他是否重写了
//那么就不能添加了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再看这个条件 看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 （8）- 1) // -1 for 1st 在把元素添加到链表后立即判断 链表是否有8个节点 有8个节点 就对该条链表 进行树化
treeifyBin(tab, hash); //在这个方法中 并不一定会直接转换成红黑树 要判断 如果table大小 小于64
//if(tab ==null || (n=tab.length) <MIN_TREEIFY_CAPACITY(64) ) resize();
//如果成立条件 才扩容 不成立 进行转成红黑树
break;
}
//如果有相同的直接break
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
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;
}
树化机制：我们知道相同hashcode且equals不相同的值会放到一条链表里面，当这条链表里面的size大于等于8，且table表的长度大于等于64会进行树化，但是没有达到64时不会树化，但是会触发resize方法。
比如table里面有16个数据，但是一条链表上有7个元素，再添加一个后，table长度会变到32，再添加一个会变到64，然后就树化了
关于扩容因子12
if (++size > threshold)
resize();
扩容的代码在这里 这里的size指的是 添加节点的个数 不管是table表上的还是在链表上的 都算在内
1.先获取元素的哈希值
2.对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号
3.如果该位置上没有其他元素，则直接存放 如果在位置上已经有其他元素，需要进行equals判断 相等不添加 不相等则添加
小总结
以下内容摘自我的 Java 启蒙书《Head first java》第二版：
当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
在openjdk8中，HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet中的源码
也就是说，在openjdk8中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。
hashCode()与 equals() 的相关规定：
如果两个对象相等，则 hashcode 一定也是相同的
两个对象相等,对两个 equals() 方法返回 true
两个对象有相同的 hashcode 值，它们也不一定是相等的
综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。
==与 equals 的区别
对于基本类型来说，== 比较的是值是否相等；
对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）；
对于引用类型（包括包装类型）来说，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。
LinkedHashSet
继承了hashset实现了set接口
1.LinkedHashSet 取出数据时跟加入数据的顺序一致
2..LinkedHashSet 底层维护的是数组+双向链表，底层维护的是LinkedHashMap（HashMap的子类）
3.LinkedList添加第一个数据将table扩容到16 存放的节点类型是 LinkedHashMap$Entry
4.数组是HashMap$Node[] 存放的元素是LinkedHashMap$Entry类型
//继承关系是在内部类完成的
static class Entry<K,V> extends HashMap.Node<K,V>{ //继承了HashMap.Node 所以他可以存放双向链表的结构
Entry<K,V> before,after;
Entry(int hash,K key,V value,Node<K,V> next){
super(hash,key,value,next);
}
}
Map
map中的每一组key value数据是放在一个叫HashMap$Node的数据类型中的 ，但是为了方便我们遍历，于是有了entry和EntrySet 。EntrySet中存放着entry，每个entry的key其实是指向 HashMap$Node的key位置 每个entry的value其实是指向 HashMap$Node的value位置
HashMap的扩容机制和HashSet基本没有差别
这里简单介绍一下
/**
* 第一步进入构造方法 new HashNap()
* 初始化 加载因子 loadFactory =0.75
* 此时有一个 HashMap$Node 类型的数组 但为空
*
* 2.执行put
* public V put(K key, V value) {// key value 就是对应的传入值
* return putVal(hash(key), key, value, false, true);
* }
* 算hash
*
* 3.执行putVal()
* 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)
* tab[i] = newNode(hash, key, value, null); //为空 无哈希冲突
* else {
* Node<K,V> e; K k;
* //如果哈希值相同 如果key相同 且key不为空 且key equals k
如果table的索引位置的key的hash相同和新的key的hash值相同，
并满足(table现有的结点的key和准备添加的key是同一个对象 或equals返回真)
* if (p.hash == hash &&
* ((k = p.key) == key || (key != null && key.equals(k))))
* e = p;
* else if (p instanceof TreeNode) //当前table的node已经是红黑树
* 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;
* }
* }
* if (e != null) { // existing mapping for key
* V oldValue = e.value;
* if (!onlyIfAbsent || oldValue == null)
* e.value = value; //key 已经存在了 这是替换原来key对应的value 所以执行这句代码
* afterNodeAccess(e);
* return oldValue;
* }
* }
* ++modCount; //增加一个node size++
* if (++size > threshold)
* resize();
* afterNodeInsertion(evict);
* return null;
* }
*/
HashTable
扩容机制 rehash（）方法
Properties
Hashtable子类
参考springboot配置文件.properties
TreeSet
可排序
public class TreeSetTest {
public static void main(String[] args) {
//使用无参构造器创建treeset 依然无序
//使用有参构造器 匿名内部类实现conparator接口
//如果实现类comparator接口能否加入 是取决于 比较的规则是否相等
/**
* 比如我们按照长度排序 treeSet.add("zs");
* treeSet.add("ko");（加不进去ko）只能加进去一个长度为2的 有一个
*/
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String) o2).charAt(0)-((String) o1).charAt(0);
}
});
treeSet.add("dsak");
treeSet.add("ab");
treeSet.add("zs");
treeSet.add("ko");
treeSet.add("ki");
System.out.println(treeSet);
/**
* 1，构造器把传入的比较器对象，赋给了TreeSet的底层的 TreeNap的属性this.comparator
* public TreeMap(Comparator<? super K> comparator) {
* this.comparator = comparator;
*/
/*
2。在调用treeSet.add( "tom")，在底层会执行到
if (cpr != null) {//cpr就是我们的匿名内部类(对象)
do {
parent = t;
/动态绑定到我们的匿名内部类(对象)comparecmpI= cpr.compare(key,t.key);
if (cmp < 0)
t = t.left;
else if (cmp >0)
t = t.right;
else //如果相等不加入
return t.setValue(value);
}while (t != null);
}
*/
Collections
Collections 工具类常用方法:
排序
查找,替换操作
同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)
排序操作
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)//用新元素替换旧元素
package Collections_;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class CollectionTest {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("tom");
list.add("tom");
list.add("javc22k");
list.add("zhefu");
list.add("sjadka");
//翻转
Collections.reverse(list);
System.out.println(list);
//随机排序
Collections.shuffle(list);
//自然排序
Collections.sort(list);
//自定义比较器
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length()-o2.length();
}
});
//执行位置交换
Collections.swap(list,0,2);
System.out.println(list);
//根据元素的自然排序返回给定集合的最大元素
System.out.println("根据元素的自然排序返回给定集合的最大元素"+Collections.max(list));
//自定义比较规则返回给定集合的最大元素
System.out.println("自定义比较规则返回给定集合的最大元素"+Collections.max(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
}));
//根据元素的自然排序返回给定集合的最小元素 min
//自定义比较规则返回给定集合的最小元素
//查看集合的元素出现次数
System.out.println("查看集合的元素出现次数"+Collections.frequency(list, "tom"));
ArrayList<Object> objects = new ArrayList<>();
for (int i = 0; i <list.size() ; i++) {
objects.add("");
}
//要提前确定长度 才能copy 否则报错
Collections.copy(objects,list);
System.out.println(objects);
}
}
