2022-10-24T11:09:24
134
原创
重拾java路-集合
集合大家庭 （体系结构图）
集合大类
1 . 单列集合 collection
list ： arraylist Linkedlist vector
collection
set ： hashset treeset
2 .双列集合 Map:
HashMap TreeMap HashTable Properties
3. collections
`
ArrayList (线程不安全，单线程执行效率高)
arrayList的常用方法
ArrayList注意事项：
迭代器
hasNext： 判断是否还有下一个元素
next: 1.下移 2.将下移以后集合位置上的元素返回
List接口和常用方法
list 接口是有序的，（添加顺序和取出顺序一致）
支持索引
常用的有 ArrayList LinkedList 和 vector
常用方法
add
addAll
get
indexOf
lastIndexOf
remove
set
sublist 左闭右开
ArrayList 源码
arrayList源码执行流程
vector（线程安全）
vector 集合注意事项：
Vector源码扩容机制 和 ArrayList 差不多
是2倍扩容
LinkedList （线程不安全，底层双向链表）
模拟简单 双向链表
package dmeo6;
/**
* Created with IntelliJ IDEA.
*
* @Author: 曾豪杰
* @Date: 2022/10/22/15:27
* @Description: 双向链表
*/
public class home {
public static void main(String[] args) {
Node jack = new Node("jack");
Node smith = new Node("smith");
Node bob = new Node("bob");
jack.next=smith;
smith.next=bob;
bob.pre=smith;
smith.pre=jack;
Node firs=jack;//首结点
Node last=bob;//尾结点
//从首到尾 遍历
while (true){
if (firs==null){
break;
}
System.out.println(firs);
firs=firs.next;
}
System.out.println("-------------");
//从尾到首 遍历
while (true){
if (last==null){
break;
}
System.out.println(last);
last=last.pre;
}
//Node{item=jack}
//Node{item=smith}
//Node{item=bob}
//-------------
//Node{item=bob}
//Node{item=smith}
//Node{item=jack}
}
static class Node{
private Object item;
private Node next;
private Node pre;
public Node(Object item) {
this.item = item;
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
'}';
}
}
}
LinkedList源码 debug 双向链表画图一下就明白了
默认是 size=0；
remove（） 的源码 remove（index）的源码
remove（index）：
ArrayList和 LinkedList 的区别
查改 用 arraylist 单线程
增删 用 linkedlist 单线程
多线程用 vector
Set 集合
set 是无序的
set 是不能重复的
set 没有索引
HashSet（实际上是 HashMap (数组+单向链表+红黑树)）
模拟数组+单向链表
/**
* Created with IntelliJ IDEA.
*
* @Author: 曾豪杰
* @Date: 2022/10/22/18:45
* @Description:
*/
public class home {
public static void main(String[] args) {
Node[] table = new Node[16];
//数组加单向链表
table[2] = new Node("jack", new Node("Lucy", new Node("rose", null)));
table[3] = new Node("bob", null);
for (Node node : table) {
System.out.println(node);
}
输出：
//null
//null
//Node{item=jack, next=Node{item=Lucy, next=Node{item=rose, next=null}}}
//Node{item=bob, next=null}
//null
//null
//null
//null
//null
}
static class Node {
private Object item;
private Node next;
public Node(Object item, Node next) {
this.item = item;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
", next=" + next +
'}';
}
}
}
HashSet的扩容机制 (底层是 hash + equals)
如果 数组长度 >64 且 单个链表的长度 >8 就树化，红黑树
添加元素 先得到hash值 转成索引 找到数组表 看此索引是否存在元素 没有 就加入 ，有就 调用equals 相同就不添加，不同加在最后
为什么 add(new String("qwe")); add(new String("qwe")); 只能添加一个？
demo练习：
/**
* Created with IntelliJ IDEA.
*
* @Author: 曾豪杰
* @Date: 2022/10/22/18:23
* @Description:
*/
@SuppressWarnings("all")
public class home {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add(123);
hashSet.add(123);
hashSet.add(456);
hashSet.add(789);
hashSet.add(789);
hashSet.add("sadasdas");
hashSet.add(null);
//只有一个
hashSet.add("qwe");
hashSet.add("qwe");
//两个不同的地址
hashSet.add(new Book("qw"));
hashSet.add(new Book("qw"));
//只有一个（为什么？）
hashSet.add(new String("qwer"));
hashSet.add(new String("qwer"));
System.out.println(hashSet);
}
static class Book{
private String name;
public Book(String name) {
this.name = name;
}
}
}
hashcode的值 不等于哈希值
源码：异或左位移16
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Hashset 底层hashmap add（）源码
结论
2倍扩容机制 0.75预警因子 链表>= 8 数组>=64 转成红黑树
自动扩展 (是size大小，包括链表和数组) 16 32 64 预警 12 24 自己测试过
putVal（）方法
resize（）数组扩容方法 初始默认扩容16 size
add() 第一种情况 添加重复元素（解决了为什么只能 add一个 String的问题了！String的equals重写了obj的可以比较内容）
add（）第二种情况 如果是红黑树 就用putTreeVal来添加
add（）第三种情况 如果上面都不是 ，是链表 就for来比较是否为空 ，为空直接添加到 结点 后面
package com.hspedu.set_;
import java.util.HashSet;
/**
* @author 韩顺平
* @version 1.0
*/
@SuppressWarnings({"all"})
public class HashSetSource {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");//到此位置，第1次add分析完毕.
hashSet.add("php");//到此位置，第2次add分析完毕
hashSet.add("java");
System.out.println("set=" + hashSet);
/*
老韩对HashSet 的源码解读
1. 执行 HashSet()
public HashSet() {
map = new HashMap<>();
}
2. 执行 add()
public boolean add(E e) {//e = "java"
return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
}
3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//key = "java" value = PRESENT 共享
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; //定义了辅助变量
//table 就是 HashMap 的一个数组，类型是 Node[]
//if 语句表示如果当前table 是null, 或者 大小=0
//就是第一次扩容，到16个空间.
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
//并把这个位置的对象，赋给 p
//(2)判断p 是否为null
//(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
Node<K,V> e; K k; //
//如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
//并且满足 下面两个条件之一:
//(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
//(2) p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
//就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判断 p 是不是一颗红黑树,
//如果是一颗红黑树，就调用 putTreeVal , 来进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果table对应索引位置，已经是一个链表, 就使用for循环比较
//(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
// 注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
// 注意，在转成红黑树时，要进行判断, 判断条件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面条件成立，先table扩容.
// 只有上面条件不成立时，才进行转成红黑树
//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break
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
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;
//size 就是我们每加入一个结点Node(k,v,h,next), size++
if (++size > threshold)
resize();//扩容
afterNodeInsertion(evict);
return null;
}
*/
}
}
如果比较的是 对象，重写 hashcode（前提保证hash值一样） 和 equals（重写 让内容也相同）
LinkedHashSet
linkedhashset是 hashset的子类
底层是 数组 + 双向链表
存入顺序 和 遍历顺序 一致（ 与hashset不一样）
双向链表 next pre 加入一个 就改变指向
LinkedHashSet 的源码 是HashSet的子类 差不多 是双向链表 brfore 和 after 指向
通过hashcode 计算 hash值 确定索引
比较 hash值 ，==对象地址 和自己的 equals 方法
before 指向前一个链表
after 指向后一个链表
每次新增都会改变链表
我亦无他，唯手熟而
TreeSet 排序
构造 重写 如果等于0 无法set
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String) o2).compareTo(((String) o1));
}
});
·
//老韩解读源码
//1. 当我们使用无参构造器，创建TreeSet时，仍然是无序的
//2. 老师希望添加的元素，按照字符串大小来排序
//3. 使用TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)
// 并指定排序规则
//4. 简单看看源码
//老韩解读
/*
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);
}
*/
// 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
Map接口
相同key 后者 覆盖 前者
key 为null 只能 有一个
demo：
特点： 中间有了 EntrySet集合（set，collection）指向的table数据地址 提供了遍历方法 里面存放 Entry<k，v>
流程
demo测验:
Map常用方法
Map6种遍历 keySet（通过key获取），values（获取值），EntrySet（获取key 和 值）
/**
* Created with IntelliJ IDEA.
*
* @Author: 曾豪杰
* @Date: 2022/10/23/14:59
* @Description: map遍历
*/
@SuppressWarnings("all")
public class home {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("小明",1230);
hashMap.put("小张",12300);
hashMap.put("小杰",123456);
//keySet
// 第一种遍历 增强for keySet
Set set = hashMap.keySet();
for (Object o : set) {
System.out.println("key:"+o);
}
System.out.println("----------------");
// 第二种遍历 迭代器for keySet
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println("key:"+next);
}
System.out.println("----------------");
//values
// 第一种遍历 增强for values
Collection values = hashMap.values();
for (Object o : values) {
System.out.println("key:"+o);
}
System.out.println("----------------");
// 第二种遍历 迭代器for values
Iterator iterators = values.iterator();
while (iterators.hasNext()) {
Object next = iterators.next();
System.out.println("key:"+next);
}
System.out.println("----------------");
//EntrySet
// 1
Set sets = hashMap.entrySet();
for (Object o : sets) {
Map.Entry entry=(Map.Entry) o;
System.out.println("key:"+entry.getKey()+"-"+"values:"+entry.getValue());
}
System.out.println("----------------");
// 2
Iterator iterator1 = sets.iterator();
while (iterator1.hasNext()) {
Object next = iterator1.next();
Map.Entry entry=(Map.Entry) next;
System.out.println("key:"+entry.getKey()+"-"+"values:"+entry.getValue());
}
System.out.println("----------------");
}
HashMap小总结
HashMap（线程不安全 初始16）源码
执行流程
源码和HashSet前面一致，提出关于树化
HashTable（线程安全 初始11 扩容机制*2+1）
默认初始11 加载因子0.75
public Hashtable() {
this(11, 0.75f);
}
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {不能为空 否则抛出异常
throw new NullPointerException();
}
计算索引值通过hash值
int index = (hash & 0x7FFFFFFF) % tab.length;
HashMap和Hashtable的区别
Properties 继承与 Hashtable ，一般是配置文件使用
TreeMap 排序
和Treeset一样 不过 put 会覆盖前面
集合的选择规则和差异
Collections 集合工具类
常用方法
reverse 反转
shuffle 随机排序
sort 升序
sort(arrayList, new Comparator() 自定义排序
swap 字符串交换
max 最大数 String的 comperTo（）方法
max(arrayList, new Comparator() 自定义
min（）
min(arrayList, new Comparator()
frequency(arrayList,"z")) 出现的次数
copy(arrayList1,arrayList); 必须 size相同不是空间
replaceAll(arrayList1,"z","杰克"); 替换
demo练习：
Treeset 和 Hashset的去重机制
hashset ： hash值和 equals
treeset ： compareable 的 compareto方法
ArrayList和Vector的比较
arraylist 初始10 1.5倍
vector 初始10 2倍
ArrayList和LinkedList的比较
HashTable和HashMap的比较
小结：
ArrayList: 初始10 ，1.5倍 线程不安全 底层 数组 查改
vector: 初始10 2倍 线程安全 底层数组
LinkedList: 底层双向链表 线程不安全 增删
HashSet: 底层 数组+链表+红黑树 0.75加载因子 hash和equals 无序 不重复 数化 链表>8 数组>64 线程不安全
LinkedHashSet:底层 数组+双向链表 有序
TreeSet:排序 compareable接口 的compareTo方法
HashMap：entry 键值对 数组+链表+红黑树 线程不安全
HashTable：线程安全 数组+链表+红黑树
properties：配置文件 继承与hashtable
LinkedHashMap: 双向链表
TreeMap:排序
学校
总结
经验
评论