JAVA中集合框架的知识点总结

时间:2022-09-03 16:13:26

题外话

  记得原来在学校的时候,大二选修了JAVA这门课,老师只教到多态继承就闪人了,不去评论他是否敬业。后期自己不断摸索,对JAVA的掌握还好能在简历上写下“熟悉”二字。本以为,不会再去写这样基础的博客了,但是想想后面要走的路还有很长很长,不能在摸索的过程中忘记来时的路,必须有深刻的理解。还是那句话,温故而知新,愿每一次的回眸,都会有不一样的收获

  再说一点。不要去为了面试而去学习。在百度or谷歌的搜索框,打下HashMap,百分之九十的概率,出现“hashmap和hashtable的区别”这类的问题,在搜索框打下String,连StringBuffer都不用打全,就会出现“stringbuffer 和stringbuilder”这样类似的推送,在搜索框打下TCP,基本上就是“什么是三次握手,四次挥手”之类的...等等,这样的例子很多,因为这些都是常见的面试题,虽说应付面试有应付面试的一套,但是你必须永远清楚明白一点 --  学习是日积月累的,技术是需要积淀的!计算机科学技术发展了这么多年,技术的点涵盖是非常广阔的,你可能穷尽一生的去学习,这必须是自主的,出于内心对技术的热爱,去追求,才能成为一名优秀的程序员!愿你我共勉!

  目前这篇博客里主要是一些知识点的总结,基本上没有示例代码,后期会陆续补上~

基本概念

  在JAVA的名著——《Thinking in Java》中,描述集合框架是在第十一章,持有对象,更为深入的介绍在十七章。如果一个程序只包含固定数量的且其生命期都是已知的对象,那么这是一个非常简单的程序。往往在开发的过程中,我们并不能确定,这个程序会创建多少个对象,所在在对对象的存储过程中,我们无法用一个固定长度的容器(如数组)去存储它。Java中有多种保存对象的方式,数组是一种方式,他是编译器支持的类型,但是他的长度是固定的,所以很多时候并不可取。所以这也是为什么我们要学习集合框架,JAVA中的容器类。

  Java容器类类库的用途是“保存对象”,并将其划分为两个不同的概念:

(1)Collection。一个独立元素的序列,这些元素都服从一条或多条规则。List必须按照插入的顺序保存元素,而Set不能有重复元素。Queue按照排队规则来确定对象产生的顺序。

(2)Map。一组成对的“键值对”对象,允许你使用键来查找值。映射表让我们能够使用一个对象来查找另一个对象,就像“字典”一样。Map是强大的编程工具。


Map接口和Collection接口的不同

  • Map是双列的,Collection是单列的
  • Map的键唯一,Collection的子体系Set是唯一的
  • Map集合的数据结构值针对键有效,跟值无关

   Collection集合的数据结构是针对元素有效

Collection

JAVA中集合框架的知识点总结


collection接口的成员方法

boolean add(E e)
boolean remove(Object o)
void clear()
boolean contains(Object o)
boolean isEmpty()
int size()

boolean addAll(Collection c)
boolean removeAll(Collection c)
boolean containsAll(Collection c)
boolean retainAll(Collection c)

Object[] toArray()
把集合转成数组,可以实现集合的遍历

Iterator iterator()
迭代器,集合的专用遍历方式


谈到迭代器,这是个很有意思的东西iterator是我最喜欢的设计模式,虽然用的不多,但是就是莫名的喜爱。迭代器的设计思想,不暴露具体如何遍历这些结合,而提供一个相同的访问方法去遍历这些集合,专业点的描述:迭代器是一个对象,它的工作是遍历并选择序列中的对象,而客户端程序员不必知道或关心该序列底层的结构。有兴趣的朋友可以去研究一下,学习完集合框架,尝试自己看一下JDK的实现源码,然后自己模拟实现一下ArrayList、LinkedList等,在模拟的过程中,你会发现迭代器的有趣之处。曾经我就是这么探索JAVA中的数据结构,非常的有趣。此外,迭代器通常被称为轻量级对象:创建它的代价小。因此会有一些限制:如Iterator只能单向移动

  • 使用方法iterator()要求容器返回一个Iterator
  • boolean hasNext() 检查是否有下一个元素
  • E next() 获取下一个元素
  • remove() 将迭代器新近返回的元素删除


List

  • ArrayList(开发中用的很多)
  1. 底层数据结构是一个自增长的数组,查询快,增删慢
  2. 线程不安全,效率高

  • Vector
  1. 底层数据结构是也是数组,查询快,增删慢
  2. 线程安全,效率低
  3. Vector类特有功能:
      public void addElement(E obj)
      public E elementAt(int index)
      public Enumeration elements()
  • LinkedList
  1. 底层数据结构是链表(存储地址不连续),查询慢,增删快
  2. 线程不安全,效率高
  3. LinkedList类特有功能

        public void addFirst(E e)及addLast(E e)
        public E getFirst()及getLast()
        public E removeFirst()及public E removeLast()


