集合
集合基本介绍
- 可以动态保存任意多个对象
- 提供了一系列方便的操作对象的方法
- 使用集合添加、删除新元素的示意代码更简洁
集合框架体系
Collection
基本介绍：
- Collection实现子类可以存放多个元素，每个元素都是object类
- 有些Collection的实现类，可以存放重复的元素，有的不可以
- Collection的实现类，有些是有序的(List)，有些不是有序(Set)
- Collection接口没有直接的实现子类，是通过它的子接口Set 和 List 来实现的
接口常用方法
add：添加单个元素
remove：删除指定元素
contains：查找元素是否存在
size：获取元素个数
isEmpty：判断是否为空
clear：清空
addAll：添加多个元素
containsAll：查找多个元素是否都存在
removeAll：删除多个元素
List list = new ArrayList();
// add:添加单个元素
list.add("jack");
list.add(10);//list.add(new Integer(10))
list.add(true);
System.out.println("list=" + list);
// remove:删除指定元素
//list.remove(0);//删除第一个元素
list.remove(true);//指定删除某个元素
System.out.println("list=" + list);
// contains:查找元素是否存在
System.out.println(list.contains("jack"));//T
// size:获取元素个数
System.out.println(list.size());//2
// isEmpty:判断是否为空
System.out.println(list.isEmpty());//F
// clear:清空
list.clear();
System.out.println("list=" + list);
// addAll:添加多个元素
ArrayList list2 = new ArrayList();
list2.add("红楼梦");
list2.add("三国演义");
list.addAll(list2);
System.out.println("list=" + list);
// containsAll:查找多个元素是否都存在
System.out.println(list.containsAll(list2));//T
// removeAll：删除多个元素
list.add("聊斋");
list.removeAll(list2);
System.out.println("list=" + list);//[聊斋]
// 说明：以ArrayList实现类来演示.
Collection接口常用遍历元素方式
- Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。
- 所有实现了Collection:接口的集合类都有一个iterator()方法，用以返回 一个实现了Iterator接口的对象，即可以返回一个迭代器。
- Iterator的结构.（看图）
- Iterator仅用于遍历集合，Iterator本身并不存放对象。
迭代器的使用
Collection col = new ArraryList();
col.add("AAA");
col.add("BBB");
col.add("CCC");
//得到col对应的迭代器
Iterator iterator = col.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println(obj);
}
//使用itit快捷键可以快速生成迭代器遍历
增强for循环
for(Object obj : col){
System.out.println(obj);
}
List
基本介绍
- List集合类中元素有序（即添加顺序和取出顺序一致）、且可重复
- List集合中的每个元素都有其对应的顺序索引，即支持索引
- List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器元素
- 常用： ArrayList、LinkedList、Vector
常用方法
-
void add(int index, Object ele)：在index位置插入ele元素
-
boolean addAll(int index, Collection eles)：从index位置开始将eles中的所有元素添加进来
-
Object get(int index)：获取指定index位置的元素
-
int indexOf(Object obj)：返回obj在集合中首次出现的位置
-
int lastindexOf(Object obj)：返回obj在当前集合中末次出现的位置
-
Object remove(int index)：移除指定index位置的元素，井返回此元素
-
Object set(int index, Object ele)：设置指定index位置的元素为ele，相当于是替换
-
List sublist(int fromlndex, int tolndex)：返回从fromlndex到tolndex位置的子集合
List list = new ArrayList(); list.add("张三丰"); list.add("贾宝玉"); // void add(int index, Object ele):在index位置插入ele元素 //在index = 1的位置插入一个对象 list.add(1, "韩顺平"); System.out.println("list=" + list); // boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来 List list2 = new ArrayList(); list2.add("jack"); list2.add("tom"); list.addAll(1, list2); System.out.println("list=" + list); // Object get(int index):获取指定index位置的元素 // int indexOf(Object obj):返回obj在集合中首次出现的位置 System.out.println(list.indexOf("tom"));//2 // int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置 list.add("韩顺平"); System.out.println("list=" + list); System.out.println(list.lastIndexOf("韩顺平")); // Object remove(int index):移除指定index位置的元素，并返回此元素 list.remove(0); System.out.println("list=" + list); // Object set(int index, Object ele):设置指定index位置的元素为ele , 相当于是替换. list.set(1, "玛丽"); System.out.println("list=" + list); // List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合 // 注意返回的子集合 fromIndex <= subList < toIndex List returnlist = list.subList(0, 2); System.out.println("returnlist=" + returnlist);
List常用遍历方式[ArraryList,LinkedList,Vector]
List list = new LinkedList();
list.add("AAA");
list.add("BBB");
list.add("CCC");
//迭代器
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
System.out.println("obj=" + obj);
}
//增强for循环
for(Object obj : list){
System.out.println("obj=" + obj);
}
//普通for循环
for(int i = 0;i < list.size();i++){
System.out.println("obj=" + list.get(i));
}
ArraryList
注意事项：
(1) 允许所有元素包括null加入
(2) ArrayList 是由数组来实现数据存储的
(3) ArrayList 基本等同于Vector，除了 ArrayList是线程不安全（执行效率高），在多线程情况下，不建议使用ArrayList
底层结构：
(1) ArrayList中维护了一个Object类型的数组elementData，transient Object[] elementData;
transient 表示瞬间,短暂的，表示该属性不会被序列化
(2) 创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData 为1.5倍
(3) 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍
Vector
注意事项：
(1) Vector底层是一个对象数组， protected Object[] elementData;
(2) Vector 是线程同步的，即线程安全，Vector类的操作方法带有synchronized
底层结构：
(1) 无参构造器默认初始化大小为10，有参构造器容量自己设置
(2) 每次扩容将会扩容2倍
public class Vector_ {
public static void main(String[] args) {
//无参构造器
//有参数的构造
Vector vector = new Vector(8);
for (int i = 0; i < 10; i++) {
vector.add(i);
}
vector.add(100);
System.out.println("vector=" + vector);
//1. new Vector() 底层
/*
public Vector() {
this(10);
}
补充：如果是 Vector vector = new Vector(8);
走的方法:
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
2. vector.add(i)
2.1 //下面这个方法就添加数据到vector集合
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
2.2 //确定是否需要扩容 条件 ： minCapacity - elementData.length>0
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
2.3 //如果 需要的数组大小 不够用，就扩容 , 扩容的算法
//newCapacity = oldCapacity + ((capacityIncrement > 0) ?
// capacityIncrement : oldCapacity);
//就是扩容两倍.
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);
}
*/
}
}
ArraryList 和 Vector
LinkedList
注意事项：
(1) LinkedList底层实现了双向链表和双端队列特点
(2) 可以添加任意元素包括null
(3) 线程不安全，没有实现同步
底层结构：
(1) Linkedlist底层维护了一个双向链表
(2) Linkedlist中维护了两个属性first和last分别指向首节点和尾节点
(3) 每个节点（Node对象），里面又维护了prev、next.item三个属性，其中通过
prev指向前一个，通过next指向后一个节点。最终实现双向链表
(4)所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高
ArrayList和LinkedList:
(1) 如果我们改查的操作多，选择ArrayList
(2) 如果我们增删的操作多，选择LinkedList
(3) 一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList
Set
HashSet
注意事项:
(1) Hashset实现了Set接口
(2) Hashset实际上是HashMap
(3) 可以存放null值，但是只能有一个null
(4) Hashset不保证元素是有序的,取决于hash后，再确定索引的结果
(5) 不能有重复元素/对象
底层结构:
(1) HashSet 底层是 HashMap
(2) 添加一个元素时，先得到hash值会转成索引值
(3) 找到存储数据表table，看这个素引位置是否己经存放的有元素如果没有，直接加入
(4) 如果有调用equals 比较，如果相同，就放奔添加，如果不相同，则添加到最后
(5) 在Java8中，如果一条链表的元素个数超过 TREEIFY THRESHOLD（默认是8），并且table的大小＞=MIN TREEIFY CAPACITY（默认 64)就会进行树化(红黑树）
// 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;
//通过hash值查找数组下标，如果该下标位置为空，则直接将数据存放到此处
// if ((p = tab[i = (n - 1) & hash]) == null)
// tab[i] = newNode(hash, key, value, null);
//如果数组下标存放的不为空，则查看链表判断是否有相等的值
// else {
// Node<K,V> e; K k;
// 判断链表上第一个元素(数组下标的位置) 是否 相等，则将原链表上的数据赋值给e
// 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) {
//将e向后移,e初始化是链表第2个元素（数组下标的next元素）
//判断该节点是否为空，为空则直接将数据挂载 并跳出循环
// 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向后移动
// p = e;
// }
// }
//如果e为空，则说明已经将数据挂载到链表上，e不为空说明将原链表上的数据赋值给e
// if (e != null) { // existing mapping for key
// V oldValue = e.value;
// if (!onlyIfAbsent || oldValue == null)
// e.value = value;
// afterNodeAccess(e);
//将oldValue返回
// return oldValue;
// }
// }
// ++modCount;
//将size加1 并判断是否达到阈值，如果达到阈值，则进行扩容
// if (++size > threshold)
// resize();
// afterNodeInsertion(evict);
//前面将数据挂载到链表，则返回null
// return null;
// }
// resize方法
// final Node<K,V>[] resize() {
// Node<K,V>[] oldTab = table;
//如果表为空则oldCap为0，不为空则将数组的大小赋值给oldCap
// int oldCap = (oldTab == null) ? 0 : oldTab.length;
//将阈值赋值给oldThr
// int oldThr = threshold;
// int newCap, newThr = 0;
//如果oldCap大于0，则进行扩容
// if (oldCap > 0) {
// if (oldCap >= MAXIMUM_CAPACITY) {
// threshold = Integer.MAX_VALUE;
// return oldTab;
// }
//oldCap << 1 oldThr << 1
// else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
// oldCap >= DEFAULT_INITIAL_CAPACITY)
// newThr = oldThr << 1; // double threshold
// }
// 如果 oldCap小于等于0且之前的阈值大于0，则将oldThr赋值给newCap
// else if (oldThr > 0) // initial capacity was placed in threshold
// newCap = oldThr;
//如果 oldCap小于等于0且之前的阈值小于等于0
//则对数组进行初始化
// 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);
// }
//将newThr赋值给阈值
// threshold = newThr;
// @SuppressWarnings({"rawtypes","unchecked"})
//根据新的数组大小创建新的数组
// Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新的数组赋值给table
// table = newTab;
//如果oldTab不等于null，则将原本的数据赋值给新的数组
// 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;
// }
扩容和红黑树机制：
(1) HashSet底层是HashMap
(2) 第一次添加时，table 数组扩容到 16，临界值(threshold)是 16*加载因子(loadFactor)是0.75= 12
(3) 每加入一个节点，size就会++，到达临界值就会扩容
(4) 如果table 数组使用到了临界值 12,就会扩容到16*2=32,新的临界值就是32*0.75=24，依次类推
(5) 在Java8中，如果一条链表的元素个数到达 TREEIFY_ THRESHOLD(默认是 8）井且table的大小＞=MIN TREEIFY CAPACITY (默认64),就 会进行树化(红黑树），否则仍然采用数组扩容机制
HashSet 去重机制:
HashSet去重机制: hashCode() + equals()，底层先通过存入对象，通过运算hash值得到对应的索引，如果table索引所在的位置没有数据就直接存放；如果有数据就比较 ( hash值和key值 ) 或者 ( 进行equals（注意重写情况）比较 )[遍历比较]，如果比较后，不相同就加入，否则就不加入
LinkedHashSet
注意事项:
(1) LinkedHashset 是Hashset 的子类
(2) LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个 数组＋双向链表
(3) LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序(图)，这使得元素看起来是以插入顺 序保存的
(4) LinkedHashSet 不允许添重复元素
底层结构:
(1) LinkedHashSet 加入顺序和取出元素/数据的顺序一致
(2) LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类)
(3) LinkedHashSet 底层结构 (数组table+双向链表)
(4) 添加第一次时，直接将 数组table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry ( 继承HashMap$Node[] )
(5) 数组是 HashMap$Node[] 存放的元素/数据是 LinkedHashMap$Entry类型
public class LinkedHashSetSource {
public static void main(String[] args) {
//分析一下LinkedHashSet的底层机制
Set set = new LinkedHashSet();
set.add(new String("AA"));
set.add(456);
set.add(456);
set.add(new Customer("刘", 1001));
set.add(123);
set.add("HSP");
System.out.println("set=" + set);
//1. LinkedHashSet 加入顺序和取出元素/数据的顺序一致
//2. LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类)
//3. LinkedHashSet 底层结构 (数组table+双向链表)
//4. 添加第一次时，直接将 数组table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry
//5. 数组是 HashMap$Node[] 存放的元素/数据是 LinkedHashMap$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);
}
}
*/
}
}
class Customer {
private String name;
private int no;
public Customer(String name, int no) {
this.name = name;
this.no = no;
}
}
TreeSet
注意事项:
(1) TreeSet中 不允许有重复的值
底层机制：
(1) TreeSet()构造器需传入Comparator接口的匿名内部类，因为底层 Comparable<? super K> k = (Comparator<? super K>) key;
若没有传入，则需要把传入的类实现Comparable接口
(2) 若按照compare方法比较value相同则无法加入value
public class TreeSet_ {
public static void main(String[] args) {
// 当我们使用无参构造器，创建TreeSet时，默认按字母排序
//使用TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)
// 并指定排序规则
// 简单看看源码
/*
1. 构造器把传入的比较器对象，赋给了 TreeSet的底层的 TreeMap的属性this.comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
2. 在 调用 treeSet.add("tom"), 在底层会执行到
if (cpr != null) {//cpr 就是我们的匿名内部类(对象)
do {
parent = t;
//动态绑定到我们的匿名内部类(对象)compare
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else //如果相等，即返回0,这个Key就没有加入
return t.setValue(value);
} while (t != null);
}
else {
//如果key是null便会报错
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
该位置要求传入的key必须实现Comparable接口，否则会报错
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
*/
// TreeSet treeSet = new TreeSet();
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//下面 调用String的 compareTo方法进行字符串大小比较
//加入的元素，按照长度大小排序
//return ((String) o2).compareTo((String) o1);
return ((String) o1).length() - ((String) o2).length();
}
});
//添加数据.
treeSet.add("jack");
treeSet.add("tom");//3
treeSet.add("sp");
treeSet.add("a");
treeSet.add("abc");//3
System.out.println("treeSet=" + treeSet);
}
}
Map
基本介绍：
(1) Map与Collection井列存在，用于保存具有映射关系的数据
(2) Map 中的key 和 value 可以是任何引用类型的数据，会封装到HashMap$Node对象中
(3) Map 中的key 不允许重复，原因和HashSet 一样
(4) Map 中的value 可以重复
(5) Map 的key可以为null，value也可以为null，key为null只有能有一个，value为null可以为多个
(6) 常用String类作为Map的key
(7) key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value
(8) Map存放数据的key-value示意图，一对 k-y是放在一个Node中的，有因为Node 实现了 Entry 接口
常用方法：
-
put：添加
-
remove：根据键删除映射关系
-
get：根据键获取值
-
size：获取元素个数
-
isEmpty：判断个数是否为0
-
clear：清除
-
containskey：查找键是否存在
public class MapMethod {
public static void main(String[] args) {
//演示map接口常用方法
Map map = new HashMap();
map.put("邓超", new Book("", 100));//OK
map.put("邓超", "孙俪");//替换-> 一会分析源码
map.put("王宝强", "马蓉");//OK
map.put("宋喆", "马蓉");//OK
map.put("刘令博", null);//OK
map.put(null, "刘亦菲");//OK
map.put("鹿晗", "关晓彤");//OK
map.put("hsp", "hsp的老婆");
System.out.println("map=" + map);
// remove:根据键删除映射关系
map.remove(null);
System.out.println("map=" + map);
// get：根据键获取值
Object val = map.get("鹿晗");
System.out.println("val=" + val);
// size:获取元素个数
System.out.println("k-v=" + map.size());
// isEmpty:判断个数是否为0
System.out.println(map.isEmpty());//F
// clear:清除k-v
//map.clear();
System.out.println("map=" + map);
// containsKey:查找键是否存在
System.out.println("结果=" + map.containsKey("hsp"));//T
}
}
class Book {
private String name;
private int num;
public Book(String name, int num) {
this.name = name;
this.num = num;
}
}
遍历方式：
有如下3种方式：
(1) 先取出 所有的Key , 通过Key 取出对应的Value
(2) 把所有的values取出
(3) 通过 EntrySet 来获取 k-v
import java.util.*;
@SuppressWarnings({"all"})
public class Test1 {
public static void main(String[] args) {
Map map = new HashMap();
//map的遍历方式
map.put("NO1", "AAA");
map.put("NO2", "BBB");
map.put("NO3", "CCC");
//第一组
Set keySet = map.keySet();
//增强for循环
for(Object key:keySet){
System.out.println(map.get(key));
}
//迭代器
Iterator iterator = keySet.iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(map.get(key));
}
//第二组
Collection values = map.values();
//增强for循环
for(Object value : values){
System.out.println(value);
}
iterator = values.iterator();
while (iterator.hasNext()) {
Object value = iterator.next();
System.out.println(value);
}
//第三组
Set entrySet = map.entrySet();
//增强for循环
for(Object entry : entrySet){
System.out.println(((Map.Entry)entry).getKey() + "-" +
((Map.Entry)entry).getValue() );
}
iterator = entrySet.iterator();
while (iterator.hasNext()) {
Object entry = iterator.next();
System.out.println(((Map.Entry)entry).getKey() + "-" +
((Map.Entry)entry).getValue() );
}
}
}
HashMap
注意事项:
(1) HashMap是Map 接口使用频率最高的实现类
(2) Hashap 是以 key-val 对的方式来存储数据(HashMap$Node类型）
(3) key 不能重复，但是值可以重复，允许使用null和null值
(4) 如果添加相同的key，则会覆盖原来的key-val ，等同于修改（key不会替换，val会替换）
(5) 与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的(jdk8的hashMap 底层 数组＋链表＋红黑树）
(6) HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized
底层结构:
(1) 扩容机制和Hashset相同
(2) HashMap底层维护了Node类型的数组table，默认为null,HashMap$Node 实现了Map$Entry 接口
(3) 当创建对象时，将加载因子(loadfactor)初始化为0.75
(4) 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元 素，继续判断该元素的key是否和准备加入的key相等，如果相等，则直接替换value：如果不相等需要判断是树结构还是链表结构， 做出相应处理。如果添加时发现容量不够，则需要扩容
(5) 第1次添加，则需要扩容table容量为16，临界值(threshold)为12
(6) 以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍,即24，依次类推
(7) 在Java8中，如果一条链表的元素个数超过 TREEIFY THRESHOLD（默认是8），并且
table的大小＞=MIN TREEIFY CAPACITY（默认64),就会进行树化（红黑树）
public class HashMapSource1 {
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("java", 10);//ok
map.put("php", 10);//ok
map.put("java", 20);//替换value
System.out.println("map=" + map);//
/*
1. 执行构造器 new HashMap()
初始化加载因子 loadfactor = 0.75
HashMap$Node[] table = null
2. 执行put 调用 hash方法，计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//K = "java" value = 10
return putVal(hash(key), key, value, false, true);
}
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;//辅助变量
//如果底层的table 数组为null, 或者 length =0 , 就扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v
//, 创建成一个 Node ,加入该位置即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;//辅助变量
// 如果table的索引位置的key的hash相同和新的key的hash值相同，
// 并 满足(table现有的结点的key和准备添加的key是同一个对象 || equals返回真)
// 就认为不能加入新的k-v
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);
//加入后，判断当前链表的个数，是否已经到8个，到8个，后
//就调用 treeifyBin 方法进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && //如果在循环比较过程中，发现有相同,就break,就只是替换value
((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对应value
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//每增加一个Node ,就size++
if (++size > threshold[12-24-48])//如size > 临界值，就扩容
resize();
afterNodeInsertion(evict);
return null;
}
5. 关于树化(转成红黑树)
//如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
//否则才会真正的树化 -> 剪枝
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();
}
*/
}
}
HashTable
注意事项：
(1) 存放的元素是键值对：即K-V
(2) hashtable的键和值都不能为null， 否则会抛出NulPointerException
原因：
if (value == null) {
throw new NullPointerException();
}
int hash = key.hashCode();
(3) hashTable 使用方法基本上和HashMap一样
(4) hashTable 是线程安全的(synchronized)，hashMap 是线程不安全的
(5) HashTable 添加节点采用头插法,HashMap 采用尾插法
底层机制
(1) 底层有数组 Hashtable$Entry[] 初始化大小为 11
(2) 临界值 threshold 8 = 11 * 0.75
(3) 扩容: 当 if (count >= threshold) 满足时，就进行扩容,按照 int newCapacity = (oldCapacity << 1) + 1;的大小扩容
(4) 执行方法 addEntry(hash, key, value, index); 添加K-V 封装到Entry
HashMap和HashTable
Properties
注意事项：
(1) Properties类继承Hashtable类，实现了Map接口，也是使用一种简直对的形式保存数据
(2) 使用特点和Hashtable类似
(3) Properties 还可以用于 从xxx.properties 文件中，加载数据到Properties类对象井进行读取和修改
(4) xxx.properties 文件通常作为配置文件
public class Properties_ {
public static void main(String[] args) {
//1. Properties 继承 Hashtable
//2. 可以通过 k-v 存放数据，当然key 和 value 不能为 null
//增加
Properties properties = new Properties();
//properties.put(null, "abc");//抛出 空指针异常
//properties.put("abc", null); //抛出 空指针异常
properties.put("john", 100);//k-v
properties.put("lucy", 100);
properties.put("lic", 100);
properties.put("lic", 88);//如果有相同的key ， value被替换
System.out.println("properties=" + properties);
//通过k 获取对应值
System.out.println(properties.get("lic"));//88
//删除
properties.remove("lic");
System.out.println("properties=" + properties);
//修改
properties.put("john", "约翰");
System.out.println("properties=" + properties);
}
}
TreeMap
注意事项：
(1) TreeMap中key不可以为空，但value可以为空
底层机制：
若按照compare方法比较key相同则无法加入value值
public class TreeMap_ {
public static void main(String[] args) {
//使用默认的构造器，创建TreeMap, 是字母排序
/*
要求：按照传入的 k(String) 的大小进行排序
*/
// TreeMap treeMap = new TreeMap();
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//按照传入的 k(String) 的大小进行排序
//按照K(String) 的长度大小排序
//return ((String) o2).compareTo((String) o1);
return ((String) o2).length() - ((String) o1).length();
}
});
treeMap.put("jack", "杰克");
treeMap.put("tom", "汤姆");
treeMap.put("kristina", "克瑞斯提诺");
treeMap.put("smith", "斯密斯");
treeMap.put("hsp", "韩顺平");//加入不了
System.out.println("treemap=" + treeMap);
/*
解读源码：
1. 构造器. 把传入的实现了 Comparator接口的匿名内部类(对象)，传给给TreeMap的comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
2. 调用put方法
2.1 第一次添加, 把k-v 封装到 Entry对象，放入root
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
2.2 以后添加
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do { //遍历所有的key , 给当前key找到适当位置
parent = t;
cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类的compare
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else //如果遍历过程中，发现准备添加Key 和当前已有的Key 相等，就不添加
return t.setValue(value);
} while (t != null);
}
*/
}
}
Collections
常用方法：
-
排序操作：
- reverse (List)：反转List中元素顺序
- shuffle(List)：对 List 集合元素进行随机排序
- sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
- sort(List, Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
- swap (List, int,int)：将指定 list 集合中的 i处元素和j处元素进行交换
-
查找替换：
-
Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
-
Object max(Collection, Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
-
Object min(Collection)
-
Object min(Collection, Comparator)
-
int frequency(Collection, Object)：返回指定集合中指定元素的出现次数
-
void copy(List dest, List src)：将src中的内容复制到dest中
-
boolean replaceAll(List list, Object oldVal, Object newVal)：使用新值替换 List 对象的所有旧值
package test.testCollections; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; @SuppressWarnings({"all"}) public class Test1 { public static void main(String[] args) { ArrayList list = new ArrayList(); list.add("AAA"); list.add("BB"); list.add("DDD"); list.add("CCCCC"); //reverse(List) 反转list中的元素 Collections.reverse(list); System.out.println(list); //shuffle(List) 对List进行随机排序 Collections.shuffle(list); System.out.println(list); //sort(List) 对List进行自然排序(按照字符串进行升序) Collections.sort(list); System.out.println(list); //sort(List,Comparator) Collections.sort(list, new Comparator() { @Override public int compare(Object o1, Object o2) { //按照字符串长度进行排序 return ((String)o1).length() - ((String)o2).length(); } }); System.out.println(list); //swap(List,int,int) 对指定List集合中的i处元素和j处元素进行交换 Collections.swap(list,2,1); System.out.println(list); //Object max(Collection) 根据自然顺序，返回集合中的最大值 System.out.println(Collections.max(list)); //Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素 System.out.println(Collections.max(list, new Comparator() { @Override public int compare(Object o1, Object o2) { //根据字符串长度进行选择 return ((String)o1).length() - ((String)o2).length(); } })); //Object min(Collection) //Object min(Collection，Comparator) //上面的两个方法，参考max即可 //int frequency(Collection，Object)：返回指定集合中指定元素的出现次数 System.out.println(Collections.frequency(list,"AAA")); //void copy(List dest,List src)：将src中的内容复制到dest中 ArrayList dest = new ArrayList(); //为了完成一个完整拷贝，我们需要先给dest 赋值，大小和list.size()一样 for(int i = 0; i < list.size(); i++) { dest.add(""); } //拷贝 Collections.copy(dest, list); System.out.println(dest); //boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值 //如果list中，有AAA 就替换成 AA Collections.replaceAll(list,"AAA","A"); System.out.println(list); } } -
集合选型
选择集合：
-
先判断存储的类型（一组对象[单列]或一组键值对[双列]）
-
一组对象[单列]： Collection接口
-
允许重复：List
增删多：LinkedList [底层维护双向链表]
改查多：ArrayList [底层維护 Object类型的可变数组]
-
不允许重复：Set
无序：HashSet [底层是HashMap，维护了一个哈希表，即(数组＋链表＋红黑树)]
排序：Treeset
插入和取出顺序一致：LinkedHashSet [底层维护数组＋双向链表]
-
-
一组键[值对双列]：Map
- 键无序：HashMap [底层是：哈希表 jdk7：数组＋链表，jdk8:数组＋链表＋红黑树]
- 键排序：TreeMap
- 键插入和取出顺序一致：LinkedHashMap
- 读取文件 Propertie