集合框架
单列集合:
双列集合:
集合和数组的区别
长度:数组固定长度
内容:集合只能是引用类型
元素:数组只能存储同一类型
Collection接口
实现类有些可以重复,有些有序,没有直接实现,而是子接口
//常用方法
list.add(true)//可以添加不同类型
.remove(true)//可以按索引也可以直接删除某个元素
.contains(obj)
.size()
.isEmpty()
.clear()
.addAll(list2)
.containsAll(list2)
.removeAll(list2);//删除多个元素
List接口
元素按索引有序,可以重复
//常用方法
List list = new ArrayList();
list.add(obj)
.add(index, obj)
.addAll(index, Collection eles)//索引位置插入集合
.get(index)
.indexOf(obj)//首次出现的位置
.lastIndexOf(obj)
.remove(index)
.set(index, obj)
.subList(fromIndex, toIndex);//获取下标[fromIndex, toIndex)的子集合
ArrayList
可以存null,底层是可变数组实现,基本等同于Vector,线程不安全,效率高,适合单线程。
底层机制:
transient Object[] elementData;//transient表示瞬间,该属性不会被序列化
扩容机制:
//构造器
new ArrayList();//无参,初始容量为0,空数组{},第一次添加扩容为10,再次扩容则扩容为1.5倍
new ArrayList(size);//指定大小,初始容量为指定大小,后续扩容为1.5倍
Vector
线程同步,即线程安全,synchronized
LinkedList
底层维护了一个双向链表和双端队列,线程不安全。
添加和删除不是通过数组完成的,相对来说效率高。
集合选择
改查操作多,选择ArrayList(大部分情况选择ArrayList)
增删较多,选择LinkedList
多线程选择Vector
Set接口
无索引存放无序(但取出顺序固定),不可重复,所以最多一个null
遍历:
Set set = new HashSet();
set.add();
//遍历
//1、迭代器
while(set.iterator().hasNext()) {iterator.next()}
//2、增强for
for(Object obj : set) {}
//无get方法
HashSet
1、实现了Set接口,底层实际上是HashMap,源码
public HashSet() {
map = new HashMap<>();
}
2、可以存放一个null
3、不保证存放元素的顺序和取出顺序一致
4、元素不重复(不能加入相同元素)
执行add方法后会返回一个布尔值
经典面试题:
set.add(new String("123"));
set.add(new String("123"));//能重复加入吗?
//不能,因为add方法底层
底层原因:
HashMap底层是数组+链表(+红黑树)
结点存储数据和下一个结点的引用,结点数组称为表,结点形成链表,链表到达一定长度,则链表形成红黑树,提高存储效率。
所以要让两个属性值相同(或部分属性值相同)的对象只存入一个,则重写hashCode方法
@Override
public int hashCode() {
return Objects.hash(Object... values);//hash()源码涉及到“31*任意数是最少重复”
}
LinkedHashSet
继承HashSet
底层是一个LinkedHashMap,底层维护了一个数组+双向链表
因为使用双向链表维护了元素的次序,所以使元素看起来是以插入顺序保存的
效率不如HashSet,但是有序了
TreeSet
区分于HashSet的最大特点:可以排序
使用无参构造器创建TreeSet时,仍然是无序的。
构造器中传入一个比较器,可以指定排序规则,实现在添加元素时按排序规则进行添加。
TreeSet treeSet = new TreeSet(new Comparator() {
@0verride
public int compare(Object o1, Object o2) {
//下面调用String的compareTo方法进行字符串大小比较,实现从小到大排序
return ((String) o1).compareTo((String) o2);//大小相同时不会添加
//长度相同时不会添加
return ((String) o1).length() - ((String) o2).length();
}
});
Map接口
保存key-value键值对,单向一对一对应,key和value可以是任何引用类型。
key不允许重复,key可以为null,常用String类作为key,key是按照hash值来的,key相同时会采用替换策略。
HashSet底层也是键值对,但是值都为private static final Object PRESENT = new Object();
//常用方法
map.put()
.remove()
.get()
.size()
.isEmpty()
.clear()
.containsKey();
遍历:
//1、(最简单)取出所有key,通过key取出对应的value
Map map = new HashMap();
Set keySet = map.keySet();
for(Object key : keySet) {
key;
map.get(key);
}
//2、迭代器
Object key = map.keySet().iterator().next();
map.get(key);
//3、把所有的value取出,遍历values
Collection values = map.values();
for(){}
//4、通过EntrySet
Set entrySet = map.entrySet();
for(Object entry : entrySet) {
//将entry(类型为Node)向下转型转成Map.Entry
Map.Entry m = (Map.Entry) entry;
m.getKey();
m.getValue();
}
HashMap
线程不安全,无序(Hash表),底层是Node类型的数组table+链表(+红黑树),链表结点是HashMap.Node,Node实现了Map.Entry接口。链表长度>8,且table数组达到64,链表就会树化。
底层机制解读:
1、Map存放数据的一对key-value是放在一个HashMap的内部类Node中的。
2、为了方便遍历,还会创建HashMap.EntrySet集合,该集合存放的元素的类型为Map.Entry,而Entry这个数据类型包含key,value。
3、entrySet中的Entry实际上还是HashMap.Node,因为Node<K,V>实现了Entry<K,V>(多态)。即HashMap.Node对象转换成Map.Entry存放到entrySet(地址指向)中,而Map.Entry中提供了getKey()和getValue()方法,故方便程序员对其进行遍历。
扩容机制(和HashSet相同):
1、创建对象时,将加载因子LoadFactor初始化为0.75。
2、添加key-value时,通过key的哈希值得到数组table的索引,然后判断索引处是否有元素。如果没有元素则直接添加,有元素则继续判断两元素的key是否相等。如果相等则直接替换value,不相等则需要判断是树结构还是链表结构,做出相应处理。如果链表添加时发现容量不够,则需要对table和链表同时进行扩容。
3、第一次添加,扩容table容量为16,临界值threshold为16*LoadFactor=12
4、以后再扩容,则需要扩容table容量为原来的2倍(32),临界值为原来的2倍(24),依此类推。
5、在Java8(JDK8)中,若一条链表的元素个数超过TREEIFY_THRESHOLD(默认为8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认64),就会进行树化。
例:同一hash的key添加到第9个会发生第一次扩容,table容量扩容为32,添加到第10个会发生第二次扩容,table容量扩容为64,添加到第11个就会树化,HashMap$Node变成HashMap$TreeNode。不同Hash的key添加到12(16*LoadFactor)个,则table扩容到32;添加到24(32x0.75)个,则table扩容到64。
Hashtable
key和value都不能为null,否则会抛出空指针异常。线程安全synchronized,较于HashMap效率较低
扩容机制:
1、底层有Hashtable$Entry[]数组,初始大小为11。
2、数组大小超过临界值threshold = 8,则大小newCapacity扩容为(oldCapacity << 1) + 1。
TreeMap
TreeMap treeMap = new TreeMap(new Comparator() {
@0verride
public int compare(Object o1, Object o2) {
//下面调用String的compareTo方法进行字符串大小比较,实现从小到大排序
return ((String) o1).compareTo((String) o2);//大小相同时不会添加
//从短到长排序,长度相同时不会添加
return ((String) o1).length() - ((String) o2).length();
}
});
treeMap.put("", "");
集合的选择
一组对象【单列】:Collection接口
允许重复:List
增删多:LinkedList(双向链表)
改查多:ArrayList(可变数组)
不允许重复:Set
无序:HashSet(HashMap)
排序:TreeSet
插入和取出顺序一致:LinkedHashSet [LinkedHashMap[HashMap]](数组+双向链表)
一组键值对【双列】:Map接口
键无序:HashMap(数组+链表+红黑树)
键排序:TreeMap
键插入和取出顺序一致:LinkedHashMap
Collections工具类
是一个操作Set、List和Map等集合的工具类。
提供了一系列静态的方法对集合元素进行排序、查询和修改的操作。
//常用静态方法
Collections.reverse(list)
.shuffle(list)//打乱顺序,随机排序
.sort(list)//自然排序(首字母最大)
.sort(list, new comparator() {//指定顺序排序
@0verride
public int compare(Object o1, Object o2) {
if(o1 instanceOf String) {
return ((String) o1).length() - ((String) o2).length();
}
}
})
.swap(list, index1, index2)//指定下标元素交换
.max(list)//自然顺序最大值
.max(list, comparator)
.min(list).min(list, comparator)
.frequency(list, object)//元素出现的频率
.copy(destList, srcList)//srcList中的内容复制到destList,注意要求集合大小相同
.replaceAll(list, oldValue, newValue);//新值替换旧值(所有符合的)
标签:Java,HashMap,Object,list,链表,key,集合,String
From: https://www.cnblogs.com/fallorange/p/17694461.html