Java的集合类
转自:Q.Mr的博客
http://www.cnblogs.com/zrtqsk/p/3472258.html
(本人第一次写博客,部分内容有参照李刚老师的疯狂java系列图书,如有遗漏错误,请多指教,谢谢。)
Java的集合类可分为Set、List、Map、Queue,其中Set、List、Queue都有共同的接口:Collection.
所以Collection和Map是Java集合框架的根接口。Java集合实际上并不是真的把对象放入其中,集合中保存的只是对象的引用。
这里首先讲Map,因为所有的Set底层都是由Map实现的,仔细观察API可以发现,Set集合继承体系中所有的接口、实现类的类名,对应的Map集合体系都有。
如:Set-->Map
EnumSet-->EnumMap
SortedSet-->SortedMap
TreeSet-->TreeMap
NavigableSet-->NavigableMap
HashSet-->HashMap
LinkedHashSet-->LinkedHashMap
所不同的是,Map集合体系中还包括IdetityHashMap、WeakHashMap、Hashtable、Properties实现类。
Map集合用于保存具有映射关系的数据,其本质就是一个Object类型的动态数组,数组元素是Map接口的内部类Entry。
内部类Entry封装了一个key-value对。
key和value存在单向的一对一关系,通过指定的key总能找到唯一的确定的value.
由于这个特征,就必须要求Key是不可重复的,符合Set的特征。事实上,Map中所有的key就组成了一个Set集合。
而Value是可以重复的。只能通过key查询value,可以把value看作key的附庸。
一、HashMap 和 Hashtable
Hashtable较为古老,是HashMap的线程安全形式。其中封装了许多古老的方法,与HashMap主要有两点区别:
1、HashMap线程不安全,Hashtable线程安全,所以HashMap性能更好。
而实现线程安全用集合工具类Collections的静态方法synchronizedMap()包装一下,更简单、实用。
2、Hashtable不允许使用null作为key和value,会引发NullPointerException异常,而HashMap允许。
HashMap的底层是数组实现的,其数组元素为一个Entry链表(栈)。
存储过程:根据元素的hashCode()返回值计算元素在数组中的存储索引。根据元素equals方法来计算元素在Entry链表中的存储位置。
若有2个元素hashCode()返回值相同而equals为false,那么发生哈希冲突。新增加的Entry总放在Entry链表栈顶。
HashMap底层数组默认大小为16,这种存储位置又叫做桶(bucket),默认负载极限为0.75,即当HashMap中填满3/4时,
HashMap的容量将自动增加一倍。这个过程中,元素会重新分配,放入新的桶中。这个过程叫做rehashing.