Java集合的基础知识
Java集合的基础知识
Java 集合概述
一方面, 面向对象语言对事物的体现都是以对象的形式,为了方便对多个对象 的操作,就要对对象进行存储。
另一方面,使用Array存储对象方面具有一些弊 端,而Java 集合就像一种容器,可以动态地把多个对象的引用放入容器中。
数组在内存存储方面的特点:
- 数组初始化以后,长度就确定了。
- 数组声明的类型,就决定了进行元素初始化时的类型
数组在存储数据方面的弊端:
- 数组初始化以后,长度就不可变了,不便于扩展
- 数组中提供的属性和方法少,不便于进行添加、删除、插入等操作,且效率不高。 同时无法直接获取 存储元素的个数
- 数组存储的数据是有序的、可以重复的。---->存储数据的特点单一
Java 集合类可以用于存储数量不等的多个对象,还可用于保存具有映射关系的 关联数组。
Java 集合可分为 Collection 和 Map 两种体系
- Collection接口:单列数据,定义了存取一组对象的方法的集合
- List:元素有序、可重复的集合
- Set:元素无序、不可重复的集合
- Map接口:双列数据,保存具有映射关系“key-value对”的集合
Collection接口继承树:
Map接口继承树:
Collection 接口:
Collection 接口方法:
1、添加
- add(Object obj)
- addAll(Collection coll)
2、获取有效元素的个数
- int size()
3、清空集合
- void clear()
4、是否是空集合
- boolean isEmpty()
5、是否包含某个元素 boolean contains(Object obj):是通过元素的equals方法来判断是否 是同一个对象
- boolean containsAll(Collection c):也是调用元素的equals方法来比 较的。拿两个集合的元素挨个比较。
6、删除
- boolean remove(Object obj) :通过元素的equals方法判断是否是 要删除的那个元素。只会删除找到的第一个元素
- boolean removeAll(Collection coll):取当前集合的差集
7、取两个集合的交集
- boolean retainAll(Collection c):把交集的结果存在当前集合中,不 影响c
8、集合是否相等
- boolean equals(Object obj)
9、转成对象数组
- Object[] toArray()
10、获取集合对象的哈希值
- hashCode()
11、遍历
- iterator():返回迭代器对象,用于集合遍历
三种遍历集合元素的方法
- 使用 Iterator 接口遍历集合元素
- 使用 for each 循环遍历集合元素
- 使用普通for循环遍历集合元素
Collection子接口之一:List接口方法
List接口方法:
List除了从Collection集合继承的方法外,List 集合里添加了一些根据索引来 操作集合元素的方法。
- void add(int index, Object ele):在index位置插入ele元素
- boolean addAll(int index, Collection eles):从index位置开始将eles中 的所有元素添加进来
- Object get(int index):获取指定index位置的元素
- int indexOf(Object obj):返回obj在集合中首次出现的位置
- int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
- Object remove(int index):移除指定index位置的元素,并返回此元素
- Object set(int index, Object ele):设置指定index位置的元素为ele
- List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex 位置的子集合
List实现类之一:ArrayList
ArrayList 是 List 接口的典型实现类、主要实现类
本质上,ArrayList是对象引用的一个”变长”数组
ArrayList的JDK1.8之前与之后的实现区别?
JDK1.7:直接创建一个初始容量为10的数组
JDK1.8:一开始创建一个长度为0的数组,当添加第一个元 素时再创建一个始容量为10的数组
List实现类之二:LinkedList
双向链表,内部没有声明数组,而是定义了Node类型的first和last, 用于记录首末元素。对于频繁的插入或删除元素的操作,建议使用LinkedList类,效率较高
List 实现类之三:Vector
Vector 是一个古老的集合,JDK1.0就有了。大多数操作与ArrayList 相同,区别之处在于Vector是线程安全的
请问ArrayList/LinkedList/Vector的异同?谈谈你的理解?ArrayList底层 是什么?扩容机制?Vector和ArrayList的最大区别?
- ArrayList和LinkedList的异同 二者都线程不安全,相对线程安全的Vector,执行效率高。 此外,ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。对于 随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。对于新增 和删除操作add(特指插入)和remove,LinkedList比较占优势,因为ArrayList要移动数据。
- ArrayList和Vector的区别 Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized),属于 强同步类。因此开销就比ArrayList要大,访问要慢。正常情况下,大多数的Java程序员使用 ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大 小的2倍空间,而ArrayList是1.5倍。Vector还有一个子类Stack。
Collection子接口之二:Set接口
Set接口是Collection的子接口,set接口没有提供额外的方法
Set实现类之一:HashSet
- HashSet 是 Set 接口的典型实现,大多数时候使用 Set 集合时都使用这个实现类。
- HashSet 按 Hash 算法来存储集合中的元素,因此具有很好的存取、查找、删除 性能。
HashSet 具有以下特点:
- 不能保证元素的排列顺序
- HashSet 不是线程安全的
- 集合元素可以是 null
HashSet 集合判断两个元素相等的标准: 两个对象通过 hashCode() 方法比较相 等,并且两个对象的 equals() 方法返回值也相等。
对于存放在Set容器中的对象,对应的类一定要重写equals()和hashCode(Object obj)方法,以实现对象相等规则。即:“相等的对象必须具有相等的散列码”。
向HashSet中添加元素的过程:
- 当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法 来得到该对象的 hashCode 值,然后根据 hashCode 值,通过某种散列函数决定该对象 在 HashSet 底层数组中的存储位置。(这个散列函数会与底层数组的长度相计算得到在 数组中的下标,并且这种散列函数计算还尽可能保证能均匀存储元素,越是散列分布, 该散列函数设计的越好)
- 如果两个元素的hashCode()值相等,会再继续调用equals方法,如果equals方法结果 为true,添加失败;如果为false,那么会保存该元素,但是该数组的位置已经有元素了, 那么会通过链表的方式继续链接。
- 如果两个元素的 equals() 方法返回 true,但它们的 hashCode() 返回值不相 等,hashSet 将会把它们存储在不同的位置,但依然可以添加成功。
Set实现类之二:LinkedHashSet - LinkedHashSet 是 HashSet 的子类
- LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置, 但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入 顺序保存的。
- LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set 里的全 部元素时有很好的性能。
- LinkedHashSet 不允许集合元素重复。
Set实现类之三: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 采用自然排序
Map接口概述
- Map与Collection并列存在。用于保存具有映射关系的数据:key-value
- Map 中的 key 和 value 都可以是任何引用类型的数据
- Map 中的 key 用Set来存放,不允许重复,即同一个 Map 对象所对应 的类,须重写hashCode()和equals()方法
- 常用String类作为Map的“键”
- key 和 value 之间存在单向一对一关系,即通过指定的 key 总能找到 唯一的、确定的 value
- Map接口的常用实现类:HashMap、TreeMap、LinkedHashMap和 Properties。其中,HashMap是 Map接口使用频率最高的实现类
Map接口:常用方法
添加、删除、修改操作:
- Object put(Object key,Object value):将指定key-value添加到(或修改)当前map对象中
- void putAll(Map m):将m中的所有key-value对存放到当前map中
- Object remove(Object key):移除指定key的key-value对,并返回value
- void clear():清空当前map中的所有数据
元素查询的操作:
- Object get(Object key):获取指定key对应的value
- boolean containsKey(Object key):是否包含指定的key
- boolean containsValue(Object value):是否包含指定的value
- int size():返回map中key-value对的个数
- boolean isEmpty():判断当前map是否为空
- boolean equals(Object obj):判断当前map和参数对象obj是否相等
元视图操作的方法:
- Set keySet():返回所有key构成的Set集合
- Collection values():返回所有value构成的Collection集合
- Set entrySet():返回所有key-value对构成的Set集合
Map实现类之一:HashMap
- HashMap是 Map 接口使用频率最高的实现类。
- 允许使用null键和null值,与HashSet一样,不保证映射的顺序。
- 所有的key构成的集合是Set:无序的、不可重复的。所以,key所在的类要重写: equals()和hashCode()
- 所有的value构成的集合是Collection:无序的、可以重复的。所以,value所在的类 要重写:equals()
- 一个key-value构成一个entry
- 所有的entry构成的集合是Set:无序的、不可重复的
- HashMap 判断两个 key 相等的标准是:两个 key 通过 equals() 方法返回 true, hashCode 值也相等。
- HashMap 判断两个 value相等的标准是:两个 value 通过 equals() 方法返回 true
HashMap的存储结构
JDK 7及以前版本:HashMap是数组+链表结构(即为链地址法)
JDK 8版本发布以后:HashMap是数组+链表+红黑树实现。
HashMap源码中的重要常量
- DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,16
- MAXIMUM_CAPACITY : HashMap的最大支持容量,2^30
- DEFAULT_LOAD_FACTOR:HashMap的默认加载因子
- TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树
- UNTREEIFY_THRESHOLD:Bucket中红黑树存储的Node小于该默认值,转化为链表
- MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量。(当桶中Node的 数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY时,此时应执行 resize扩容操作这个
- MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4 倍。)
- table:存储元素的数组,总是2的n次幂
- entrySet:存储具体元素的集
- size:HashMap中存储的键值对的数量
- modCount:HashMap扩容和结构改变的次数。
- threshold:扩容的临界值,=容量*填充因子 loadFactor:填充因子
负载因子值的大小,对HashMap有什么影响
- 负载因子的大小决定了HashMap的数据密度。
- 负载因子越大密度越大,发生碰撞的几率越高,数组中的链表越容易长, 造成查询或插入时的比较次数增多,性能会下降。
- 负载因子越小,就越容易触发扩容,数据密度也越小,意味着发生碰撞的 几率越小,数组中的链表也就越短,查询和插入时比较的次数也越小,性 能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能,建 议初始化预设大一点的空间。
- 按照其他语言的参考及研究经验,会考虑将负载因子设置为0.7~0.75,此 时平均检索长度接近于常数。
Map实现类之二:LinkedHashMap
- LinkedHashMap 是 HashMap 的子类
- 在HashMap存储结构的基础上,使用了一对双向链表来记录添加元素的顺序
- 与LinkedHashSet类似,LinkedHashMap 可以维护 Map 的迭代 顺序:迭代顺序与 Key-Value 对的插入顺序一致
Map实现类之三:TreeMap
- TreeMap存储 Key-Value 对时,需要根据 key-value 对进行排序。 TreeMap 可以保证所有的 Key-Value 对处于有序状态。
- TreeSet底层使用红黑树结构存储数据
- TreeMap 的 Key 的排序:
自然排序: TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有 的 Key 应该是同一个类的对象,否则将会抛出 ClasssCastException
定制排序: 创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口 - TreeMap判断两个key相等的标准:两个key通过compareTo()方法或 者compare()方法返回0。
Map实现类之四:Hashtable
- Hashtable是个古老的 Map 实现类,JDK1.0就提供了。不同于HashMap,Hashtable是线程安全的。
- Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询 速度快,很多情况下可以互用。
- 与HashMap不同,Hashtable 不允许使用 null 作为 key 和 value
- 与HashMap一样,Hashtable 也不能保证其中 Key-Value 对的顺序
- Hashtable判断两个key相等、两个value相等的标准,与HashMap一致
Map实现类之五:Properties
- Properties 类是 Hashtable 的子类,该对象用于处理属性文件
- 由于属性文件里的 key、value 都是字符串类型,所以 Properties 里的 key 和 value 都是字符串类型
- 存取数据时,建议使用setProperty(String key,String value)方法和 getProperty(String key)方法
Collections工具类
- Collections 是一个操作 Set、List 和 Map 等集合的工具类
- Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作, 还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
Collections常用方法
排序操作:(均为static方法)
- 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):返回指定集合中指定元素的出现次数
- void copy(List dest,List src):将src中的内容复制到dest中
- boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换 List 对象的所有旧值
Collections常用方法:同步控制
Collections 类中提供了多个 synchronizedXxx() 方法,该方法可使将指定集 合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题