Java集合框架部分细节总结二
Set
实现类:HashSet,TreeSet
HashSet
基于HashCode计算元素存放位置,当计算得出哈希码相同时,会调用equals判断是否相同,相同则拒绝存入
存储结构:哈希表(数组+链表+红黑树(JDK1.8之后))
即数组上每个元素可追加链表,若HashCode判断相同,而equals判断不同,则会在数组该位置追加Node。超过一定规模,链表转为红黑树存储结构
public static void main(String[] args) {
Set<Student> set = new HashSet<>();
Student s1 = new Student("xiaomign",11);
Student s2 = new Student("xiaohong",12);
Student s3 = new Student("xiaolan",13);
set.add(s1);
set.add(s2);
set.add(s3);
set.add(new Student("xiaolan",13));
System.out.println(set.size());
System.out.println(set);
}
会输出4个Student实例,之所以出现4个,是因为equals判断不相同(是两个地址),重写equals可判断重复
存储过程
- 根据HashCode计算保存位置,若为空,直接包存,否则执行第二步
- 执行equals,若返回true,则认为重复,否则存入(形成链表)
ArrayList实验中曾重写Student,详情可见”ArrayList“
Set<Student> set = new HashSet<>();
Student s1 = new Student("xiaomign",11);
Student s2 = new Student("xiaohong",12);
Student s3 = new Student("xiaolan",13);
set.add(s1);
set.add(s2);
set.add(s3);
set.add(new Student("xiaolan", 13));
若不改动重写代码,则该段执行,出现4个元素,原因在于第一步判断不为空
想让第一步判断为空,需要重写hashCode(),例:
@Override
public int hashCode() {
int n1 = this.name.hashCode();
int n2 = age;
return n1+n2;
}
重写一二步判断后,则集合中为3个元素
alt+insert可直接调用工具,以下为IDEA自动重写代码
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Student)) return false;
Student student = (Student) o;
return getAge() == student.getAge() &&
Objects.equals(getName(), student.getName());
}
@Override
public int hashCode() {
return Objects.hash(getName(), getAge());
}
遍历:增强for,迭代器
PS:
有些版本的重写hashCode()
执行原理是,定义一个Int(31),质数减少散列冲突;提高执行效率:31*i == (i<<5)-i 取31,内部可以进行移位操作
TreeSet
基于排列顺序实现元素不重复
实现SortedSet接口,对集合元素自动排序
元素对象的类型必须实现Comparable接口,指定排序规则,通过CompareTo方法确定是否为重复元素
TreeSet的存储结构为红黑树,红黑树结构即为二叉查找树,数据结构与算法后续将介绍
TreeSet<Student> treeSet = new TreeSet<>();
Student s1 = new Student("xiaomign",11);
Student s2 = new Student("xiaohong",12);
Student s3 = new Student("xiaolan",13);
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
举例一段代码,该段代码不能执行
Student cannot be cast to class java.lang.Comparable
使用TreeSet必须要求元素能够实现Comparable接口,Student类实现Comparable接口里重写CompareTo()
@Override
public int compareTo(Student o) {
int n1 = getName().compareTo(o.getName());
int n2 = getAge()-o.getAge();
return n1==0?n2:n1;
}
该重写的比较规则,先比姓名再比年龄,重写后已能删除,总结:只要实现了比较方式,无论重写哈希还是compareTo都可实现删除等操作。
Comparator接口:实现定制比较(比较器)
实现:
TreeSet<Person> people = new TreeSet<>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
int n1 = o1.getName().compareTo(o2.getName());
int n2 = o1.getAge()-o2.getAge();
return n1==0?n2:n1;
}
});
在实例化过程中直接定义比较器,不需要在Person类中实现Comparable
Map
实现类:HashMap,TreeMap,Hashtable(JDK1.0,目前基本不用了)
特点:存储任意键值对(Key-Value),类似python字典
- Key:无序,无下标,不允许重复(key的判定实际上还是equals和hashCode)
- Value:无序,无下标,允许重复
HashMap
JDK1.2,线程不安全,运行效率快,允许用null作为K或V,构造一个具有默认初始容量16(int)和默认加载因子0.75(float)的空HashMap
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashMap<String,Integer> hashMap = new HashMap<>();
刚创建的时候hashMap=null, size=0;添加第一个元素之后,才赋值默认初始容量;节省空间
当Size超过加载因子规定的容量,第一轮为Size>12时,容量扩展为2倍,newCap为oldCap向左移位了一位
JDK1.8,当链表长度大于8,且Size大于等于64时,链表调整为红黑树,目的是提高执行效率。当链表长度小于6时,调整为链表结构。JDK1.8以前链表是头插入,1.8及以后是尾插入
存储结构:哈希表
遍历方式 entrySet() 返回值类型<K,V>
//增强for
for(Object ob:hashMap.keySet()){
System.out.println(ob+hashMap.get(ob).toString());
}
for(Map.Entry<String,Integer> entry :hashMap.entrySet()) {
System.out.println(entry);
}
同一Key的map中,add之后会覆盖前一个的Value
Hashtable:线程安全,运行效率慢,不允许null作为K或V(初始容量11,加载因子0.75)
Properties:Hashtable的子类,要求K和V均为String,经常用于配置文件的读取(后续会写,涉及流的概念)
Treemap
实现了SortedMap接口(Map子接口),可以对key自动排序
排序过程和TreeSet类似,要满足Comparable接口,两种重写比较方法
遍历方法同HashMap
Collections工具类
常用的有
public static void reverse(List<?>list); //反转集合中元素顺序
public static void shuffle(List<?>list); //随机重置集合中元素顺序
public static void sort(List<T>list); //升序排列(元素类型必须实现Comparable接口)
举例:
Collections.sort(list);
System.out.println(list);
int i =Collections.binarySearch(list,20);
System.out.println(i);//负数则为未找到
注意:
Collections.copy(list1,list);
System.out.println(list1);
copy方法要求两个List大小相同,若list1为刚实例化,则size为0;而list若有元素,size必不为0;无法完成copy
for(int j=0 ; j < list.size() ; j++)
list1.add(0);
解决方法如上,本demo中list1和list均为Integer类型
Integer[]n = list.toArray(new Integer[0]);
for(Object ob:n){
System.out.println(ob);
}
.toArray方法,参数为 T[ ],上述代码若new Integer的大小大于list的大小,则空白处为null,因为Integer为引用类型,默认为null
String[] name = {"apple","pear","banana"};
List<String> list2 = Arrays.asList(name);
System.out.println(list2);
上述为Arrays工具类,与toArray类似,该例中list2不能改动,是一个受限集合
Integer[] num = {1,2,3,4};
List<Integer> list3 = Arrays.asList(num);
System.out.println(list3);
整数数组转List建议这样写,因为int[]之后,下方的泛型也需要使用 int[],这样的话,list中存储的每个元素都是一个数组
基本总结就是这样了,在将来上述有些知识会陆续补充或放在新的博客里,本博客只显示了集合框架中的大概。