数据结构

常用的数据结构简介

线性表

  • 数组实现

    数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。可以参考ArrayList的源码。实现动态数组。

  • 链表实现

    • 单链表
  • 双向链表

    JDK中的LinkedList集合类就是双向链表

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈顶,对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表,即后进先出。

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

  • 二叉树

    • 满二叉树:一颗树为K且有2^k-1个节点为满二叉树

    • 完全二叉树: 完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

  • 平衡二叉树
  • 红黑树

并发集合和同步集合

同步集合

  • arrayList和vector、stack:

    Vector是线程安全的,源码中有很多的synchronized可以看出,而ArrayList不是。导致Vector效率无法和ArrayList相比

    ArrayList和Vector都采用线性连续存储空间,当存储空间不足的时候,ArrayList默认增加为原来的50%,Vector默认增加为原来的一倍

    Vector可以设置capacity,Increment,而ArrayList不可以,从字面理解就是capacity容量,Increment增加,容量增长的参数

    Stack是继承于Vector,基于动态数组实现的一个线程安全的栈

    arrayList、vector、Stack的共性特点:随机访问速度快,插入和移除性能较差(这是数组的特点,三者的底层均为数组实现)


  • HashMap和Hashtable:

    HashMap是非synchronized的,而Hashtable是synchronized的。这说明Hashtable是线程安全的,而且多个线程可以共享一个Hashtable

    由于Hashtable是线程安全的,也是synchronized的,所以在单线程环境下比HashMap要慢

    HashMap可以存在null的键值(key)和值(value),
    但是Hashtable是不可以的


并发集合

  • ConcurrentHashMap:线程安全的HashMap的实现
  • CopyOnWriteArrayList:线程安全且在读操作时无锁的ArrayList
  • CopyOnWriteArraySet:基于CopyOnWriteArrayList,不添加重复元素
  • ArrayBlockingQueue:基于数组、先进先出、线程安全,可实现指定时间的阻塞读写,并且容量可以限制
  • LinkedBlockingQueue:基于链表实现,读写各用一把锁,在高并发读写操作都多的情况下,性能优于ArrayBlockingQueue

List、Set、Map的区别

  • List是一个有序的队列,每一个元素都有它的索引。第一个元素的索引值是0。List的实现类有LinkedList, ArrayList, Vector, Stack。
  • Set是一个不允许有重复元素的集合。 Set的实现类有HastSet和TreeSet。HashSet依赖于HashMap,它实际上是通过HashMap实现的;TreeSet依赖于TreeMap,它实际上是通过TreeMap实现的。

  • Map是一个映射接口,即key-value键值对。Map中的每一个元素包含“一个key”和“key对应的value”。AbstractMap是个抽象类,它实现了Map接口中的大部分API。而HashMap,TreeMap,WeakHashMap都是继承于AbstractMap。
    Hashtable虽然继承于Dictionary,但它实现了Map接口。

List和Map的实现方式以及存储方式

  • ArrayLis t是一个动态数组,也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。查询很快。

  • LinkedList 同样实现List接口的LinkedList与ArrayList不同,ArrayList是一个动态数组,而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get,remove,insert方法在LinkedList的首部或尾部。

    由于实现的方式不同,LinkedList不能随机访问,它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端,节约一半时间)。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

  • Vector 与ArrayList相似,但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

  • HashMap 以哈希表数据结构实现,查找对象时通过哈希函数计算其位置,它是为快速查询而设计的,其内部定义了一个hash表数组(Entry[] table),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引,如果有冲突,则使用散列链表的形式将所有相同哈希地址的元素串起来,可能通过查看HashMap.Entry的源码它是一个单链表结构。