Java集合包
Java集合包
越是憧憬越要风雨兼程 发表于4个月前
Java集合包
  • 发表于 4个月前
  • 阅读 15
  • 收藏 0
  • 点赞 0
  • 评论 0

集合包是java中最常用的包,最常用的有Collection和Map接口的实现类,前者用于存放多个单对象,后者用于存放key-value形式的键值对。

java集合包常用实现类结构图如下所示(I表示接口):

 

 

 

 

 

 

1、ArrayList

动态数组,底层即数组,可以用来容纳任何对象,要求连续存放。ArrayList的重要成员是Object[] elementDate int Size表示有效元素的个数,数组的初始大小是10,扩容操作示意图如下,之前(上面)这块内存变成垃圾。 因此在初始化时尽量指定初始容量,避免扩容产生的内存垃圾,影响性能。

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}// 指定初始化大小

特点及使用注意

(1)foreach中能否对其元素值进行赋值改变?

 不能,高级For在JDK 5.0开始引入,用其迭代代码简洁,在foreach中修改的只是元素的副本,并不会改变原值(反编译之后可发现这一点),所以高级For循环可以用来遍历查询,不可修改当前取回的元素本身。

参考链接:http://me2xp.blog.51cto.com/6716920/1630007/

(2)如何正确遍历并删除ArrayList元素值?

问题背景:给定字符串集合["a","b","b","c"],删除其中元素"b"。

常见错误写法1:

