天长做网站公司,网站建设服务好公司,老房装修,女生做网站编辑怎么样数据结构
数组#xff1a;
内存地址连续检索效率高(可以通过下标访问成员)增删操作效率低(保证数据越界的问题,需动态扩容)长度固定#xff0c;扩容的需要新的数组复制或者Arrays类的copyOf方法
链表
内存地址不连续查询快删除慢#xff0c;因为需要移动指针又分双向链表… 数据结构
数组
内存地址连续检索效率高(可以通过下标访问成员)增删操作效率低(保证数据越界的问题,需动态扩容)长度固定扩容的需要新的数组复制或者Arrays类的copyOf方法
链表
内存地址不连续查询快删除慢因为需要移动指针又分双向链表和单向链表单向链表有下一个元素的指针双向有指向上一个下一个两个指针
双向链表的结构 static final class Node {// 前一个节点volatile Node prev;// 后一个节点volatile Node next;// 链表节点存储的具体数据volatile Thread thread;}队列
尾插头删管状结构先进先出
栈
尾插尾删杯状结构先进后出
集合框架
HashMap
底层是数组链表的结构hash值相同的会形成链表jdk1.8之后当相同hash值超过8个之后会变为红黑树并不是线程安全的如果想要一个安全的collections.synchronizedMap返回一个线程安全的。或者使用concurrentHashMap允许一个key为null多个value为null HashTable
是一个古老的Map实现类它不允许使用null作为键和值。Hashtable的性能略低于HashMap多线程安全。
LinkedHashMap
底层是数组链表双向链表根据添加顺序排序;线程不安全。数组和链表的作用和HashMap的作用一样双向链表是来记录键值对的插入顺序或访问顺序 TreeMap
底层是红黑树默认是根据键值字典排序就是无序也可以自己排序。compareable接口或者Comparator线程安全。
ConcurrentHashMap
ConcurrentHashMap底层采用分段的数组链表实现线程安全。通过分段锁的方式保证线程安全默认性能提高16倍。超过75%时扩容仅扩容当前分段数组1.7的实现是使用Segment数组每个Segment就是一个分段锁对应了一个HashEntry数组。每个HashEntry对应着一个node数组。get时需要计算两次Hash,第一次拿到Segment,第二次拿到对应的hashEntry。1.8后只需要一次了。1.8之后去掉了Sement分段锁直接以HashEntry为锁这样减少了锁的粒度也减少了冲突的概率。除了去掉Segment外把node数组更换为红黑树空间复杂度也从O(n)变为O(logn) HashSet
不重复且无序允许有一个null因为源自hashmap所以hash冲突时解决方法一样 LinkedHashSet
不重复且有序添加的双向链表定义了迭代顺序即按照将元素插入到集合中的顺序插入顺序进行迭代 TreeSet
底层是红黑树默认是根据键值字典排序就是无序也可以自己排序。compareable接口或者Comparator查询和删除都很快线程不安全
ArrayList
存取有序、可重复添加第一个元素时底层会创建一个新的长度为10的数组。扩容1.5倍大量数据的查询、 少量数据的增删
LinkedList
双链表 、查询慢、增删快线程不安全
