java基础数据结构
从开始接触软件行业开始,就知道了 程序=数据结构+ 算法。作为一名搞技术的,平时单独研究数据结构和算法的情况不多,但是这些相关的数据结构都有一直在用。
今天趁空闲时间总结下java中的相关的数据结构的知识点。
1.Array数组
Java
中除了8中基本类型,数组也是作为对象处理的,所以创建对象时也需要使用new关键字。和大多数编程语言一样,数组一旦创建,大小便不可改变。
Java中有一个Arrays
类,专门用来操作array。 Arrays
中拥有一组static函数,
- equals()
:比较两个array是否相等。array拥有相同元素个数,且所有对应元素两两相等。
- fill()
:将值填入array中。
- sort()
:用来对array进行排序。
- binarySearch()
:在排好序的array中寻找元素。
- System.arraycopy()
:array的复制。
下面是部分方法的使用理例子:
int[] demo = new int[3];
demo[0]=9;
demo[1]=0;
demo[2]=4;
Arrays.sort(demo);
for(int i:demo){
System.out.println("Arrays.sort==="+i);
}
输出结果:
Arrays.sort===0
Arrays.sort===4
Arrays.sort===9
int[] demo = new int[3];
demo[0]=9;
demo[1]=0;
demo[2]=4;
int[] demo2 = new int[3];
demo2[0]=9;
demo2[1]=0;
demo2[2]=4;
System.out.println("Arrays.equals==="+Arrays.equals(demo, demo2));
输出结果:Arrays.equals===true
Array是Java中随机访问一连串对象最有效率的数据结构,但很不灵活,大小固定,且不知道里面有多少元素。为此JDK已经为我们提供了一系列相应的类来实现功能强大且更灵活的基本数据结构。这些类均在java.util
包,结构如下:
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
│ └SortedSet
└Queue
-Map
├HashTable
├HashMap
├TreeMap
└WeakHashMap
从图中比较直观的看出java中的基本数据结构包含的继承关系,其中 List、Set、Queue、Map都是接口,不能实例化,都是需要实例化它们中的一个实现的子类。
List
List主要的实现类有LinkedList 、ArrayList、Vector,ArrayList
里面的内部实现,是通过一定的增长规则动态复制增加数组长度来实现动态增加元素的。如果在大数据量的情况下,在某一个位置随机插入或者删除元素,就会产生性能问题。LinkedList
可以解决这类问题,但LinkedList
在通过下标取元素的时候,需要遍历整个链表节点匹配,数据量大的情况下,效率不高。Vector
是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。Stack
是Java实现了一个堆栈,先进后出结构。
在实际开发过程中,有些时候使用增强for循环遍历List对元素进行删除的操作,会抛出java.util.ConcurrentModificationException
的异常,代码如下:
for(Integer i:demo){
demo.remove(i);
}
建议方法:新建一个要删除的List,最后一起删除。list.removeAll(deleteList);
Set
接口继承Collection
接口,最大的特点是集合中的元素都是唯一的,没有重复。它有两个子类,HashSet
和TreeSet
。HashSet
1.不允许出现重复元素;
2.不保证集合中元素的顺序。哈希算法来的~
3.允许包含值为NULL的元素,但最多只能有一个NULL
元素。
TreeSet
1.不允许出现重复元素;
2.集合中元素的顺序按某种规则进行排序
3.不允许包含值为NULL
的元素Map
Map是一个单独的接口,没有继承Collection,它使用key-value键值对来存储数据,常用的有HashMap、HashTable、TreeMap
- HashMap:Map
基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor,以调整容器的性能。
- LinkedHashMap
: 类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是其插入次序,或者是最近最少使用(LRU
)的次序。只比HashMap慢一点。而在迭代访问时发而更快,因为它使用链表维护内部次序。
- TreeMap
: 基于红黑树数据结构的实现。查看“键”或“键值对”时,它们会被排序(次序由Comparabel
或Comparator
决定)。TreeMap的特点在 于,你得到的结果是经过排序的。TreeMap是唯一的带有subMap()
方法的Map,它可以返回一个子树。
- WeakHashMao
:弱键(weak key)Map,Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”,则此“键”可以被垃圾收集器回收。
- IdentifyHashMap
: : 使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。
线程安全
Vector、HashTable都是线程安全的,但是相对性能要差些,对于其他的数据结果要使用线程安全的话,java中Collections这个工具类提供了相关对于的转换方法:
List synchronizedList = Collections.synchronizedList(new ArrayList());
Set synchronizedSet=Collections.synchronizedSet(new HashSet<>());
Map synchronizedMap=Collections.synchronizedMap(new HashMap<>());
使用安全的集合类
jdk也提供了相关的安全集合类都是Queue的实现类,队列的相关使用介绍,会在后面的博客中涉及到,先看看队列的类的继承关系图: