文档章节

Java基础篇——集合浅谈

o
 osc_w9s1w4o0
发布于 2019/04/13 23:39
字数 1443
阅读 6
收藏 0

<font color=gray> 原创不易,如需转载,请注明出处https://www.cnblogs.com/baixianlong/p/10703558.html,否则将追究法律责任!!! </font>

Set(基于Map来实现的,不细说)

HashSet(不重复、无序、非线程安全的集合)

  • 底层实现,源码如下:

      public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    
          static final long serialVersionUID = -5024744406713321676L;
      	//卖个关子,这里为啥要用transient关键字? 评论区见哦!
          private transient HashMap<E,Object> map;
          private static final Object PRESENT = new Object();
    
          public HashSet() {
              map = new HashMap<>();
          }
          public boolean add(E e) {
              return map.put(e, PRESENT)==null;
          }
      	...
      }
    

    不用多说,是不没想到,原来HashSet是基于HashMap实现的,元素都存到HashMap键值对的Key上面,而Value时有一个统一的值private static final Object PRESENT = new Object();

  • 注意:

    1. 对于HashSet中保存的对象,主要要正确重写equals方法和hashCode方法,以保证放入Set对象的唯一性
    2. HashSet没有提供get()方法,愿意是同HashMap一样,Set内部是无序的,只能通过迭代的方式获得

TreeSet(不重复、有序、非线程安全的集合)

  • 底层实现,源码如下:

      public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    
          private transient NavigableMap<E,Object> m;
          private static final Object PRESENT = new Object();
          TreeSet(NavigableMap<E,Object> m) {
              this.m = m;
          }
    
          public TreeSet() {
              this(new TreeMap<E,Object>());
          }
          public boolean add(E e) {
              return m.put(e, PRESENT)==null;
          }
      }
    

    我去,又是这个尿性,基于TreeMap来实现的

  • 注意:

    1. 首先要正确重写equals方法和hashCode方法,以保证放入Set对象的唯一性
    2. 需要实现Comparable接口,从而实现有序存储

LinkedHashSet(不重复、位置有序、非线程安全的集合)

  • 底层实现,源码如下:

      public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    
          private static final long serialVersionUID = -2851667679971038690L;
    
          public LinkedHashSet(int initialCapacity, float loadFactor) {
              super(initialCapacity, loadFactor, true);
          }
          public LinkedHashSet(int initialCapacity) {
              super(initialCapacity, .75f, true);
          }
          public LinkedHashSet() {
              super(16, .75f, true);
          }
      	public LinkedHashSet(Collection<? extends E> c) {
              super(Math.max(2*c.size(), 11), .75f, true);
              addAll(c);
          }
      }
    

    都是super,实现了把HashSet中预留的构造方法启用了,因而可以实现有序插入(LinkedHashMap再谈究竟)

  • 注意:

    1. 首先要正确重写equals方法和hashCode方法,以保证放入Set对象的唯一性
    2. 内部实现了有序插入,所以使用时不需要考虑

Map

HashMap(无序、线程不安全)

  • Jdk1.7数据存储结构(采用数组+链表)

    hashmap.png hashmap2.png

  • Jdk1.8数据存储结构(采用数组+链表+红黑树)

    hashmap3.png

    注意:在链表长度大于8后,查询复杂度由O(n)变为O(logn),将链表存储转换成红黑树存储(也就是TreeMap)

  • 红黑树R-B Tree简介(本质其实是2-3-4树):

    红黑树.png

    二叉树特性:
    (1)左字数上所有的节点的值都小于或等于他的根节点上的值
    (2)右子树上所有节点的值均大于或等于他的根节点的值
    (3)左、右子树也分别为二叉树
    红黑树特点(一种平衡二叉树):
    (1)每个结点要么是红的要么是黑的。
    (2)根结点是黑的。 
    (3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。 
    (4)如果一个结点是红的,那么它的两个儿子都是黑的。 
    (5)对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点
    节点操作:
    (1)左旋
    (2)右旋
    (3)变色
    

TreeMap(有序、线程不安全)

  • 底层就是红黑二叉树

LinkedHashMap(有序、线程不安全)

  • 底层实现,源码如下:

    static class Entry<K,V> extends HashMap.Node<K,V> {
        //这里维护了一个before和after的Entry, 见名思意, 就是每个Entry<K,V>都维护它的上一个元素和下一个元素的关系。这也是LinkedHashMap有序的关键所在。
    	Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    

    LinkedHashMap是继承HashMap, 也就是说LinkedHashMap的结构也是和HashMap那样(数组+链表)

    注意:LinkedHashMap分为插入的顺序排列和访问的顺序排列两种方式,通过accessOrder参数来控制

Hashtable(线程安全)

  • 底层数据结构同HashMap。线程安全,效率低,没什么卵用,需要使用线程安全的Map可以使用ConcurrentHashMap

List

ArrayList(位置有序、可重复、线程不安全)

  • 底层数据结构是数组,查询快

LinkedList(有序、线程不安全)

  • 底层数据结构是双向链表,查询慢,增删快

Vector(有序、线程安全)

  • 底层数据结构是数组,查询快,增删慢

并发集合

ConcurrentHashMap(线程安全)

  • 利用了锁分段的思想提高了并发度,把Map分成了N个Segment,每个Segment相当于HashTable

CopyOnWriteArrayList(线程安全)

  • 读写分离,写时复制出一个新的数组,完成插入、修改或者移除操作后将新数组赋值给array

Queue

非阻塞队列

  • PriorityQueue :实质上维护了一个有序列表
  • ConcurrentLinkedQueue :基于链接节点的、线程安全的队列

阻塞队列

  • ArrayBlockingQueue :一个由数组支持的有界队列。
  • LinkedBlockingQueue :一个由链接节点支持的可选有界队列。
  • PriorityBlockingQueue :一个由优先级堆支持的无界优先级队列。
  • DelayQueue :一个由优先级堆支持的、基于时间的调度队列。
  • SynchronousQueue :一个利用 BlockingQueue 接口的简单聚集(rendezvous)机制。

总结

  • 本来想详细的总结一下各种集合的使用和底层实现,但发现说来说去还是数据结构的事,你要能把数组、链表、二叉树、红黑树等数据结构弄明白,这些所谓的集合也就是不同的实现而已。
  • 以后有机会还是直接来搞数据结构、算法吧!

个人博客地址:

csdn:https://blog.csdn.net/tiantuo6513 cnblogs:https://www.cnblogs.com/baixianlong segmentfault:https://segmentfault.com/u/baixianlong github:https://github.com/xianlongbai

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

pycurl libcurl link-time ssl backend (nss)

pip uninstall pycurlecho 'pycurl==7.19.5.1 --global-option="--with-nss"' > requires.pypip install -r requires.py...

小红手
49分钟前
17
0
计算机网络性能衡量

1、速率 单位时间(s)内传输信息(bit)量 单位:KB/s, MB/s, Gb/s K = 10^3 ,M = 10^6, G=10^9 一般表示的是理想的传输速率 2、带宽 计算机网络中的带宽和通信等领域的带宽概念不一样,计算机网...

osc_np3y0rbq
49分钟前
3
0
互联网掀起农家乐,巨头上演AI掘金战

配图来自Canva **前有网易、阿里AI养猪,后有腾讯AI养鹅,互联网大佬们纷纷玩起了“农家乐”,互联网的生意在尖端技术的引领之下频频跨界,巨头之间的较量也从线上延伸至线下。**自古“民以食...

osc_5cok9i01
50分钟前
9
0
原来!我在4年前就开始体验雾游戏了!

前有云游戏后有雾游戏,游戏的方式看来起来越来越多种多样。那么“震撼业界”的雾游戏到底是什么来头?它依靠什么改变游戏界?它的原理又是什么? 本月月初,著名的日本游戏杂志《Fami通》表...

osc_j34n26zn
52分钟前
11
0
活动预告|田溯宁与你相约GSMA Thrive·万物生晖,分享5G风口下的创新与投资洞察

在万物互联的时代背景下,5G+AI+IoT的技术变革与融合,正在引发一场深刻的全产业创新与变革。5G技术创新、行业应用及投资机遇已成为科技行业所瞩目的焦点。 6月30日,宽带资本董事长田溯宁将...

osc_0qnrwmy3
53分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部