Set


Set是一个不包含重复元素的 collection。Set中最常被使用的是测试归属性,你可以很容易的查询某个对象是否在其中。正因如此,查找成了set中的重要操作,因此你通常都会选择一个HashSet实现,它专门进行了优化。

Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像List一样有不同的list。实际上Set就是Collection,只是行为不同。加入Set的元素必须定义equals方法以确保对象的唯一性


  • HashSet:为快速查而设计的Set。存入HashSet的元素必须定义hashCode()不保证set的迭代顺序,特别是它不保证该顺序恒久不变。
    1. HashSet如何保证元素唯一性?
    • 底层数据结构是哈希表(元素是链表的数组)
    • 哈希表依赖于哈希值存储
    • 添加功能底层依赖两个方法:
                  int hashCode()
                  boolean equals(Object obj)


  • LinkedHashSet:具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。元素也必须定义hashCode()方法
  1. 元素有序唯一
  2. 由链表保证元素有序
  3. 由哈希表保证元素唯一



  • TreeSet:保持次序的set,底层为树结构。使用它可以从set中提取有序的序列。元素必须实现Comparable接口。
  1. 使用元素的自然顺序对元素进行排序
  2. 或者根据创建 set 时提供的 Comparator 进行排序
  3. 具体取决于使用的构造方法。

  必须提的一点:TreeSet是如何保证元素的排序和唯一性的?

                                         底层数据结构是红黑树(红黑树是一种自平衡的二叉树)!红黑树属于比较复杂的一种数据结构,我也计划着后期写一篇博客专门研究一下TreeSet/TreeMap的源码,有兴趣的朋友我们可以一起探讨。


Map

  Map的思想,映射表(也可以称为关联数组)的基本思想是它维护的键-值(对)关联,因此你可以使用键来查找值。标准的Java类库中包含了Map的集中基本实现类,包括HashMap,TreeMap、LinkedHashMap、WeakHashMap,ConcurrentHashMap、IdentityHashMap。它们都有同样的基本接口Map,但是行为特效各不同,这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面。Map接口实现的数量应该可以让你感觉到这种工具的重要性。


Map接口成员方法:

V put(K key,V value)
V remove(Object key)
void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
boolean isEmpty()
int size()
V get(Object key)
Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()

这里提一下Map的遍历方式吧:

方式1:根据键找值

               获取所有键的集合
               遍历键的集合,获取到每一个键
               根据键找值
(这里应当有代码,这篇博客目前基本上没有代码,最近很忙,后期都会补上)


方式2:根据键值对对象找键和值

               获取所有键值对对象的集合
               遍历键值对对象的集合,获取到每一个键值对对象
               根据键值对对象找键和值



  • HashMap:Map基于散列表的实现(它取代 了Hashtable)。插入和查询“键值对”的开销是固定的。可以通过构造器设置容器和负载因子,以调整容器的性能。
  • LinkedHashMap:类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是其插入次序,或者是最近最少使用的(LRU)的次序。只是比HashMap慢一点,而在迭代访问时,反而更快,因为它使用链表维护内部次序。
  • TreeMap:基于红黑树的实现,查看“键”或“键值对”时,它们会被排序(次序由Comparable或Comparator决定)。TreeMap的特点在干,所得到的结果是经过排序的。TreeMap是唯一带有subMap()方法的Map,它可以返回一个子树
  • WeakHashMap:弱键(weak key)映射,允许释放映射所指向的对象,这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”,则此键可以被垃圾回收器回收。
  • ConcurrentHashMap:一种线程安全的Map,它不涉及加同步锁。
  • IdentityHashMap:使用==代替equals()对“键”进行比较的散列映射。专为解决特殊问题而设计的。


既然谈到了HashMap那么就来总结一下与Hashtable的不同,最直观的方法,看其底层实现的源码(这里就不贴源码了)。

1.它们的家族就不同,虽然都实现了Map接口,但HashMap是继承自AbstractMap,Hashtable继承自古老的Dictionary

2.HashMap是允许key为null的,而Hashtbale是不允许的

3.在Hashtable的源码里,一眼我们就能看到一个关键字 -----synchronized ,所以其是线程同步的,HashMap不是线程同步的,所以效率会高上一些


简而言之,HashMap是Hashtable的轻量级实现(非线程安全实现)

最大的不同是,Hashtable的方法是Synchronize的,而HashMap不是,在多个线程访问Hashtable时,不需要自己为它的方法实现同步,而HashMap 就必须为之提供外同步(Collections.synchronizedMap)。