Java集合

一、接口继承关系和实现

集合类存放于java.util包中,主要有3种:Set、List(包含Queue)、和Map

接口:

1、Collection:是集合List、Set和Queue的主要接口

2、Iterator:迭代器,可以通过迭代器遍历集合中的数据

3、Map:映射表


图1

二、List

List有三个实现类,分别是Vector、ArrayList、LinkedList。

2.1 ArrayList

    ArrayList是最常用的List实现类,内部通过数组实现,它允许对元素进行随机快速访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要将已有数组的数据复制到新的存储空间中。当从ArrayList中间插入或者删除元素时,需要对数组进行复制、移动,代价比较高,因此,它适合随机查找和遍历,不适合插入和删除。ArrayList可以动态调整容量,扩容时容量会增加50%。

2.2 Vector

    Vector和ArrayList一样,也是通过数组实现,不同的是它支持线程同步,即某一时刻只有一个线程可以写数据,但实现同步的代价很高,导致效率比ArrayList低。Vector也可以根据需要扩展容量,当数组已满时,会创建新的数组,容量会扩展一倍,并拷贝原有数据到新的数组。

2.3 LinkedList

    LinkedList 是用双向链表结构存储的数据,很适合数据的动态插入和删除,但随机访问速度比较慢。另外,它还提供了List接口中没有定义的方法,专门用于操作表头和表尾元素,可以当做堆栈、队列和双向队列使用。

三、Map

    Map是以键值对的形式存储和操作数据的容器类型,主要包含Hashtable、HashMap、TreeMap、LinkedHashMap、ConcurrentHashMap等。

3.1 Hashtable

    Hashtable是早期Java类库提供的一个哈希表的实现,本身是同步的,不支持null键和值,由于同步导致的性能开销,所以已经很少被推荐使用。

3.2 HashMap   

    HashMap是应用更加广泛的哈希表实现,行为上大致上与HashTable一致,主要区别在于HashMap不是同步的,支持null键和值等。通常情况下,HashMap进行put或者get操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选。

    HashMap的结构:JAVA7是数组+链表;JAVA8是数组+链表+红黑树

put方法流程:

    1、检查map中的数据Node table[]是否初始化,没有则初始化

    2、根据新增的key的hashcode,获取table[(n-1) & hash]元素,如果为空,直接放入到此位置

    3、如果2上面对应位置的元素不为空,对比新的key.equals(oldKey)是否相等,如果相等,替换就元素的值;如果不相等,判断2中的元素是否是红黑树,如果是,将新元素加入到红黑树结构中,如果不是红黑树结构,将新元素添加到该元素的链表结构中

    4、若链表的长度达到8,转为红黑树结构

    5、当前HashMap的size+1,并检查当前的容量是否超过初始容量和负载因子的乘积,如果超过,扩容

在计算key的hashCode时,用的并不是key本身的hashCode,而是HashMap内部的另外一个hash方法。如下:

    static final int hash(Object kye) {

        int h;

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16;

    }

    为什么这里要将高位数据移位到低位进行异或运算呢?

    这是因为有些数据计算出的哈希值差异主要在高位,而HashMap里的哈希寻址是忽略容量以上的高位的,那么这种处理就可以有效避免类似情况下的哈希碰撞。

    为什么采用红黑树而不是平衡二叉树?

    红黑树的查询性能略逊色于AVL(平衡二叉树)树,因为他比AVL树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较,但是,红黑树在插入和删除上比AVL开销小得多。

    为什么要转成树结构?

    本质上这个是安全问题。在元素放置过程中,如果一个对象哈希冲突,都被放置到同一个桶里,则会形成一个链表,链表查询是线性的,会严重影响存取的性能。而在现实世界,构造哈希冲突的数据并不是非常复杂的事情,恶意代码就可以利用这些数据大量与服务端交互,导致服务器端CPU大量占用,这就构成了哈希碰撞拒绝服务攻击。

3.3 TreeMap

    TreeMap是基于红黑树的一种提供顺序访问的Map,和HashMap不同,它的get、put、remove之类的操作都是O(log(n))的时间复杂度,具体顺序可以由构造函数指定的Comparator来决定,或者根据键的自然顺序来判断,默认按照升序排序。

3.4 LinkedHashMap

    LinkedHashMap 是 HashMap 的一个子类,保存了记录的插入顺序,在用 Iterator 遍历LinkedHashMap 时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

四、Set

    Set注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同),值不能重复。对象的相等性本质是对象的hashCode值(java是根据对象的内存地址计算出的此序号)判断的。如果想要让两个不通的对象视为相等的,就必须覆盖Object的equals和hashCode方法。

4.1 HashSet

    哈希表存放的是哈希值。HashSet存储元素的顺序并不是按照存入时的顺序(和List显然不同)而是按照哈希值来存的,所以取数据也是按照哈希值取得。元素的哈希值是通过元素的hashCode方法来获取的,HashSet首先判断两个元素的哈希值,如果哈希值一样,接着会比较equals方法,如果返回true,HashSet就会判断为同一个元素,如果返回false就不是同一个元素。

    哈希值相同equals返回false的元素的存储方式是在同样的哈希表下以链表形式存储,因为HashSet的实现是以HashMap为基础的。

    特点:提供常数时间的添加、删除、包含等操作,但它不是有序的。

4.2 TreeSet(二叉树)

    TreeSet是使用二叉树的原理对新增的对象按照指定的顺序(升序、降序),每增加一个对象都会进行排序,将对象插入二叉树的指定位置。添加到TreeSet中的对象必须实现Comparable接口并实现compareTo方法,排序是通过调用对象的此方法与待比较对象比较实现的。同样的,TreeSet底层实现是以TreeMap为基础的。

    特点:log(n)时间的添加、删除、包含等操作,有序访问。

4.3 LinkedHashSet(HashSet+LinkedHashMap)

    内部构建了一个记录插入顺序的双向链表,因此提供了按照插入顺序遍历的能力。继承HashSet,基于LinkedHashMap实现。

    特点:提供常数时间的添加、删除、包含等操作,但是性能略低于HashSet,因为要维护链表的开下,有序访问。

在遍历元素时,HashSet受自身容量影响,除非有必要,不然不要将其背后的HashMap容量设置过大。对于LinkedHashSet,由于其内部链表提供的便利,遍历性能只和元素多少有关系。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Java集合类可用于存储数量不等的对象,并可以实现常用的数据结构如栈,队列等,Java集合还可以用于保存具有映射关...
    小徐andorid阅读 1,980评论 0 13
  • 原文地址 Java集合 Java集合框架:是一种工具类,就像是一个容器可以存储任意数量的具有共同属性的对象。 Ja...
    gyl_coder阅读 999评论 0 8
  • 1.Java集合框架是什么?说出一些集合框架的优点? 每种编程语言中都有集合,最初的Java版本包含几种集合类:V...
    Oneisall_81a5阅读 911评论 0 11
  • 1.Java集合框架是什么?说出一些集合框架的优点? 每种编程语言中都有集合,最初的Java版本包含几种集合类:V...
    胖先森阅读 815评论 4 17
  • http://www.cnblogs.com/jasonHome/p/5969574.html 结合框架体系应该最...
    shhdjjj阅读 1,219评论 0 0