响应式网站建设合同,11月将现新冠感染高峰,亚马逊站外deal网站,广州网站优化外包常见的集合有哪些#xff1f;
Java集合类主要由两个接口Collection和Map派生出来的#xff0c;Collection有三个子接口#xff1a;List、Set、Queue。
Java集合框架图如下#xff1a; List代表了有序可重复集合#xff0c;可直接根据元素的索引来访问#xff1b;Set代表…常见的集合有哪些
Java集合类主要由两个接口Collection和Map派生出来的Collection有三个子接口List、Set、Queue。
Java集合框架图如下 List代表了有序可重复集合可直接根据元素的索引来访问Set代表无序不可重复集合只能根据元素本身来访问Queue是队列集合。Map代表的是存储key-value对的集合可根据元素的key来访问value。
集合体系中常用的实现类有ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等实现类。
List 、Set和Map 的区别
List 以索引来存取元素有序的元素是允许重复的可以插入多个nullSet 不能存放重复元素无序的只允许一个nullMap 保存键值对映射List 底层实现有数组、链表两种方式Set、Map 容器有基于哈希存储和红黑树两种方式实现Set 基于 Map 实现Set 里的元素值就是 Map的键值。
ArrayList 了解吗
ArrayList 的底层是动态数组它的容量能动态增长。在添加大量元素前应用可以使用ensureCapacity操作增加 ArrayList 实例的容量。ArrayList 继承了 AbstractList 并实现了 List 接口。
ArrayList 的扩容机制
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化并将原有数组内容复制到新数组中去。默认情况下新的容量会是原容量的1.5倍。以JDK1.8为例说明:
public boolean add(E e) {//判断是否可以容纳e若能则直接添加在末尾若不能则进行扩容然后再把e添加在末尾ensureCapacityInternal(size 1); // Increments modCount!!//将e添加到数组末尾elementData[size] e;return true;}// 每次在add()一个元素时arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力经过处理之后将元素存储在数组elementData的尾部private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private static int calculateCapacity(Object[] elementData, int minCapacity) {//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount;// 若ArrayList已有的存储能力满足最低存储要求则返回add直接添加元素如果最低要求的存储能力ArrayList已有的存储能力这就表示ArrayList的存储能力不足因此需要调用 grow();方法进行扩容if (minCapacity - elementData.length 0)grow(minCapacity);}private void grow(int minCapacity) {// 获取elementData数组的内存空间长度int oldCapacity elementData.length;// 扩容至原来的1.5倍int newCapacity oldCapacity (oldCapacity 1);//校验容量是否够if (newCapacity - minCapacity 0)newCapacity minCapacity;//若预设值大于默认的最大值检查是否溢出if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// 调用Arrays.copyOf方法将elementData数组指向新的内存空间//并将elementData的数据复制到新的内存空间elementData Arrays.copyOf(elementData, newCapacity);}怎么在遍历 ArrayList 时移除一个元素
foreach删除会导致快速失败问题可以使用迭代器的 remove() 方法。
Iterator itr list.iterator();
while(itr.hasNext()) {if(itr.next().equals(jay) {itr.remove();}
}Arraylist 和 Vector 的区别
ArrayList在内存不够时扩容为原来的1.5倍Vector是扩容为原来的2倍。Vector属于线程安全级别的但是大多数情况下不使用Vector因为操作Vector效率比较低。
Arraylist 与 LinkedList的区别
ArrayList基于动态数组实现LinkedList基于链表实现。对于随机index访问的get和set方法ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素LinkedList要移动指针遍历每个元素直到找到为止。新增和删除元素LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时可能扩容和复制数组LinkedList实例化对象需要时间外只需要修改指针即可。
HashMap
HashMap 使用数组链表红黑树JDK1.8增加了红黑树部分实现的 链表长度大于8TREEIFY_THRESHOLD时会把链表转换为红黑树红黑树节点个数小于6UNTREEIFY_THRESHOLD时才转化为链表防止频繁的转化。
解决hash冲突的办法有哪些HashMap用的哪种
解决Hash冲突方法有开放定址法、再哈希法、链地址法。HashMap中采用的是 链地址法 。
开放定址法基本思想就是如果pH(key)出现冲突时则以p为基础再次hashp1H(p),如果p1再次出现冲突则以p1为基础以此类推直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素而且因为存在再次hash所以只能在删除的节点上做标记而不能真正删除节点。再哈希法提供多个不同的hash函数当R1H1(key1)发生冲突时再计算R2H2(key1)直到没有冲突为止。 这样做虽然不易产生堆集但增加了计算的时间。链地址法将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
使用的hash算法
Hash算法取key的hashCode值、高位运算、取模运算。
hkey.hashCode() //第一步 取hashCode值
h^(h16) //第二步 高位参与运算减少冲突
return h(length-1); //第三步 取模运算在JDK1.8的实现中优化了高位运算的算法通过hashCode()的高16位异或低16位实现的这么做可以在数组比较小的时候也能保证考虑到高低位都参与到Hash的计算中可以减少冲突同时不会有太大的开销。
为什么建议设置HashMap的容量
HashMap有扩容机制就是当达到扩容条件时会进行扩容。扩容条件就是当HashMap中的元素个数超过临界值时就会自动扩容threshold loadFactor * capacity。
如果我们没有设置初始容量大小随着元素的不断增加HashMap会发生多次扩容。而HashMap每次扩容都需要重建hash表非常影响性能。所以建议开发者在创建HashMap的时候指定初始化容量。
扩容过程
1.8扩容机制当元素个数大于threshold时会进行扩容使用2倍容量的数组代替原有数组。采用尾插入的方式将原数组元素拷贝到新数组。1.8扩容之后链表元素相对位置没有变化而1.7扩容之后链表元素会倒置。
1.7链表新节点采用的是头插法这样在线程一扩容迁移元素时会将元素顺序改变导致两个线程中出现元素的相互指向而形成循环链表1.8采用了尾插法避免了这种情况的发生。
原数组的元素在重新计算hash之后因为数组容量n变为2倍那么n-1的mask范围在高位多1bit。在元素拷贝过程不需要重新计算元素在数组中的位置只需要看看原来的hash值新增的那个bit是1还是0是0的话索引没变是1的话索引变成“原索引oldCap”根据e.hash oldCap 0判断 。这样可以省去重新计算hash值的时间而且由于新增的1bit是0还是1可以认为是随机的因此resize的过程会均匀的把之前的冲突的节点分散到新的bucket。
put方法流程
如果table没有初始化就先进行初始化过程使用hash算法计算key的索引判断索引处有没有存在元素没有就直接插入如果索引处存在元素则遍历插入有两种情况一种是链表形式就直接遍历到尾端插入一种是红黑树就按照红黑树结构插入链表的数量大于阈值8就要转换成红黑树的结构添加成功后会检查是否需要扩容 红黑树的特点
每个节点或者是黑色或者是红色。根节点和叶子节点NIL是黑色的。如果一个节点是红色的则它的子节点必须是黑色的。从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
在解决 hash 冲突的时候为什么选择先用链表再转红黑树?
因为红黑树需要进行左旋右旋变色这些操作来保持平衡而单链表不需要。所以当元素个数小于8个的时候采用链表结构可以保证查询性能。而当元素个数大于8个的时候并且数组容量大于等于64会采用红黑树结构。因为红黑树搜索时间复杂度是 O(logn)而链表是 O(n)在n比较大的时候使用红黑树可以加快查询速度。
HashMap 的长度为什么是 2 的幂次方
Hash 值的范围值比较大使用之前需要先对数组的长度取模运算得到的余数才是元素存放的位置也就是对应的数组下标。这个数组下标的计算方法是(n - 1) hash。将HashMap的长度定为2 的幂次方这样就可以使用(n - 1)hash位运算代替%取余的操作提高性能。
HashMap默认加载因子是多少为什么是 0.75
先看下HashMap的默认构造函数
int threshold; // 容纳键值对的最大值
final float loadFactor; // 负载因子
int modCount;
int size; Node[] table的初始化长度length为16默认的loadFactor是0.750.75是对空间和时间效率的一个平衡选择根据泊松分布loadFactor 取0.75碰撞最小。一般不会修改除非在时间和空间比较特殊的情况下
如果内存空间很多而又对时间效率要求很高可以降低负载因子Load factor的值 。如果内存空间紧张而对时间效率要求不高可以增加负载因子loadFactor的值这个值可以大于1。
一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当 HashMap 当 key。String类比较常用。
因为 String 是不可变的所以在它创建的时候hashcode就被缓存了不需要重新计算。这就是 HashMap 中的key经常使用字符串的原因。获取对象的时候要用到 equals() 和 hashCode() 方法而Integer、String这些类都已经重写了 hashCode() 以及 equals() 方法不需要自己去重写这两个方法。
HashMap为什么线程不安全
多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素在多线程的环境下扩容的时候有可能导致环形链表的出现形成死循环。在JDK1.8中在多线程环境下会发生数据覆盖的情况。
HashMap和HashTable的区别
HashMap和Hashtable都实现了Map接口。
HashMap可以接受为null的key和valuekey为null的键值对放在下标为0的头结点的链表中而Hashtable则不行。HashMap是非线程安全的HashTable是线程安全的。Jdk1.5提供了ConcurrentHashMap它是HashTable的替代。Hashtable很多方法是同步方法在单线程环境下它比HashMap要慢。哈希值的使用不同HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
LinkedHashMap底层原理
HashMap是无序的迭代HashMap所得到元素的顺序并不是它们最初放到HashMap的顺序即不能保持它们的插入顺序。
LinkedHashMap继承于HashMap是HashMap和LinkedList的融合体具备两者的特性。每次put操作都会将entry插入到双向链表的尾部。
讲一下TreeMap
TreeMap是一个能比较元素大小的Map集合会对传入的key进行了大小排序。可以使用元素的自然顺序也可以使用集合中自定义的比较器来进行排序。
public class TreeMapK,Vextends AbstractMapK,Vimplements NavigableMapK,V, Cloneable, java.io.Serializable {
}TreeMap 的继承结构 TreeMap的特点
TreeMap是有序的key-value集合通过红黑树实现。根据键的自然顺序进行排序或根据提供的Comparator进行排序。TreeMap继承了AbstractMap实现了NavigableMap接口支持一系列的导航方法给定具体搜索目标可以返回最接近的匹配项。如floorEntry()、ceilingEntry()分别返回小于等于、大于等于给定键关联的Map.Entry()对象不存在则返回null。lowerKey()、floorKey、ceilingKey、higherKey()只返回关联的key。
HashSet底层原理
HashSet 基于 HashMap 实现。放入HashSet中的元素实际上由HashMap的key来保存而HashMap的value则存储了一个静态的Object对象。
public class HashSetEextends AbstractSetEimplements SetE, Cloneable, java.io.Serializable {static final long serialVersionUID -5024744406713321676L;private transient HashMapE,Object map; //基于HashMap实现//...
}HashSet、LinkedHashSet 和 TreeSet 的区别
HashSet 是 Set 接口的主要实现类 HashSet 的底层是 HashMap线程不安全的可以存储 null 值
LinkedHashSet 是 HashSet 的子类能够按照添加的顺序遍历
TreeSet 底层使用红黑树能够按照添加元素的顺序进行遍历排序的方式可以自定义。
什么是fail fast
fast-fail是Java集合的一种错误机制。当多个线程对同一个集合进行操作时就有可能会产生fast-fail事件。例如当线程a正通过iterator遍历集合时另一个线程b修改了集合的内容此时modCount记录集合操作过程的修改次数会加1不等于expectedModCount那么线程a访问集合的时候就会抛出ConcurrentModificationException产生fast-fail事件。边遍历边修改集合也会产生fast-fail事件。
解决方法
使用Colletions.synchronizedList方法或在修改集合内容的地方加上synchronized。这样的话增删集合内容的同步锁会阻塞遍历操作影响性能。使用CopyOnWriteArrayList来替换ArrayList。在对CopyOnWriteArrayList进行修改操作的时候会拷贝一个新的数组对新的数组进行操作操作完成后再把引用移到新的数组。
什么是fail safe
采用安全失败机制的集合容器在遍历时不是直接在集合内容上访问的而是先复制原有集合内容在拷贝的集合上进行遍历。java.util.concurrent包下的容器都是安全失败可以在多线程下并发使用并发修改。
原理由于迭代时是对原集合的拷贝进行遍历所以在遍历过程中对原集合所作的修改并不能被迭代器检测到所以不会触发Concurrent Modification Exception。
缺点基于拷贝内容的优点是避免了Concurrent Modification Exception但同样地迭代器并不能访问到修改后的内容即迭代器遍历的是开始遍历那一刻拿到的集合拷贝在遍历期间原集合发生的修改迭代器是不知道的。
讲一下ArrayDeque
ArrayDeque实现了双端队列内部使用循环数组实现默认大小为16。它的特点有
在两端添加、删除元素的效率较高根据元素内容查找和删除的效率比较低。没有索引位置的概念不能根据索引位置进行操作。
ArrayDeque和LinkedList都实现了Deque接口如果只需要从两端进行操作ArrayDeque效率更高一些。如果同时需要根据索引位置进行操作或者经常需要在中间进行插入和删除LinkedList有相应的 api如add(int index, E e)则应该选LinkedList。
ArrayDeque和LinkedList都是线程不安全的可以使用Collections工具类中synchronizedXxx()转换成线程同步。
哪些集合类是线程安全的哪些不安全
线性安全的集合类
Vector比ArrayList多了同步机制。Hashtable。ConcurrentHashMap是一种高效并且线程安全的集合。Stack栈也是线程安全的继承于Vector。
线性不安全的集合类
HashmapArraylistLinkedListHashSetTreeSetTreeMap
