常用的数据结构
数组
数组和链表都是线性表结构，数组在内存中是一串连续的内存空间，比如定义一个 int 类型数组，int[] array = new int[6]，计算机会为 array 分配一块连续的空间。
链表
链表是一种最常见的数据结构，其内部数据呈线性排列，属于线性表结构，什么是线性表？表中的数据按顺序依次排列，就像用一条线把数据串联起来一样。
问
数组和链表有什么区别?
数组会在内存当中开辟一块连续的存储空间，需要指定长度数组当中的每一个元素都有索引，查询的话通过索引可以直接定位到某一个元素，效率很高。但是进行删除的话，数组会进行移动，所以效率很低。
链表不需要连续的存储单元，链表中的上一个元素通过指针指向下一个元素。所以链表结构进行查询的话，头部尾部比较快，中间元素查找速度比较慢。但是删除的话，只需要删除前后指针，重新建立指针就可以了，所以删除的性能很高。
集合类或集合框架
图｜集合类总结图
collection接口是集合类的顶层接口，collections是工具类。collection有两个子接口，一个list接口，一个是set接口。
list接口
特点：list接口有序可重复。
常用的实现类：
arrayList 基于数组实现的。
linkedList 基于链表实现的，区别参考数组和链表区别。
vector 基于数组实现的，但是是线程安全的(synchronized)。
copyOnwriteArrayList 复制数组副本来实现。
set接口
特点：set接口无序不可重复
常用的实现类：
HashSet 基于hashMap来实现的，实现不可重复是通过 hashCode方法和equals方法进行两次比较，先比较hashCode，再通过equals。
TreeSet 基于二叉树来实现的，可以对元素进行排序(排序规则默认是自然顺序，可以自定义比较器，实现自定义排序)。
Map接口，key value结构的。
map接口
特点：key value结构。
常用实现类：
HashMap key不可重复，无序，可以为null。实现原理 ：基于数组和链表来实现的，当存入一组键值对的时候，先对key进行hash，然后映射到一个初始化长度为16的数组上，当不同的key产生hash碰撞的时候，value会通过链表结构来进行存储。jdk1.8之后对hashMap进行了改进，当链表长度达到临界值8，会通过红黑树来存储value。hashMap有两个参数，一个是初始化数组长度16，负载因子0.75。当满足扩容阈值的时候(当数组的12个元素被存满，并且有hash碰撞了)，动态扩容，以2倍的增长方式进行扩容。
HashTable HashTable是线程安全的hashMap（synchronized机制），key不准许为null。TreeMap基于二叉树来实现的，可对key进行自然排序（自定义比较器，写比较规则）。
ConcurrentHashMap是线程安全的，对整个hash桶采用分段策略，拆分成若干个段segment，对每一个段上锁（synchronized）,极大的提高了并发修改的效率。
网友评论