集合的框架体系
本节课学习的目标：彻底搞明白集合的通用框架体系，以不变应万变。能够分清楚一个集合类型的应用与区别。
首先明白collection和map的区别，collection接口时单列集合，Map接口是双列集合
Collection
Collection的遍历
可以使用Iterator迭代器来遍历Collection集合中的元素，且此迭代器本身并不存放对象。（快捷键：itit）
也可以使用增强for循环来进行遍历（快捷键：iter）
ArrayList arrayList = new ArrayList();
arrayList.add("西游记");
arrayList.add("三国演义");
arrayList.add("水浒传");
arrayList.add("红楼梦");
//使用迭代器遍历列表,再次遍历就需要重置迭代器
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println("obj="+ next);
}
//使用增强for循环来遍历列表
for (Object o : arrayList) {
System.out.println("obj=" + o);
}
list(有序)
List接口的特征
- 有序（添加顺序和取出顺序一致，可重复，可以根据索引进行增删改查）
- 可索引
- 可重复
ArrayList底层代码分析
这些是通过底层代码得出的，一定要分清楚
Vector底层代码分析
Vector中有两个值得注意的点：第一是2倍扩容，第二是带有synchronized机制，能够有效实现互斥（保证了线程同步）
LinkedList底层代码分析
与AaaryList和Vector相比，LinkedList链表里的添加和删除，不是通过数组完成的，而是通过节点链表的形式。
//创建一个双向链表
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
//修改节点对象
linkedList.set(1,999);
//遍历节点对象(这里面体现的是一种数据结构的思想）
Iterator iterator = linkedList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println("next=" + next);
}
System.out.println("linkedList=" + linkedList);
ArrayList与Vector的区别
ArrayList与LinkedList的区别
ArrayList和LinkedList的主要区别在于由底层结构不同导致的增删效率不同。
Set
List接口的特征
- 无序（添加顺序和取出顺序不一致，没有索引）
- 没有索引
- 不重复（因为没有索引所以不可重复）
HashSet的底层机制说明（重要）
//1.hashset底层其实就是hashmap，只用了key，只不过是value固定的hashmap
public HashSet() {
map = new HashMap<>();
}
//2.add方法
public boolean add(E e) {//这里的e就是想要加进去的内容，这里的PRESENT是常量
return map.put(e, PRESENT)==null;//如果是添加成功，则为T，否则为F
}
//3.put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//4.核心的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)//这里就是创建这个tab数组用来存放节点
n = (tab = resize()).length;//这里设置了tab数组的大小和临界值
if ((p = tab[i = (n - 1) & hash]) == null)//这里是计算key对应的tab数组的索引，并且得到一个对象p
tab[i] = newNode(hash, key, value, null);//这里吧把hash值存放的原因就是便于比较equals，key就是真正的数据，value是对应present
else {//这个就是对于该节点有数据的判断，是在后面按照链表加入，还是拒绝加入
Node<K,V> e; K k;//在需要的地方创建辅助变量
if (p.hash == hash &&//当前索引位置对应的链表的第一个元素和准备添加的元素hash值相同
((k = p.key) == key || (key != null && key.equals(k))))//准备加入的key和p指向的node节点的key是同一个对象//或者是p指向的节点的key的equals方法和准备加入的key的计算，比较后相同
e = p;//就不能加入
else if (p instanceof TreeNode)//判断p是否是红黑树
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;//增加修改次数
if (++size > threshold)//如果超过12，继续扩容
resize();
afterNodeInsertion(evict);//子类实现
return null;
}
hashset的扩容机制
LinkedHashSet底层机制
就是在hashset上补充了一个双向链表
Map
Map的遍历机制
Entry是Map的内部类，因此可以使用Entry直接转换
Set set = hashMap.entrySet();
for (Object o : set) {
Map.Entry m =(Map.Entry) o;
System.out.println(m.getKey() +"-"+m.getValue());
}
//先取出所有的key列表，其实就是多了一个keyset
Set keyset = hashMap.keySet();
//增强for循环
for (Object key : keyset) {
System.out.println(key+ "-"+ hashMap.get(key));
}
//迭代器
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(key+ "-" +hashMap.get(key));
}
HashMap机制
Hashtable机制
public synchronized V put(K key, V value) {//具有互斥机制，跟hashmap很像
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
Collection中的操作
为什么treeset和treemap可以排序？
TreeSet treeSet = new TreeSet(new Comparator() {//使用Comparator接口来实现有序排序
@Override
public int compare(Object o1, Object o2) {
//下面 调用String的 compareTo方法进行字符串大小比较
//如果老韩要求加入的元素，按照长度大小排序
//return ((String) o2).compareTo((String) o1);
return ((String) o1).length() - ((String) o2).length();
}
});
集合选型
TIPS：HashSet与TreeSet实现去重的机制区别
