数组和集合的比较
数组不是面向对象的,存在明显的缺陷,集合弥补了数组的缺点,比数组更灵活更实用,而且不同的集合框架类可适用不同场合。如下:
- 数组能存放基本数据类型和对象,而集合类存放的都是对象的引用,而非对象本身!
- 数组容易固定无法动态改变,集合类容量动态改变。
- 数组无法判断其中实际存有多少元素,length只告诉了数组的容量,而集合的size()可以确切知道元素的个数
- 集合有多种实现方式和不同适用场合,不像数组仅采用顺序表方式
- 集合以类的形式存在,具有封装、继承、多态等类的特性,通过简单的方法和属性即可实现各种复杂操作,大大提高了软件的开发效率
Java集合
Collection
和Map
,是集合框架的根接口。
- Set集合:内部元素无序,并且元素不可以重复;
- List集合:内部元素有序,且元素可以重复;
- Map集合:具有映射关系的集合
Collection接口:
Collection接口是List,Set和Queue接口的父接口,该接口中定义的方法可以用户操作List,Set和Queue集合;其中主要有以下的一些方法:
List集合
- 扩展Collection接口
- List 代表一个元素有序、且可重复的集合,集合中的每个元素都有其对应的顺序索引
- List 允许使用重复元素,可以通过索引来访问指定位置的集合元素。
- List 默认按元素的添加顺序设置元素的索引。
Arrays.asList(…)
方法返回的 List 集合即不是 ArrayList 实例,也不是 Vector 实例。Arrays.asList(…)
返回值是一个固定长度的 List 集合。- 允许使用null元素
- ArrayList(实现类)
- LinkedList (实现类)
List常用方法:
// 添加对象element到位置index上
void add(int index, Object element)
// 在index位置后添加容器collection中所有的元素
boolean addAll(int index, Collection collection)
// 取出下标为index的位置的元素
Object get(int index)
// 查找对象element 在List中第一次出现的位置
int indexOf(Object element)
// 查找对象element 在List中最后出现的位置
int lastIndexOf(Object element)
// 删除index位置上的元素
Object remove(int index)
// 返回一个ListIterator 跌代器,开始位置为startIndex
ListIterator listIterator(int startIndex)
// 返回一个子列表List ,元素存放为从 fromIndex 到toIndex之前的一个元素
List subList(int fromIndex, int toIndex)
实现类:
- ArrayList:数组实现,查询快,增删慢,轻量级;(线程不安全)
- LinkedList:双向链表实现,增删快,查询慢 (线程不安全)
- Vector:数组实现,重量级 (线程安全、使用少)
ArrayList
底层是Object数组,所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点。
而在LinkedList的底层是一种双向循环链表。在此链表上每一个数据节点都由三部分组成:前指针(指向前面的节点的位置),数据,后指针(指向后面的节点的位置)。最后一个节点的后指针指向第一个节点的前指针,形成一个循环。
双向循环链表的查询效率低但是增删效率高。
ArrayList和LinkedList在用法上没有区别,但是在功能上还是有区别的。
LinkedList
LinkedList是采用双向循环链表实现的。
利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。
它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()等。
经常用在增删操作较多而查询操作很少的情况下:
队列和堆栈。
队列:先进先出的数据结构。
栈 :后进先出的数据结构。
注意:使用栈的时候一定不能提供方法让不是最后一个元素的元素获得出栈的机会。
Vector
(与ArrayList相似,区别是Vector是重量级的组件,使用使消耗的资源比较多。)
结论:在考虑并发的情况下用Vector(保证线程的安全)。
在不考虑并发的情况下用ArrayList(不能保证线程的安全)。
ArrayList自动扩充机制
实现机制:ArrayList.ensureCapacity(int minCapacity)
首先得到当前elementData 属性的长度oldCapacity。
然后通过判断oldCapacity和minCapacity参数谁大来决定是否需要扩容, 如果minCapacity大于
oldCapacity,那么我们就对当前的List对象进行扩容。
扩容的的策略为:取(oldCapacity * 3)/2 + 1和minCapacity之间更大的那个。然后使用数组拷
贝的方法,把以前存放的数据转移到新的数组对象中
如果minCapacity不大于oldCapacity那么就不进行扩容。
用LinkedList实现队列:
队列(Queue)是限定所有的插入只能在表的一端进行,而所有的删除都在表的另一端进行的线性表。
表中允许插入的一端称为队尾(Rear),允许删除的一端称为队头(Front)。
队列的操作是按先进先出(FIFO)的原则进行的。
队列的物理存储可以用顺序存储结构,也可以用链式存储结构。
用LinkedList实现栈:
栈(Stack)也是一种特殊的线性表,是一种后进先出(LIFO)的结构。
栈是限定仅在表尾进行插入和删除运算的线性表,表尾称为栈顶(top),表头称为栈底(bottom)。
栈的物理存储可以用顺序存储结构,也可以用链式存储结构。
Set集合(接口)
- 扩展Collection接口
- 无序集合,不允许存放重复的元素;
- 允许使用null元素
- 对 add()、equals() 和 hashCode() 方法添加了限制
- HashSet (实现类)
- LinkedHashSet(实现类)
- SortedSet接口 – NavigableSet接口
- TreeSet (实现类)
HashSet常用方法:
// 如果set包含指定元素,返回true
public boolean contains(Object o)
// 返回set中元素的迭代器
public Iterator iterator()
// 返回包含set中所有元素的数组
public Object[] toArray()
// 返回包含set中所有元素的数组,返回数组的运行时类型是指定数组的运行时类型
public Object[] toArray(Object[] a)
// 如果set中不存在指定元素,则向set加入
public boolean add(Object o)
// 如果set中存在指定元素,则从set中删除
public boolean remove(Object o)
// 如果set包含指定集合,则从set中删除指定集合的所有元素
public boolean removeAll(Collection c)
// 如果set包含指定集合的所有元素,返回true。如果指定集合也是一个set,只有是当前set的子集时,方法返回true
public boolean containsAll(Collection c)
实现类
- HashSet:equals返回true,hashCode返回相同的整数;哈希表;存储的数据是无序的。
LinkedHashSet:此实现与 HashSet 的不同之外在于,后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。
HashSet类
HashSet类直接实现了Set接口, 其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素,因此具有比较好的读取和查找性能。
HashSet的特征
- 不仅不能保证元素插入的顺序,而且在元素在以后的顺序中也可能变化(这是由HashSet按HashCode存储对象(元素)决定的,对象变化则可能导致HashCode变化)
- HashSet是线程非安全的
- HashSet元素值可以为NULL
实现Set接口的HashSet,依靠HashMap来实现的。
我们应该为要存放到散列表的各个对象定义hashCode()和equals()。
HashSet的equals和HashCode
前面说过,Set集合是不允许重复元素的,否则将会引发各种奇怪的问题。那么HashSet如何判断元素重复呢?
HashSet需要同时通过equals和HashCode来判断两个元素是否相等,具体规则是,如果两个元素通过equals为true,并且两个元素的hashCode相等,则这两个元素相等(即重复)。
所以如果要重写保存在HashSet中的对象的equals方法,也要重写hashCode方法,重写前后hashCode返回的结果相等(即保证保存在同一个位置)。所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。
试想如果重写了equals方法但不重写hashCode方法,即相同equals结果的两个对象将会被HashSet当作两个元素保存起来,这与我们设计HashSet的初衷不符(元素不重复)。
另外如果两个元素哈市Code相等但equals结果不为true,HashSet会将这两个元素保存在同一个位置,并将超过一个的元素以链表方式保存,这将影响HashSet的效率。
如果重写了equals方法但没有重写hashCode方法,则HashSet可能无法正常工作。
如何达到不能存在重复元素的目的?
“键”就是我们要存入的对象,“值”则是一个常量。这样可以确保,我们所需要的存储的信息
之是“键”。而“键”在Map中是不能重复的,这就保证了我们存入Set中的所有的元素都不重复。
HashSet如何过滤重复元素
调用元素HashCode获得哈希码
—>判断哈希码是否相等,不相等则录入
—>相等则判断equals()后是否相等,不相等在进行 hashcode录入,相等不录入
LinkedHashSet的特征
LinkedHashSet是HashSet的一个子类,LinkedHashSet也根据HashCode的值来决定元素的存储位置,但同时它还用一个链表来维护元素的插入顺序,插入的时候即要计算hashCode又要维护链表,而遍历的时候只需要按链表来访问元素。
TreeSet
TreeSet 是 SortedSet 接口的实现类,TreeSet 可以确保集合元素处于排序状态。
其中TreeSet还有以下的一些常用的操作:
- Comparator comparator() // 比较器
- Object first() // 获取第一个元素
- Object last() // 获取最后一个元素
- Object lower(Object e)
- Object higher(Object e)
- SortedSet subSet(fromElement, toElement)
- SortedSet headSet(toElement)
- SortedSet tailSet(fromElement)
TreeSet 支持两种排序方法:自然排序和定制排序。默认情况下,TreeSet 采用自然排序。
1)自然排序
排序:TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序排列,如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable 接口。实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过 compareTo(Object obj) 方法的返回值来比较大小。
public class PersonCompare implements Comparable{
public String name;
public int age;
@Override
public int compareTo(Object o) {
if (o instanceof PersonCompare){
PersonCompare personCompare = (PersonCompare) o;
return this.name.compareTo(personCompare.name);
}else{
throw new ClassCastException("转换类型失败!");
}
}
}
自然排序方法的使用示例:
/**
* 自然排序情况(升序)
*
* 默认情况下TreeSet要求集合中的元素必须实现Comparable接口
* Comparable接口中只有一个方法:
* public int compareTo(T o)
* 如果返回0 代表两个元素相等
* 如果返回正数,代表当前元素大
* 如果返回负数,代表当前元素小
* TreeSet 会调用每个元素的compareTo()方法去和集合中的每个已经有的元素比较,进而决定当前元素在集合中的位置
*
*/
@Test
public void testTreeSet(){
TreeSet treeSet = new TreeSet();
treeSet.add(new PersonCompare("AAA",16));
treeSet.add(new PersonCompare("BBB",13));
treeSet.add(new PersonCompare("CCC",11));
treeSet.add(new PersonCompare("DDD",15));
for (Object o : treeSet) {
System.out.println(o.toString());
}
}
2)定制排序
如果需要实现定制排序,则需要在创建 TreeSet 集合对象时,提供一个 Comparator 接口的实现类对象。由该 Comparator 对象负责集合元素的排序逻辑。定制排序的优点就是让需要排序的对象不需要实现Compareable接口,减少了耦合性,是程序更加简单。
/**
* 定制排序
*
*/
@Test
public void testTreeSet2(){
//创建comparator接口的实现类对象
Comparator comparator = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof Person && o2 instanceof Person){
Person p1 = (Person)o1;
Person p2 = (Person)o2;
return p1.getAge() - p2.getAge();
}
throw new ClassCastException("类型转换异常");
}
};
//创建TreeSet对象,传入Comparator接口的实现类对象
TreeSet treeSet = new TreeSet(comparator);
treeSet.add(new Person("AAA",16));
treeSet.add(new Person("BBB",13));
treeSet.add(new Person("CCC",11));
treeSet.add(new Person("DDD",15));
for (Object person : treeSet) {
System.out.println(person.toString());
}
}
Map集合
概述
- Map 用于保存具有映射关系的数据,因此 Map 集合里保存着两组值,一组值用于保存 Map 里的 Key,另外一组用于保存 Map 里的 Value
- Map 中的 key 和 value 都可以是任何引用类型的数据
- Map 中的 Key 不允许重复,即同一个 Map 对象的任何两个 Key 通过 equals 方法比较中返回 false
- Key 和 Value 之间存在单向一对一关系,即通过指定的 Key 总能找到唯一的,确定的 Value。
常用方法:
Object put(Object key,Object value) // 用来存放一个键-值对Map中
Object remove(Object key) // 根据key(键),移除键-值对,并将值返回
void putAll(Map mapping) // 将另外一个Map中的元素存入当前的Map中
void clear() // 清空当前Map中的元素
Object get(Object key) // 根据key(键)取得对应的值
boolean containsKey(Object key) // 判断Map中是否存在某键(key)
boolean containsValue(Object value)// 判断Map中是否存在某值(value)
public Set keySet() // 返回所有的键(key),并使用Set容器存放
public Collection values() // 返回所有的值(Value),并使用Collection存放
public Set entrySet() // 返回一个实现 Map.Entry 接口的元素 Set
Map.Entry说明
Map是java中的接口,Map.Entry是Map的一个内部接口。
Map提供了一些常用方法,如keySet()、entrySet()等方法,keySet()方法返回值是Map中key值的集合;entrySet()的返回值也是返回一个Set集合,此集合的类型为Map.Entry。
Map.Entry是Map声明的一个内部接口,此接口为泛型,定义为Entry<K,V>。它表示Map中的一个实体(一个key-value对)。接口中有getKey(),getValue()方法。
Map.Entry使用
你是否已经对每次从Map中取得关键字然后再取得相应的值感觉厌倦?使用Map.Entry类,你可以得到在同一时间得到所有的信息。标准的Map访问方法如下:
Set keys = map.keySet();
if(keys != null) {
Iterator iterator = keys.iterator();
while(iterator.hasNext()) {
Object key = iterator.next();
Object value = map.get(key);
;....;
}
}
然后,这个方法有一个问题。从Map中取得关键字之后,我们必须每次重复返回到Map中取得相对的值,这是很繁琐和费时的。
幸运的是,这里有一个更加简单的途径。Map类提供了一个称为entrySet()的方法,这个方法返回一个Map.Entry实例化后的对象集。接着,Map.Entry类提供了一个getKey()方法和一个getValue()方法,因此,上面的代码可以被组织得更符合逻辑。举例如下:
Set entries = map.entrySet();
if(entries != null) {
Iterator iterator = entries.iterator();
while(iterator.hasNext()) {
Map.Entry entry =iterator.next();
Object key = entry.getKey();
Object value = entry.getValue();
;....
}
}
HashMap 和 Hashtable
- HashMap 和 Hashtable 是 Map 接口的两个典型实现类
- 区别:
- Hashtable 是一个古老的 Map 实现类,不建议使用
- Hashtable 是一个线程安全的 Map 实现,但 HashMap 是线程不安全的。
- Hashtable 不允许使用 null 作为 key 和 value,而 HashMap 可以
- 与 HashSet 集合不能保证元素的顺序的顺序一样,Hashtable 、HashMap 也不能保证其中 key-value 对的顺序
- Hashtable 、HashMap 判断两个 Key 相等的标准是:两个 Key 通过 equals 方法返回 true,hashCode 值也相等。
- Hashtable 、HashMap 判断两个 Value相等的标准是:两个 Value 通过 equals 方法返回 true
LinkedHashMap
LinkedHashMap 是 HashMap 的子类
LinkedHashMap 可以维护 Map 的迭代顺序:迭代顺序与 Key-Value 对的插入顺序一致
@Test
public void testLinkedHashMap(){
Map map = new LinkedHashMap<>();
map.put("CC", new Person("CC", 18));
map.put("AA", new Person("AA", 10));
map.put("DD", new Person("DD", 12));
map.put("BB", new Person("BB", 16));
/*Iterator it = map.keySet().iterator();
while (it.hasNext()){
Object key = it.next();
Object value = map.get(key);
System.out.println(key+":"+value);
}
System.out.println();*/
for (Object key : map.keySet()){
Object value = map.get(key);
System.out.println(key+":"+value);
}
}
TreeMap
TreeMap 存储 Key-Value 对时,需要根据 Key 对 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。
TreeMap 的 Key 的排序:
- 自然排序:TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出 ClassCastException
- 定制排序:创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口
同样这里的key值也需要具有可比性
@Test
public void testTreeMap(){
Map map = new TreeMap<>();
//这里使用加入Compareable接口的Person类,这样才可以进行排序
map.put(new PersonCompare("CC", 18),"CC");
map.put(new PersonCompare("AA", 10),"AA");
map.put(new PersonCompare("DD", 12),"DD");
map.put(new PersonCompare("BB", 16),"BB");
for (Object key : map.keySet()){
Object value = map.get(key);
System.out.println(key+":"+value);
}
}
操作集合的工具类:Collections
- Collections 是一个操作 Set、List 和 Map 等集合的工具类
- 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): 返回指定集合中指定元素的出现次数
- boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换 List 对象的所有旧值
同步控制
Collections 类中提供了多个 synchronizedXxx()
方法,该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题
public class CollectionsTest {
@Test
public void testList(){
List list = new ArrayList<>();
list.add(new Person("AAA",16));
list.add(new Person("BBB",13));
list.add(new Person("CCC",11));
list.add(new Person("DDD",15));
for (Object o : list) {
System.out.println(o.toString());
}
//按年龄升序排列
//实现Comparator类进行排序操作
Collections.sort(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof Person && o2 instanceof Person){
Person p1 = (Person)o1;
Person p2 = (Person)o2;
return p1.getAge() - p2.getAge();
}
throw new ClassCastException("类型转换异常");
}
});
System.out.println();
for (Object o : list) {
System.out.println(o.toString());
}
//获取list中最小的元素
//要求集合中的元素都实现Compareable接口
Set set = new HashSet();
set.add(new PersonCompare("AAA",20));
set.add(new PersonCompare("BBB",34));
set.add(new PersonCompare("CCC",27));
set.add(new PersonCompare("DDD",29));
for (Object person : set) {
System.out.println(person.toString());
}
System.out.println();
Object object = Collections.min(set);
System.out.println(object.toString());
}
}
集合遍历
public static void main(String[] args) {
ArrayList<News> list = new ArrayList<News>();
list.add(new News(1,"list1","a"));
list.add(new News(2,"list2","b"));
list.add(new News(3,"list3","c"));
list.add(new News(4,"list4","d"));
//遍历
}
- 增强for循环
for(Object obj:collection){
System.out.println(obj);
}
for (News s : list) {
System.out.println(s.getId()+" "+s.getTitle()+" "+s.getAuthor());
}
- 使用iterator
Iterator it= collection.iterator;
while(it.hasNext()){
Object o = it.next()
}
Iterator iter = list.iterator();
while (iter.hasNext()) {
News s = (News) iter.next();
System.out.println(s.getId()+" "+s.getTitle()+" "+s.getAuthor());
}
- 普通循环
for(Iterator iterator = list.iterator();iterator.hasNext();){
News s = (News) iter.next();
System.out.println(s.getId()+" "+s.getTitle()+" "+s.getAuthor());
}
for (int i = 0; i < list.size(); i++) {
News s = (News)list.get(i);
System.out.println(s.getId()+" "+s.getTitle()+" "+s.getAuthor());
}
面试知识点
- ArrayList: 元素单个,效率高,多用于查询
- Vector: 元素单个,线程安全,多用于查询
- LinkedList:元素单个,多用于插入和删除
- HashMap: 元素成对,元素可为空
- HashTable: 元素成对,线程安全,元素不可为空
HashMap和Hashtable的区别:
HashMap和Hashtable都是java的集合类,都可以用来存放java对象,这是他们的相同点
以下是他们的区别:
1.历史原因:
Hashtable是基于陈旧的Dictionary类的,HashMap是java 1.2引进的Map接口的一个现实。
2.同步性:
Hashtable是同步的,这个类中的一些方法保证了Hashtable中的对象是线程安全的,而HashMap则是异步的,因此HashMap中的对象并不是线程安全的,因为同步的要求会影响执行的效率,所以如果你不需要线程安全的结合那么使用HashMap是一个很好的选择,这样可以避免由于同步带来的不必要的性能开销,从而提高效率,我们一般所编写的程序都是异步的,但如果是服务器端的代码除外。
3.值:
HashMap可以让你将空值作为一个表的条目的key或value
Hashtable是不能放入空值(null)的
ArrayList和Vector的区别:
ArrayList与Vector都是java的集合类,都是用来存放java对象,这是他们的相同点,
区别:
1.同步性:
Vector是同步的,这个类的一些方法保证了Vector中的对象的线程安全的,而ArrayList则是异步的,因此ArrayList中的对象并不 是线程安全的,因为同步要求会影响执行的效率,所以你不需要线程安全的集合那么使用ArrayList是一个很好的选择,这样可以避免由于同步带来的不必 要的性能开销。
2.数据增长:
从内部实现的机制来讲,ArrayList和Vector都是使用数组(Array)来控制集合中的对象,当你向两种类型中增加元素的时候,如果元素的数目超过了内部数组目前的长度他们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大,所以如果你要在集合中保存大量的数据,那么使用Vector有一些优势,因为你可以通过设置集合的初始大小来避免不必要的资源开销。
总结:
- 如果要求线程安全,使用Vector,Hashtable
- 如果不要求线程安全,使用ArrayList,LinkedList,HashMap
- 如果要求键值对,则使用HashMap,Hashtable
- 如果数据量很大,又要求线程安全考虑Vector
arraylist和linkedlist联系与区别
- ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
- 对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
- 对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。 这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。
HashMap与TreeMap联系与区别
- HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。
- 在Map 中插入、删除和定位元素,HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。
- 两个map中的元素一样,但顺序不一样,导致hashCode()不一样。
同样做测试:
在HashMap中,同样的值的map,顺序不同,equals时,false;
而在treeMap中,同样的值的map,顺序不同,equals时,true,说明,treeMap在equals()时是整理了顺序了的。
评论前必须登录!
注册