public static void remove(List<String> list) 
	{
		for (int i = 0; i < list.size(); i++) 
		{
			String s = list.get(i);
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}
// 错误的原因:这种最普通的循环写法执行后会发现第二个“b”的字符串没有删掉。

常见错误写法2:

public static void remove(List<String> list) 
	{
		for (String s : list)
		{
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}
// 使用增强的for循环 在循环过程中从List中删除元素以后,继续循环List时会报ConcurrentModificationException,但删除之后马上就跳出的也不会出现异常 

思考及对策

为何和出现错误1,怎么解决?

public boolean remove(Object o) {
		if (o == null) {
			for (int index = 0; index < size; index++)
				if (elementData[index] == null) {
					fastRemove(index);
					return true;
				}
		} else {
			for (int index = 0; index < size; index++)
				if (o.equals(elementData[index])) {
					fastRemove(index);
					return true;
				}
		}
		return false;
	}

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // Let gc do its work
    }

可以看到会执行System.arraycopy方法,导致删除元素时涉及到数组元素的移动。针对错误写法1,在遍历第一个字符串b时因为符合删除条件,所以将该元素从数组中删除,并且将后一个元素移动(也就是第二个字符串b)至当前位置,导致下一次循环遍历时后一个字符串b并没有遍历到,所以无法删除。针对这种情况可以倒序删除的方式来避免:

public static void remove(ArrayList<String> list) 
	{
		for (int i = list.size() - 1; i >= 0; i--) 
		{
			String s = list.get(i);
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}

为何会出现错误2怎么解决?

final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}

这里会做迭代器内部修改次数检查,因为上面的remove(Object)方法修改了modCount的值,所以才会报出并发修改异常。要避免这种情况的出现则在使用迭代器迭代时(显示或for-each的隐式)不要使用ArrayList的remove,改为用Iterator的remove即可:

public static void remove(List<String> list) 
		{
		Iterator<String> it = list.iterator();
		while (it.hasNext()) 
		{
			String s = it.next();
			if (s.equals("b")) 
			{
				it.remove();
			}
		}
}

部分参考:http://swiftlet.net/archives/743; http://elim.iteye.com/blog/1523785

(3)ArrayList非线程安全,如何解决?

Collections给出了解决方案,提供了synchronizedCollection方法,该方法返回一个线程安全容器。

*Java中常用的集合框架中的实现类HashSet、TreeSet、ArrayList、ArrayDeque、LinkedList、HashMap、TreeMap都是线程不安全的,如果有多个线程同时访问它们,且同时有多个线程修改他们的时候,将会出现如读脏数据等错误。Collections给出了解决方案,提供了synchronizedCollection方法来实现线程安全,该方法返回一个线程安全容器。

(4)contains方法

contains()方法是通过将传入的实际参数和集合中已有的元素进行equals()比较来实现的,Object类中的equals()方法比较的是两个对象的地址,因此需要根据实际需要重写equals()方法。
(5)ArrayList、LinkedList、Vector、Stack区别联系

ArrayList和LinkedList是List(线性表)的两种典型实现:基于数组和基于双向链表的线性表。一般而言,由于数组以一块连续内存区来保存所有的数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问时性能都比较好;而内部以链表作为底层实现的集合在执行插入、删除操作时有较好的性能。但总体来说,ArrayList的性能要更好,因此大部分使用时都应该考虑使用ArrayList。

  • 如果需要遍历List集合元素,对于ArrayList和Vector(也是以数组形式存储集合元素的一种集合类型)集合,应该使用随机访问方法(get)来遍历集合元素;对于LinkedList集合,则应该采用迭代器(Iterator)来遍历集合元素。
  • 如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小,可以考虑使用LinkedList集合。使用ArrayList和Vector集合可能需要经常重新分配内部数组的大小,效果较差。
  • 如果有多个线程需要同时访问List集合的元素,开发者可以考虑使用Collections将集合包装成线程安全的集合。

Vector是基于synchronized机制实现的线程安全的ArrayList,但在插入元素容量扩充时机制略有不同,通过传入的capacityIncrement来控制容量的扩充。

Stack继承自Vector,在此基础上实现了栈的弹出以及压入和弹出操作,push、pop、peek(只返回,不出栈)

2、HashMap

底层实现

JDK7实现,数组+链表;JDK8实现,数组+红黑树。

可参考:https://my.oschina.net/hosee/blog/618953

存储过程

当程序试图将一个 key-value 对放入 HashMap 中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部。流程图如下所示:

读取实现

如果 HashMap 的每个 bucket 里只有一个 Entry 时,HashMap 可以根据索引、快速地取出该 bucket 里的 Entry;在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 Hash 算法来决定其存储位置;当需要取出一个 Entry 时,也会根据 Hash 算法找到其存储位置,直接取出该 Entry。

可参考:http://www.liuzk.com/162.html

性能选项

实际容量(capacity):大于initial capacity最小的2的n次方,如10<16

初始容量(initial capacity):可以通过HashMap的构造函数指定

size:变量保存了该 HashMap 中所包含的 key-value 对的数量

threshold:该变量包含了 HashMap 能容纳的 key-value 对的极限,它的值等于 HashMap 的容量乘以负载因子(load factor)

负载因子(load factor):决定了Hash表的最大填满程度

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,程序员无需改变负载因子的值。

3、TreeMap

采用红黑树(https://my.oschina.net/hosee/blog/618828)的数据结构来管理key-value对(红黑树的每个节点就是一个key-value对)

存储key-value对需要根据key排序,排序方式与TreeSet相同(两种排序方式)。

判断两个key相等的标准是:通过compareTo()返回0即认为这两个key相等。

对于自定义类作为key的情况,最好做到:两个key通过equals()方法比较返回true时,compareTo()方法也返回0。

两种排序的比较器:

java.lang.Comparable,TreeMap使用无参构造函数,那么容纳的对象必须实现Comparable接口。

public int compareTo(T o);

java.util.Comparator,TreeSet在构造时使用Comparator作为构造函数的参数。(两种排序方式同时存在时,该方式优先权更高)

int compare(T o1, T o2);

4、HashSet

HashSet的底层实现用到HashMap,HashSet操作的就是HashMap。(Java源码就是先实现HashMap、TreeMap,然后包装一个value为null的Map集合来实现Set集合的)

存储过程

两个对象的equals()方法返回true,但是hashCode值不相等,这时HashSet会把这两个对象存储在Hash表的不同位置,两个对象均可以添加成功,但这会与Set集合的规则相冲突。(这就是不重写相应hashCode()方法的后果,也可阅读参考:http://blog.chinaunix.net/uid-26602509-id-3355659.html)

所以阿里Java规范这样写道:

HashSet如何判断对象是否是相同

——>两个对象通过equals()方法比较相等,并且两个对象的hashCode方法的返回值也相等。

因此需要注意:

当把一个对象放入HashSet中时,如果需要重写此对象对应类的equals()方法,则同时需要重写其hashCode()方法。具体规则是:如果两个对象通过equals()方法比较返回true时,则它们的hashCode值也应该相等(Object规范:相等的对象必须具有相等的hashcode)。

5、TreeSet

底层是TreeMap,集合中的元素处于排序状态。采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方式:自然排序(默认情况)和定制排序。

当把一个对象添加到TreeSet中时,TreeSet会调用该对象的compareTo(Object obj)方法与容器中的其它对象比较大小,然后根据红黑树结构找到它的存储位置。如果compareTo(Object obj)返回0,意味着两个对象相同将无法添加到TreeSet集合中。

附:阿里Java规范-集合

6、List/Set/Map判断对象相同方式的区别

import java.util.*;

class A {
    @Override
    public int hashCode() {
        return UUID.randomUUID().hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

public class Main {

    public static void main(String[] args) throws Exception {
        List<A> list = new ArrayList<>();
        A a1 = new A();
        A a2 = new A();
        list.add(a1);
        // list contains()方法是通过将传入的实际参数和集合中已有的元素进行equals()比较来实现的
        System.out.println(list.contains(a2));
        Map<A, Object> map = new HashMap<>();
        map.put(a1, null);
        System.out.println(map.containsKey(a2));
        Set<A> set = new HashSet<>();
        set.add(a1);
        System.out.println(set.contains(a2));
    }
}
// output:
true
false
false

那么HashSet是如何判断对象是否是相同的呢?

——>两个对象通过equals()方法比较相等,并且两个对象的hashCode方法的返回值也相等。

因此需要注意:

当把一个对象放入HashSet中时,如果需要重写此对象对应类的equals()方法,则同时需要重写其hashCode()方法。具体规则是:如果两个对象通过equals()方法比较返回true时,则它们的hashCode值也应该相等(Object规范:相等的对象必须具有相等的hashcode)。

Map与Set类似,List稍有不同,其contains()方法是通过将传入的实际参数和集合中已有的元素进行equals()比较来实现的,Object类中的equals()方法比较的是两个对象的地址,因此需要根据实际需要重写equals()方法。

 

 

共有 人打赏支持
粉丝 3
博文 32
码字总数 29707
×
越是憧憬越要风雨兼程
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: